Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
The title doesn't reflect the question; the title unambiguously corresponds to a) and not to b). –  joriki Mar 17 '12 at 22:51
    
@joriki: So, what do you propose as helpful title? I would already be quite happy with an answer to a), but I included the other interpretation in case someone thinks that it is more natural / tractable. –  Phira Mar 17 '12 at 22:59
    
Perhaps you misunderstood me. I wasn't saying that b) isn't a possible interpretation of the question, only of the title. It's usually a bad idea to write something different in the title than in the question. I would simply put the formulation in the question into the title: "probability of reading $2012$ without having read $012$ beforehand in a random infinite sequence of digits $0$, $1$, $2$" –  joriki Mar 17 '12 at 23:03
    
@joriki You mean "What is the probability that one reads "2,0,1,2" without having read "0,1,2" beforehand?" without explaining where one reads what? –  Phira Mar 17 '12 at 23:05
    
@joriki I edited the question. –  Phira Mar 17 '12 at 23:09

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer
    
So, $X$ neither ends with a prefix of 012 nor with a prefix of 2012? –  Phira Mar 18 '12 at 1:43
    
In that case, it seems that patterns of the form 0012 are not considered in the calculation. –  Phira Mar 18 '12 at 1:45
    
@Phira: Yes, 0012 is included: it will result in the sequence of states A,B,B,C,D. X is not necessarily the same string in every line. If you really want I can spell out more precisely which strings correspond to which states. –  Nate Eldredge Mar 18 '12 at 2:01
    
Could you maybe reformulate the sentences before the states as in "The states are the longest substrings at the end of the strings that are prefixes of either 2012 or 012"? I think that I can see now what my error was, but I still have to sleep on it. –  Phira Mar 18 '12 at 3:41
1  
@Phira: Okay, I made my states precise. –  Nate Eldredge Mar 18 '12 at 3:47

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$
share|improve this answer
    
If you're using interpretation a), then this is very likely wrong; I wrote a simulation and get values very close to $8/27$, the official answer, and far from $10/29$. –  joriki Mar 18 '12 at 0:42
    
You have no state ending in $00$. –  joriki Mar 18 '12 at 0:52
    
@joriki: First point: I have an error in the transition which I will correct and get Nate's answer. Second point: True - but B $X0$ was designed to cover it. –  Henry Mar 18 '12 at 1:04
    
Comparing our solutions, I see the error in yours: C cannot transition to E but it can transition to B. With that correction, you should get a value numerically close to mine. Also, the string X should be interpreted a little differently: your definition doesn't cover strings like 00 and 22. –  Nate Eldredge Mar 18 '12 at 1:05
    
@Nate: Thanks - I had deduced this from joriki's comments and I now get the same answer –  Henry Mar 18 '12 at 1:15

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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