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?


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.