3
$\begingroup$

I am using a letter set of four letters, say {A,B,C,D}, which is used to output a random string of letters. I want to calculate the expected output length until the word ABCD is obtained; that is, the letters A B C D appearing consecutively in that order.

I have referenced this question (Expected Number of Coin Tosses to Get Five Consecutive Heads), but have found a complexity in our case; when we obtain, say, ABA, then we can't say that the chain resets, since we have the next potentially successful chain already being started.

I have tried the approach below, but am not sure if it is completely correct.
I would be grateful for assertion that this approach is ok, as well as for any alternative methods to approach this issue.


Let e be the expected number of output letters needed to get the target string ABCD. Also, let f be the expected number of output letters needed to get the target string ABCD given we obtained the letter A.

The table for expected length and probability for e would be

|                          | Exp Len | Prob |
|--------------------------|---------|------|
| if first letter is [BCD] |   e+1   | 3/4  |
| if A then [CD]           |   e+2   | 1/8  |
| if A then A              |   f+1   | 1/16 |
| if AB then [BD]          |   e+3   | 1/32 |
| if AB then A             |   f+2   | 1/64 |
| if ABC then [BC]         |   e+4   | 1/128|
| if ABC then A            |   f+3   | 1/256|
| if ABCD                  |    4    | 1/256|
--------------------------------------------- 


and a similar table for f after we obtained the letter A would be

|                       | Exp Len | Prob |
|-----------------------|---------|------|
|if first letter is [CD]|   e+2   | 1/2  |
|if first letter is A   |   f+1   | 1/4  |
|if B then [BD]         |   e+3   | 1/8  |
|if B then A            |   f+2   | 1/16 |
|if BC then [BC]        |   e+4   | 1/32 |
|if BC then A           |   f+3   | 1/64 |
|if BCD                 |    4    | 1/64 |
------------------------------------------

The expected length e is equal to the sum of each (Probability)*(Expected Length) product set from the first table, giving $$ e\, =\, \frac{3}{4}(e+1)\, +\, \frac{1}{8}(e+2)\, +\, \frac{1}{16}(f+1)\, +\, \frac{1}{32}(e+3 )\, +\, \frac{1}{64}(f+2)\, +\, \frac{1}{128}(e+4)\, +\, \frac{1}{256}(f+3)\, +\, \frac{1}{256}(4) \\-----\\ e\, \, =\, \frac{117}{128}e\, +\, \frac{21}{256}f\, +\, \frac{319}{256} \\\\ 22e\, =\, 21f\, +\, 319 \: \: \: ---(1) \\ 44e\, =\, 42f\, +\, 638 \: \: \: ---(1') $$ A similar approach for f yields $$ f\, =\, \frac{1}{2}(e+2)\, +\, \frac{1}{4}(f+1)\, +\, \frac{1}{8}(e+3)\, +\, \frac{1}{16}(f+2 )\, +\, \frac{1}{32}(e+4)\, +\, \frac{1}{64}(f+3)\,+\, \frac{1}{64}(4) \\-----\\ f\, \, =\, \frac{21}{32}e\, +\, \frac{21}{64}f\, +\, \frac{127}{64} \\\\ 43f\, =\, 42e\, +\, 127 \: \: \: ---(2) $$ Combining these, we obtain
$$ (2)-(1')\Rightarrow f\, =\, -2e\, +\, 765 \: \: \: ---(3)\\ (3)\rightarrow (1)\Rightarrow 22e = 21(-2e+765)+319 \\ e=256 \\ f=253 $$

So the expected length seems to be 256 letters output.


I notice this is exactly what we would expect from the naive approach, from the fact that each letter has a 1 in 4 chance appearing each time, and after any four letters' output, the chance of ABCD appearing is $$ \left( \frac{1}{4} \right) ^ 4 = \frac{1}{256} . $$ which is slightly worrying, since the question about five consecutive heads has a probability of 1/32, but a differing number of 62 for the expected length.



2014/09/16 addition:
After the above, I also calculated the expected length until I obtain either of TWO target strings; I used ABCD and CDBA as my targets, if it matters. The result was not the intuitive 128, but was 136 instead, by methodology similar to that above.

Using the answers provided, I will also try to check this result using new tactics proposed in the answers.

$\endgroup$
3
$\begingroup$

The natural approach uses transition matrices. For ease of typesetting we write up the solution another way.

Let $e$ be the expected number. Let $a$ be the expected number of additional letters, given that the last letter was an A. Let $b$ be the expected number of additional letters, given the last two letters were AB. And let $c$ be the analogous thing, given the last three letters were ABC.

At the start, if the first letter is an A, our expected total is $1+a$. If it is anything else, then our expected total is $1+e$. Thus $$e=\frac{1}{4}(1+a)+\frac{3}{4}(1+e).$$

If our last letter was an A, with probability $\frac{1}{4}$ we get an A, and the additional total (after the first A) is $1+a$. If we get a B, the expected additional total after the first A is $1+b$. If we get a C or a D, the expected additional total after the A is $1+e$. Thus $$a=\frac{1}{4}(1+a)+\frac{1}{4}(1+b)+\frac{2}{4}(1+e).$$ If the last two letters were AB, and we get an A, the additional expected total after the AB is $1+a$. If we get a B or a D, the additional expected total is $1+e$. And if we get a C it is $1+c$. Thus $$b=\frac{1}{4}(1+a)+\frac{2}{4}(1+e)+\frac{1}{4}(1+c).$$ Finally, the same reasoning gives $$c=\frac{1}{4}(1+a)+\frac{2}{4}(1+e)+\frac{1}{4}(1).$$ Four linear equations, four unknowns.

$\endgroup$
  • $\begingroup$ I see that this method increases the number of variables introduced, but keeps each resulting equation simpler. I was able to reconstruct the transition matrix from your argument as well. +1 for a great generalizable solution! It would be nice if you could point me to some reference as to how to directly apply the transition matrix to obtain e... $\endgroup$ – yybtcbk Sep 16 '14 at 3:00
  • $\begingroup$ Additionally: I was able to apply this method to the addendum problem to get e=136, a=134, b=128, and c=102. It seems a bonus of this method that I can get the a, b, and c values on the way as well. $\endgroup$ – yybtcbk Sep 16 '14 at 3:03
  • $\begingroup$ Good! For transition matrices, any beginning book on Markov chains should have it, also many a basic probability book. Can't think of a specific title. $\endgroup$ – André Nicolas Sep 16 '14 at 3:09
  • $\begingroup$ I guess it's time to dig out my old Markov Chains textbook... gave up on it in Uni, but maybe I can understand it better now... thanks for the pointer! $\endgroup$ – yybtcbk Sep 16 '14 at 3:19
0
$\begingroup$

Conway's algorithm provides a quick method of calculation: look at how whether the initial letters match the final letters: so "AAAA" has matches for the initial $1,2,3,4$, while "ABCD" has matches only for the initial $4$; "ABCA" would have matches for $1$ and $4$, while "ABAB" would have matches for $2$ and $4$. Since the alphabet has four equally likely letters, the algorithm gives the following expected samples sizes:

  • AAAA: $340 = 4^4+4^3+4^2+4^1$
  • ABCD: $256 = 4^4$
  • ABCA: $260 = 4^4+4^1$
  • ABAB: $272 = 4^4+4^2$

So, as you say, the expected time until "ABCD" appears is $256 = 4^4$ samples. This is similar to the coin sequence "HHHHT" requiring an expected $32=2^5$ samples.

By contrast the expected time until "AAAA" appears is $340 = 4^4+4^3+4^2+4^1$ samples. This is similar to the coin sequence "HHHHH" requiring an expected $62=2^5+2^4+2^3+2^2+2^1$ samples.

If you had a long string of $n$ letters then you would expect "ABCD" to appear about $\frac{n-3}{256}$ times on average. Similarly you would expect "AAAA" to appear about the same number of times on average. But strings of type "AAAA" can overlap themselves while those of type "ABCD" cannot: for example a string of length $6$ might possibly have three "AAAA"s but cannot have more than one "ABCD", even if the expected number of each is the same.

To balance the greater possibility of "AAAA"s appearing several times, but the same overall expected number, there is also a greater possibility for "AAAA" not appearing at all in the first $6$ letters, or indeed in other initial samples. It is this latter feature which increases the expected sample size until "AAAA" does appear, compared with "ABCD".

$\endgroup$
  • $\begingroup$ Greatly convincing way to see that repeating letters lead to a longer expected string! This also works to suggest why the additional question results in a 136 greater than the intuitive 128; ABCD and CDBA overlap each other. Could you point me somewhere for the theory behind this Conway's Algorithm? My googling only got me algorithms for the game of life, betting odds, and calendars... $\endgroup$ – yybtcbk Sep 16 '14 at 4:10
  • $\begingroup$ As for using this Conway's Algorithm for the additional question, I guess that for target strings ABCD and CDBA, positions 2 and 4 match the last target letter, I can do 4^4 + 4^2 = 272, and then can halve this (since we have two target strings?) to get 136...? I'm not sure if this is a valid approach, but the numbers do match up... $\endgroup$ – yybtcbk Sep 16 '14 at 4:18
  • $\begingroup$ Two target strings raises the issue in Penney's game $\endgroup$ – Henry Sep 16 '14 at 7:05
  • $\begingroup$ All the links refer to the Conway Number and Conway's Algorithm in terms of odds; are these directly applicable to the string length calculations above somehow? $\endgroup$ – yybtcbk Sep 16 '14 at 8:14

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.