Where's the cheese?

Bernoulli places a mouse token at the point 0 on the real line and two cheese tokens at the points 3 3 and 3 -3 . Bernoulli then begins flipping a coin repeatedly. Each time the coin is heads, he moves the mouse 1 to the right, and each time the coin is tails, he moves the mouse 1 to the left. Let p p be the probability that the mouse will eventually get a piece of cheese. Determine the value of 100 p \lfloor 100p \rfloor .


The answer is 100.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

9 solutions

Sean Elliott
Dec 21, 2013

We seek an equation in terms of p p . Note that, if the mouse goes to either side of 0 0 , he must go through 0 0 to get to the other side. So we act like the mouse stays on one side, as if it moves to the other it has a new movement path.

Begin with the movement where the mouse eventually ends on 0 0 . We can go 0 1 0 0\rightarrow1\rightarrow0 , 0 1 2 1 0 0\rightarrow1\rightarrow2\rightarrow1\rightarrow0 , 0 1 2 1 2 1 0 0\rightarrow1\rightarrow2\rightarrow1\rightarrow2\rightarrow1\rightarrow0 , and so on. The probabilities are ( 1 2 ) 2 , ( 1 2 ) 4 , ( 1 2 ) 6 (\frac{1}{2})^2,(\frac{1}{2})^4,(\frac{1}{2})^6 , and so on. Summing these gives us an infinite geometric series; using the formula a 1 r \frac{a}{1-r} for this series, we obtain 1 4 1 1 4 = 1 3 \frac{\frac{1}{4}}{1-\frac{1}{4}=\frac{1}{3}} .

However, we were only considering one side of 0 0 ; we multiply by 2 2 to get both sides, since they are symmetric. Note that when the mouse gets to 0 0 , we are back at probability p p . So we have that p = ( 2 ) ( 1 3 ) ( p ) + other terms p=(2)(\frac{1}{3})(p)+\text{ other terms} .

The only other place where the mouse can end up is 3 3 (or 3 -3 , but again we only consider one side). Our sequence of movement paths is 0 1 2 3 , 0 1 2 1 2 3 , 0\rightarrow1\rightarrow2\rightarrow3,0\rightarrow1\rightarrow2\rightarrow1\rightarrow2\rightarrow3, and so on. Again we get a geometric sequence, this time ( 1 2 ) 3 , ( 1 2 ) 5 , ( 1 2 ) 7 , (\frac{1}{2})^3,(\frac{1}{2})^5,(\frac{1}{2})^7,\cdots . Using the same formula for the summation, we get 1 8 1 1 4 = 1 6 \frac{\frac{1}{8}}{1-\frac{1}{4}}=\frac{1}{6} . We again multiply this by 2 2 due to symmetry.

So we have the equation p = 2 3 p + 1 3 p=\frac{2}{3}p+\frac{1}{3} , which implies 1 3 p = 1 3 p = 1 \frac{1}{3}p=\frac{1}{3}\Rightarrow p=1 , so our answer is 100 p = 100 100p=\boxed{100} .

Very well explained...

Mridul Sachdeva - 7 years, 5 months ago
Ben Frankel
Dec 21, 2013

At first I was confused, because it wasn't stated how many times Bernoulli would flip a coin... I then decided that it must be infinitely many times.

If the coin is truly random, then in an infinite sequence of H or T, there must exist every subsequence of H's and T's. Thus, the mouse token must eventually reach a cheese token, making the probability p = 1 p = 1 .

100 p = 100 1 = 100 \lfloor 100p \rfloor = \lfloor 100\cdot1 \rfloor = \boxed{100}

there must exist every subsequence of H's and T's

Are you sure? What about the infinite sequence H H T T H H T T H H T T . . . HHTTHHTTHHTT... ?

Michael Tong - 7 years, 5 months ago

Log in to reply

Yes, but he said a truly random infinite sequence.

Daniel Liu - 7 years, 5 months ago

"If the coin is truly random,"

I didn't say that for no reason... of course an infinite sequence can have a pattern :)

It is given that this is a fair coin, and so this means that the infinite sequence of H and T is normal. Thus, every finite subsequence must exist, including HHHHH.

Ben Frankel - 7 years, 5 months ago

You can sort of hack the following solution up: We will show that there must exist a sequence H H H H H H H HHHHHHH with probability 1, by counting sequences that do not contain this sequence. It turns out that this satisfies the recurrence a i = a i 1 + a i 2 + a i 3 + a i 4 + a i 5 + a i 6 a_i = a_{i-1}+a_{i-2}+a_{i-3}+a_{i-4}+a_{i-5}+a_{i-6} whose characteristic polynomial has no roots with an absolute value equal to or greater than 2. (Wolfram|Alpha informs me that it's about 1.983 and -0.84). So the proportion of HHHHHHH-less sequences tends to zero.

bob smith - 7 years, 5 months ago

Log in to reply

If you generalize this to any finite string from the alphabet { H , T } \{H, T\} , then that is a proof of my statement,

If the coin is truly random, then in an infinite sequence of H or T, there must exist every subsequence of H's and T's.

Ben Frankel - 7 years, 5 months ago

When Bernoulli is on point 0 the probability he will end on -1 or 1 is 1 so we let A be the probability of Bernoulli getting to 3 or -3 from 1 or -1 respectively. Let B be the probability of Bernoulli getting to 3 or -3 from 2 or -2 respectively. Then we get the two equations:

A = 1 2 A + 1 2 B A=\frac{1}{2}A+\frac{1}{2}B

B = 1 2 A + 1 2 B=\frac{1}{2}A+\frac{1}{2}

Solving these equations will give A = 1 A=1 . It is guaranteed that Bernoulli will land on 1 or -1 in his first coin flipping therefore p = 1 × A = 1 p=1 \times A = 1 . Hence the answer is 100 p = 100 ⌊100p⌋=100

Could you please explain the two equations

Sourav Chaudhuri - 7 years, 10 months ago

Log in to reply

The first one is the probability of Bernoulli getting from 1 or -1 to 3 or -3. There are two cases: Bernoulli will go to 0 or he will go to 2 or -2. He ha a 50% chance of going to 0 and from there he is guarantied to go to either 1 or -1. From those points he has a probability of A getting to 3 or -3. He has a 50% chance of going to 2 or -2 and from there has a a probability of B getting to 3 or -3 (as mentioned in the solution).

The second one is the probability of Bernoulli getting from 2 or -2 to 3 or -3. Again, there are two cases: Bernoulli will go to 1 or -1 or he will go to 3 or -3. He has a 50% chance going to 1 or -1 and from there has a probability A of getting to 3 or -3. From 2 or -2 he has a 50% chance going to 3 or -3.

Gardar Sigurdsson - 7 years, 10 months ago

p = 0 2.5 cos 2 θ d θ p = \int_0^{2.5} \cos^{2} \theta d\theta

p = 1 2 0 2.5 ( cos 2 θ + 1 ) d θ p = \frac{1}{2} \int_0^{2.5} (\cos 2\theta + 1) d\theta

p = [ 1 4 sin 2 θ + 1 2 x ] 0 2.5 p = [\frac{1}{4}\sin 2\theta + \frac{1}{2} x]_0^{2.5}

p = 1 \lfloor p \rfloor = 1

100 p = 100 \lfloor 100p \rfloor = 100

Saad Haider - 7 years, 10 months ago
Bob Bob
Dec 21, 2013

If the mouse never reaches the cheese, this requires an infinite number of moves, so the probability is 0. If the mouse reaches the cheese, there is a finite number of steps, so the probability is not 0. Clearly only the nonzero terms will add to 1, so the mouse will always reach the cheese. 100 1 = 100 \lfloor100\cdot1\rfloor = 100

Not very rigorous, but your explanation does the job.

It turns out that the probability that the mouse reaches 3 3 is the value of the geometric sum 1 8 + 3 32 + 9 128 + = 1 2 \dfrac{1}{8}+\dfrac{3}{32}+\dfrac{9}{128}+\cdots =\dfrac{1}{2} . This also applies to 3 -3 , so our total probability is 1 2 + 1 2 = 1 \dfrac{1}{2}+\dfrac{1}{2}=1 .

Daniel Liu - 7 years, 5 months ago

Log in to reply

May I know why is that the geometric sequence?

Fan Zhang - 7 years, 5 months ago

Log in to reply

It's a little hard to explain without a diagram. The short way to say it is that it is the probability of getting there in 3 steps+ probability in 5 steps+7 steps and so on.

Daniel Liu - 7 years, 5 months ago
Aditya Joshi
Feb 6, 2014

This is a one dimensional random walk. In a one dimensional random walk, each point on the Z \mathbb{Z} line is visited an infinite number of times. The result is called the gambler's ruin. Thus the probability that the mice will eventually reach is 1 1 because it will cross the values 3 3 and 3 -3 an infinite number of times. The probability that the mouse will reach these points in k k steps is not 1 1 .

Rithvik Pasumarty
Aug 10, 2013

Before we start blindly approaching the problem, we have to think for a minute.

Bernoulli essentially flips the coin forever. So we can easily see that at one point there will be 3 3 more heads than tails or 3 3 more tails than heads. Thus we get that the probability that the mouse gets the cheese is just 1 1 . So 1 100 {1}\cdot{100} rounded down is just 100 \boxed {100}

Divyansh Singhal
Aug 6, 2013

The probability that the mouse will get cheese is 1(1/2+1/2).Hence, 100*p=100.

The probability of the mouse not getting the cheese is ( 1 / 2 ) n (1/2)^{n} , where n tends to infinity. Hence the probability of the mouse not getting the cheese tends to zero and hence, p =1. Thus [100p] = 100.

Moderator note:

The claim that "The probability of the mouse not getting the cheese is ( 1 / 2 ) n (1/2)^{n} , where n n tends to infinity" is false.

Do you know how to calculate the actual probability?

I may be wrong, but I have a few ideas.

For the mouse to not get the cheese, at the very least the number of heads and tails must be equal or differ by at most 2 (obviously, this does not by any means guarantee that the mouse doesn't get the cheese, but this is certainly a requisite ).

If we have 2 n 2n coinflips, then we need there to be n n heads and tails or n + 1 n + 1 heads and n 1 n - 1 tails or vice versa. The probability thus that the mouse doesn't reach the cheese in n n coinflips is less than ( 2 n n ) + 2 ( 2 n n + 1 ) 2 2 n \frac {{2n \choose n} + 2{2n \choose n+1}}{2^{2n}} . The limit of this expression as it tends towards infinity is 0. Since the probability that the mouse doesn't reach the cheese is less than this, that probability is also 0.

For the case when the heads and tails differ only by 1, say we have 2 n + 1 2n + 1 coinflips. The probability that the heads = n + 1 n + 1 and tails = n n or vice versa is 2 ( 2 n + 1 n ) 2 2 n + 1 \frac {2{2n+1 \choose n}}{2^{2n + 1}} . As before, the limit of this expression as n tends to infinity is 0 and the probability that the mouse doesn't reach the cheese is (empirically) less than this, so as we found before, the probability that the mouse doesn't reach the cheese is 0.

Please Calvin L. / other Challenge Masters correct my mistakes if I am wrong. Your contributions to this site are truly appreciated :)

Michael Tong - 7 years, 10 months ago

Log in to reply

For completeness, you should note that ( 2 n n ) 4 n π n \dbinom{2n}{n} \sim \dfrac{4^n}{\sqrt{\pi n}} as n n \to \infty . This can be used to show that the probability of not reaching the cheese after n n coinflips tends to 0 0 . Otherwise, your solution looks correct.

Jimmy Kariznov - 7 years, 10 months ago

A sequence of 6 tail guarantees the mouse to eat the cheese, and appears with a probability of 1 2 6 \frac{1}{2^6} . After 6N flips, the probability that such a sequence appeared is greater than the probability that such a sequence appeared in one of the disjoint N slots of size 6. The reverse probability that it does not appears in the disjoint N slots of size 6 is ( 1 1 2 6 ) n (1-\frac{1}{2^6})^n , therefore the probability that it appears is 1 ( 1 1 2 6 ) n 1-(1-\frac{1}{2^6})^n , which tends to 1. So the final probability is 1.

Mikaël Mayer - 7 years, 10 months ago

p = x y p = \sum {{x \over y}}

Saad Haider - 7 years, 10 months ago
Rindell Mabunga
Aug 5, 2013

Since flipping a coin may result in 3 or more consecutive heads or tails, the mouse WILL ALWAYS able to get it either of the 2 cheese. p = 1 because the event will surely happen. Therefore [100p] = [100(1)] = [100] = 100 [x] is the floor function of x

Moderator note:

Consider the sequence of coin flips HTHTHTHT ... In this sequence, we do not get 2 consecutive heads or tails, making the first phrase incorrect.

Even with the assumption that the first phrase is correct, consider the sequence of coin flips HTTTHTHTHT ... In this sequence, the mouse never gets the cheese, even though there is a sequence of 3 (or more) consecutive heads or tails.

Rigorously showing what Christopher H. has demonstrated:

After an odd number of steps, the mouse is at an odd integer. Thus, if the mouse never gets any cheese, the mouse must be at ± 1 \pm 1 after every odd number of steps.

Let P n P_n be the probability of not getting any cheese after 2 n + 1 2n+1 steps.

If the mouse didn't get any cheese after 2 n + 1 2n+1 steps, then it didn't get any cheese after 2 n 1 2n-1 steps. This happens with probability P n 1 P_{n-1} .

If the mouse didn't get any cheese after 2 n 1 2n-1 steps, the mouse is at ± 1 \pm 1 and must avoid taking 2 2 consecutive steps away from the origin to not get the cheese after 2 n + 1 2n+1 steps. This happens with probability 1 ( 1 2 ) 2 = 3 4 1 - \left(\tfrac{1}{2}\right)^2 = \tfrac{3}{4} .

So, the probability of not getting cheese after 2 n + 1 2n+1 steps is P n = 3 4 P n 1 P_{n} = \tfrac{3}{4}P_{n-1} .

Trivially P 0 = 1 P_0 = 1 . Solving the recursion with this I.C. yields P n = ( 3 4 ) n P_n = \left(\tfrac{3}{4}\right)^n .

So, P n 0 P_n \to 0 , and thus, mouse eventually gets cheese with probability p = 1 p = 1 .

Jimmy Kariznov - 7 years, 10 months ago

Log in to reply

You do not need to know the probability regardless, since a 1-D random walk will cross every point with probability 1 1 (level-crossing phenomenon). One such proof is given here with d = 1 d = 1 .

George Williams - 7 years, 10 months ago

Please correct me if I was wrong

Rindell Mabunga - 7 years, 10 months ago

Do not refer to my age, my true age is 15. That's my ge in Facebook :D

Rindell Mabunga - 7 years, 10 months ago

I think instead of saying "3 or more consecutive heads or tails," say "5 consecutive heads or tails." The probability of that happening eventually is also 1, and 5 consecutive heads or tails will guarantee that the mouse lands on, or goes past, -3 or 3, if it hasn't done so already.

Jiayang Zhao - 7 years, 10 months ago

Thank you for correcting me

Rindell Mabunga - 7 years, 10 months ago

I don't have a complete answer to this, but here goes:

Denote number of heads as h and number of tails as t. For the mouse to get the cheese it needs |h-t| = 3.

Consider the simplest case: the coin flips are HHH / TTT The probability of each toss is 1/(2^3) = 1/8 and there are 2 possible combinations so total probability for this case is 1/4

The next case: 5 tosses required (h = 4, t=1 and vice versa) Probability for each toss is 1(2^5) = 1/32 Possible combinations (let's consider h = 4, t = 1 and multiply by 2 since situation is symmetric): Sub case 1: T is in the first 3 tosses, no. of combinations (g) = 3C1 = 3 Total combinations =3*2 = 6 Total probability = 6/32 = 3/16

The next case: 7 tosses required (h = 5, t=2 and vice versa) Probability for each toss is 1(2^7) = 1/128 Possible combinations (consider h = 5, t = 2 and multiply by 2): Sub case 1: both T are in the first 3 tosses, no. of combinations (g) = 3C2 = 3 Sub case 2: 1 T in first 3 tosses, second T in next 2, g = 3C1 2C1 = 6 Total combinations =(3+6) 2 = 18 Total probability = 18/128 = 9/64

I've tried this for the next 2 cases, and if you add up the probabilities it goes something like this:

p = 1/4 + 3/16 + 9/64 + 27/256 + ...

This is just a infinite geometric series with ratio 3/4. It converges to a/(1-r) where a = 1/4 and r = 3/4 to give p = 1.

I realise that this is not a full solution as I have merely spotted the trend and not conclusively proved that the ratio is always 3/4. The 1/4 factor is easy: each successive case adds 2 tosses so the probability per toss decreases by a factor of 4. But I haven't been able to prove (rigorously) that the number of combinations increases by a factor of 3 for each successive case.

Christopher Ho - 7 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...