2
$\begingroup$

I have a table with $r$ rows of length $\ell$, with each cell containing a letter from an alphabet $A$ of length $a$. I'm trying to determine the expected number of distinct strings of length $k$ appearing from left to right along a row (strings cannot `loop round' or continue on the next row). I'm fairly certain that a closed form is not worth pursuing as different strings occur with different probabilities. For example, denoting by $p_J$ the probability that a string $J$ will occur on a given row, the expected number of strings is

$$ \sum_J 1-(1-p_J)^r $$

which seems very difficult to calculate.

Can we bound the above value to any extent?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.