1
$\begingroup$

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 [42], |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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – астон вілла олоф мэллбэрг Sep 15 '16 at 1:24
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Sep 15 '16 at 3:13
  • $\begingroup$ 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... $\endgroup$ – fedja Sep 15 '16 at 13:35

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.