4
$\begingroup$

The following problem is from the semifinals of the Federation Francaise des Jeux Mathematiques:

One draws randomly an infinite sequence with digits 0, 1 or 2. Afterwards, one reads it in the order of the drawing.

What is the probability that one reads "2,0,1,2" without having read "0,1,2" beforehand?

Besides the obvious assumption that digits are drawn independently with equidistribution, I am primarily interested in the following interpretation:

*) If the sequence starts with 0,1,2,0,1,2 one regards this as having read 0,1,2 before 2,0,1,2 because the first pattern is finished before the second.

In addition, I would also like a solution to the following alternative interpretation, especially if it turns out to be easier to calculate:

*) If the sequence starts with 0,1,2,0,1,2 one regards this as NOT read 0,1,2 before 2,0,1,2 at this point because the first pattern has not finished before the second starts.

  • 0
    Empirically, $8/27$ seems to be correct for a).2012-03-18

3 Answers 3

4

I took an approach very similar to Henry's (edit: but independently), with a Markov chain, and I also get $8/27$.

If X represents any string not relevant to the pattern, our states are

 A : X B : X0 C : X01 D : X012 E : X2 F : X20 G : X201 H : X2012 

Let $a,b,c,d,e,f,g,h$ represent the probability of finding 2012 before another 012 when starting in state A,B,C,D,E,F,G,H respectively. Then by considering the possible transitions, we get the system of equations: $\begin{align*} a &= \frac{1}{3}(b+a+e) \\ b &= \frac{1}{3}(b+c+e) \\ c &= \frac{1}{3}(b+a+d) \\ d &= 0 \\ e &= \frac{1}{3}(f+a+e) \\ f &= \frac{1}{3}(b+g+e) \\ g &= \frac{1}{3}(b+a+h) \\ h &= 1. \end{align*}$ Solving this system (I used Maple because I'm lazy) gives $a=8/27$.

Edit: I'll be precise about the states. In the following, Y represents any string not containing 012. The state corresponding to a given string is the first entry in the list that matches the string.

 H: Y2012 D: Y012 G: Y201 C: Y01 F: Y20 B: Y0 E: Y2 A: Y 

This covers all strings, except those which contain 012 somewhere other than the end. We need not consider those, since as soon as we see 012, the rest of the string is irrelevant and we need not continue drawing.

  • 1
    @Phira: Okay, I made my states precise.2012-03-18
1

Corrected for joriki's comment and so now similar to Nate

Based on a Markov chain between the positions

  • A: $X$
  • B: $X0$
  • C: $X01$
  • D: $X012$ (absorption)
  • E: $X2$
  • F: $X20$
  • G: $X201$
  • H: $X2012$ (absorption)

where $X$ is any string which will not lead to absorption (possibly because of what follows) and might be empty.

So the transition matrix (or perhaps its transpose) looks like

          A         B         C D         E         F         G H A 0.3333333 0.0000000 0.3333333 0 0.3333333 0.0000000 0.3333333 0 B 0.3333333 0.3333333 0.3333333 0 0.0000000 0.3333333 0.3333333 0 C 0.0000000 0.3333333 0.0000000 0 0.0000000 0.0000000 0.0000000 0 D 0.0000000 0.0000000 0.3333333 1 0.0000000 0.0000000 0.0000000 0 E 0.3333333 0.3333333 0.0000000 0 0.3333333 0.3333333 0.0000000 0 F 0.0000000 0.0000000 0.0000000 0 0.3333333 0.0000000 0.0000000 0 G 0.0000000 0.0000000 0.0000000 0 0.0000000 0.3333333 0.0000000 0 H 0.0000000 0.0000000 0.0000000 0 0.0000000 0.0000000 0.3333333 1 

and putting it to a very high power gives

          A         B         C D         E         F         G H A 0.0000000 0.0000000 0.0000000 0 0.0000000 0.0000000 0.0000000 0 B 0.0000000 0.0000000 0.0000000 0 0.0000000 0.0000000 0.0000000 0 C 0.0000000 0.0000000 0.0000000 0 0.0000000 0.0000000 0.0000000 0 D 0.7037037 0.7407407 0.8148148 1 0.6666667 0.6296296 0.4814815 0 E 0.0000000 0.0000000 0.0000000 0 0.0000000 0.0000000 0.0000000 0 F 0.0000000 0.0000000 0.0000000 0 0.0000000 0.0000000 0.0000000 0 G 0.0000000 0.0000000 0.0000000 0 0.0000000 0.0000000 0.0000000 0 H 0.2962963 0.2592593 0.1851852 0 0.3333333 0.3703704 0.5185185 1 

so starting at $A$ the probability of reaching $H$ is $0.2962963$ or $\frac{8}{27}$.

Now let's do it with simultaneous equations, using $P_k$ to mean the probability of ending with 2012 starting at k. We have

  • $P_H = 1$
  • $P_D = 0$
  • $P_A = (P_A + P_B + P_E)/3$
  • $P_B = (P_B + P_C + P_E)/3$
  • $P_C = (P_A + P_B + P_D)/3$
  • $P_E = (P_A + P_E + P_F)/3$
  • $P_F = (P_B + P_E + P_G)/3$
  • $P_G = (P_A + P_B + P_H)/3$

and these eight equations and eight unknowns have the solutions

  • $P_A = \frac{8}{27}$
  • $P_B = \frac{7}{27}$
  • $P_C = \frac{5}{27}$
  • $P_D = 0$
  • $P_E = \frac{9}{27}$
  • $P_F = \frac{10}{27}$
  • $P_G = \frac{14}{27}$
  • $P_H = 1$
  • 0
    @Phira: If you make that point, you might make the same point about B and F, or C and G, or even A and E. But D is supposed not to include H - if there is $\ldots2012$ then I am taking the $2$ contributes to the absorption even though there would be a different absorption is the 2 was not present.2012-03-18
1

I have learned about another answer that may be the shortest:

The probability that 012 is in the first position is $1/27$.

The probability that 012 is preceded by 0 is 1/3.

(Because putting a 0 before the first 012 never forms a new 012 and thus gives a bijection from all strings to this case, where the 1/3 is the probability of drawing 0.)

The probability that 012 is preceded by 1 is 1/3.

(Same argument, but note that the argument does not work for 2 because this might form an earlier instance of 012.)

Now, the probability of having the first 012 preceded by 2 is the complementary probability:

$1-1/3-1/3-1/27=8/27$.