# $42$ letters on a typewriter

Imagine a bear is typing on a typewritter, and the bear is planning to write a $42$-letter string with only the English alphabet (consider only lower-case letters). Any given letter has equal probability of being written at a given point in the string. I want to find the probability that there is some sub-sequence of letters (not necessarily one right after another, but nonetheless in a sequential ordering) such that the subsequence is "panda." I.e. we are looking for the probability that, given the string $S$, $\exists A \subset , |A| = 5. S_A = \text{"panda"}$. To clarify what I mean, let's consider some strings: $$a = \text{pandafda}$$ $$b = \text{pfantreda}$$ $$c = \text{eqeryads}$$ $$d = \text{andapdf}$$ We can see that $a_{[1:5]} = \text{panda},$ and so $a$ does satisfy our event. $b$ also satisfies our event since $b_{[1,2,3,7,8]} = \text{panda}.$ $c$ does not satisfy our event, since their is no subsequence that spells out panda. $d$ also doesn't satisfy our event, as while there are a set of letters that do spell out panda, they are not in a sequential ordering (i.e. p occurs after the rest of the letters have been stated).

I was wondering, what may be a good first step to handle finding this probability? To me this seems like a tough problem to count the number of ways this subsequence can occur in a $42$-letter string. Any recommendations would be appreciated.

• This is a very difficult question, because the substring panda could appear up to $8$ times in a $42$ letter string, and you could end up counting all of them in terms of occurences of panda, when in truth they should be counted as one string. – астон вілла олоф мэллбэрг Sep 15 '16 at 1:24

Just set up the Markov chain with 6 states according to what beginning you already have. Note that adding a letter cannot spoil the progress and adding a wrong letter cannot advance it. The transition probability matrix is very simple because at each step there is exactly one letter that advances the chain. It is just $P=\frac{25}{26}I+\frac{1}{26}J$ where $J$ is the "above diagonal unit matrix", which makes raising it to the 42-nd power a child game (the same story as with a single Jordan block). You have just one absorbing state (all letters are there) and you need the element in $P^{42}$ in the right top corner (going from no letters to all letters). The rest should be clear.
• This can be computed in a spreadsheet. Each column represents a state, each row a number of letters in the string. At zero letters the chance of having zero letters (state 0) is $1$. In most cells the chance is $1/26$ times the cell up and left plus $25/26$ times the cell above. Copy right and down. Fix columns 1 and 6. – Ross Millikan Sep 15 '16 at 3:13
• Or on any decent calculator. After all ${42\choose 5}\left(\frac{25}{26}\right)^{37}\left(\frac{1}{26}\right)^5$ is not such a terrible expression... – fedja Sep 15 '16 at 13:35