| Summary: | When considering binary strings, it's natural to wonder how many distinct
subsequences might exist in a given string. Given that there is an existing
algorithm which provides a straightforward way to compute the number of
distinct subsequences in a fixed string, we might next be interested in the
expected number of distinct subsequences in random strings. This expected value
is already known for random binary strings where each letter in the string is,
independently, equally likely to be a 1 or a 0. We generalize this result to
random strings where the letter 1 appears independently with probability
$\alpha \in [0,1]$. Also, we make some progress in the case of random strings
from an arbitrary alphabet as well as when the string is generated by a
two-state Markov chain.
|
|---|