Probability Challenge 2!?

I assume that "wins" means "is the first player to flip the coin so that it's the third consecutive flip of the same type" (this isn't clear from your question). Let me know if this is not correct.

I agree that the probability is 60%.

For definiteness, let us say "It is Player 1's turn" to mean that Player 1 is about to flip the coin, and similarly for "It is Player 2's turn."

This game has a finite number of describable states, namely:

1. It is player 1's first turn

2. It is player 1's turn, and only one of the same flip has happened in a row

3. It is player 1's turn, and two of the same flip have happened in a row

4. It is player 2's turn, and only one of the same flip has happened in a row

5. It is player 2's turn, and two of the same flip have happened in a row

6. Player 1 has won the game

7. Player 2 has won the game

Each time the coin is flipped, the state will switch from one to another, with certain probabilities depending on what the current state is. (For example, if the game is in State 2, then after one coin flip, there is a 50% probability of transitioning to State 4, and a 50% probability of transitioning to State 5.)

It will be easier to model this problem in the way I want if we assume the coin flips continue indefinitely. There is no harm in continuing to flip coins after Player 1 has already won--we'll just say that, once the game is in State 6, it always stays there (because Player 1 was still the first to end his turn with a third flip of the same type).

The transition probabilities are:

* When in State 1, there is a 100% chance of transition to State 4

* When in State 2, there is a 50% chance of transition to State 4, and a 50% chance of transition to State 5

* When in State 3, there is a 50% chance of transition to State 4, and a 50% chance of transition to State 6

* When in State 4, there is a 50% chance of transition to State 2, and a 50% chance of transition to State 3

* When in State 5, there is a 50% chance of transition to State 2, and a 50% chance of transition to State 7

* When in State 6, there is a 100% chance of transition to State 6

* When in State 7, there is a 100% chance of transition to State 7.

This information can be encoded in the following 7 x 7 stochastic matrix:

[0.0 0.0 0.0 0.0 0.0 0.0 0.0]

[0.0 0.0 0.0 0.5 0.5 0.0 0.0]

[0.0 0.0 0.0 0.5 0.0 0.0 0.0]

[1.0 0.5 0.5 0.0 0.0 0.0 0.0]

[0.0 0.5 0.0 0.0 0.0 0.0 0.0]

[0.0 0.0 0.5 0.0 0.0 1.0 0.0]

[0.0 0.0 0.0 0.0 0.5 0.0 1.0]

The entry in the ith row and the jth column corresponds to the probability of transitioning to State i, given that we start in State j. Let us call this matrix "M."

If v is a 7 x 1 vector where the ith entry is the probability that we are currently in State i, then Mv is a 7 x 1 vector where the ith entry is the probability that we will be in State i after one iteration of the game. This fact follows from a few basic facts about probability and the definition of matrix multiplication.

Since the game starts off in State 1 (with certainty), then we should let v be the following vector:

[1]

[0]

[0]

[0]

[0]

[0]

[0]

To find the probability that Player 1 wins, we should compute lim n->∞ [M^n * v]; this vector should only have entries in the 6th and 7th places (because, after many flips, the probability that no one has won the game approaches zero), and the entry in the 6th place will be the probability that Player 1 wins.

Mathematica gives the result of this limit as a vector with 0.6 in the 6th place and 0.4 in the 7th place.

So the probability that Player 1 wins is 60%.

---

This solution is a little unsatisfactory (to me) because I haven't proven what the limit is analytically. It turns out that the matrix M above is diagonalizable, though, so it should be possible to do this in principle--one just needs to argue that, for large values of n, the matrix M^n is close to

[0.0 0.0 0.0 0.0 0.0 0.0 0.0]

[0.0 0.0 0.0 0.0 0.0 0.0 0.0]

[0.0 0.0 0.0 0.0 0.0 0.0 0.0]

[0.0 0.0 0.0 0.0 0.0 0.0 0.0]

[0.0 0.0 0.0 0.0 0.0 0.0 0.0]

[0.6 0.4 0.8 0.6 0.2 1.0 0.0]

[0.4 0.6 0.2 0.4 0.8 0.0 1.0]

Diagonalizing M makes it easy to compute M^n for large values of n, so it should be possible to see that M^n converges to this matrix by looking at its diagonal form. (I don't want to actually carry out this argument--diagonalizing a 7 x 7 matrix by hand would surely take an awfully long time.)

Presumably this problem could also be solved by using combinatorics only (no linear algebra), but it is not clear to me at this time how to accomplish this in a straightforward way. I may revisit your question later when I have some more time.

Each time the coin is flipped, the state will switch from one to another, with certain probabilities depending on what the current state is. (For example, if the game is in State 2, then after one coin flip, there is a 50% probability of transitioning to State 4, and a 50% probability of transitioning to State 5.)

It will be easier to model this problem in the way I want if we assume the coin flips continue indefinitely. There is no harm in continuing to flip coins after Player 1 has already won--we'll just say that, once the game is in State 6, it always stays there (because Player 1 was still the first to end his turn with a third flip of the same type). http://www.maxchallengecoins.com/

You almost have to do a monte carlo simulation in order to answer this ! There is a mathematical way, but it leads to unsolvable expressions that need to be evaluated by computer :

Name P[n,x] the chance that there are n identical outcomes after x throws, then we have

P[1,x] = 1/2

P[2,x] = (1/2) P[1,x-1] / (1-P[3,x-1]) = (1/4) / (1-P[3,x-1])

P[3,x] = (1/2) P[2,x-1] / (1-P[3,x-1]) = (1/8) / (1-P[3,x-2])*(1-P[3,x-1])

The last equation is a recursive equation

f1=f2=0

f3=1/4

fn = (1/8) / (1-fn-1)*(1-fn-2)

This recursive difference equation can be solved analytically maybe, but i don't know that.

I will solve it numerically because it converges very fast. I will come up with the

result any minute ... One moment please.

fn -> 0.191 very fast

The computer gives exactly 60 % chance for player 1 to win.

Here is the program that performed the calculation :

int throw()

{

return(rand()%2);

}

main()

{

long i,w[2],notend,counter;

double odd,even,px,px2,f[1001];

int t,t1,t2;

f[1]=0.0;

f[2]=0.0;

f[3]=0.25;

for(i=4;i<=1000;i++) f[i]=0.125/((1-f[i-1])*(1-f[i-2]));

odd = 0.0; even=0.0; px2=0.0;

for(i=3;i<=1000;i++)

{

px = (1-px2)*f[i];

px2 += px;

if (i%2==1) odd += px; else even += px;

}

printf("\n%4.8f %4.8f %4.8f %4.8f\n",odd,even,f[100],f[1000]);

printf("\nMonte Carlo simulation...\n");

w[0]=0;

w[1]=0;

for(i=1;i<=1000000;i++)

{

notend=1;

counter=0;

t1=-1;

t2=-1;

while(notend)

{

counter++;

t = throw();

if ((t==t1) && (t==t2)) { w[counter%2]++; notend=0; }

t2=t1;

t1=t;

}

}

printf("\n%ld",w[1]);

}

50/50

you can do it in solo, but not in local.