Probability question -- Infinite series?

Question

A & B play game where they toss a coin. A starts first. The first one to get five heads wins. What is the probability of A winning? Even if you could give me some pointers to approach this, that will be great.

Sorry if the question was not clear -- A tosses a coin then B tosses it and so on and so on. The first person to get 5 Heads wins. So if we have a situation after 18 tosses where --
A --> HHTTTTHHT
B --> TTHTHHHTH
then B has won because B got five heads before A.

You will definitely notice that since A goes first, he has a higher probability than B. Just thought I will clarify

Answer 1

You need to work backwards on this problem.

Let Pmn be the odds of A winning given that
a) it is A's turn to move
b) A has m heads
c) B has n heads

Obviously P50=P51=P52+P53=P54 = 1.0
Obviously P05=P15=P25=P35=P45 = 0.0

Consider P44:
if A now flips a head A wins and the game is over. There is 0.5 chance this will happen. If A flips a tail and B flips a head the game is over and A loses. If they both flip a tail we are at the same state, P44.
SO P44 = 0.5(1.0) + 0.25(0.0) + 0.25(P44) or
P44 = 0.5/0.75 = 2/3

Similarly P43 = 0.50(1.0) + 0.25(P44) + 0.25(P43)
or P43 = 0.50(1.0) + 0.25(2/3) + 0.25(P43)
P43 = 8/9

In general:
Pmn = ( P(m+1)(n+1) + P(m+1)n + Pm(n+1) +Pmn ) / 4
or Pmn = 1/3 * ( P(m+1)(n+1) + P(m+1)n + Pm(n+1) )

You work this all the way back to the calculation of P00 when you will get the answer you want. It's ugly but it works.

This was easy to do in excel with the following results.
The probabilities go from P00 in the top left corner to P55 in the bottom right corner. Columns are increasing n and rows are increasing m.

0.549 0.354 0.173 0.055 0.008 0.000
0.737 0.556 0.332 0.132 0.025 0.000
0.886 0.768 0.568 0.296 0.074 0.000
0.968 0.922 0.815 0.593 0.222 0.000
0.996 0.988 0.963 0.889 0.667 0.000
1.000 1.000 1.000 1.000 1.000 1.000

The final answer is that A to move first has 0.549 chance of getting to 5 heads first.

The exact probability is 10802/(3^9) = 0.5487984555... .

Answer 2

You can simplify this problem quite a bit if you reformulate it a little.

Let's say A needs x scores (heads) to win, and B needs y scores to win.
We don't have to be fair.
If A needs x, B needs y, and it's A's turn to flip, call this game (x,y,A); if it's B's turn, call the game (x,y,B). Thus we are not looking at just one game, but a whole family of games, depending on x and y.

So the question as stated is:
What's the probability of A winning the game (5,5,A)?

Let P(x,y,A) be A's probability of winning (x,y,A),
and P(x,y,B) be A's probability of winning (x,y,B).
Note that all the probabilities are for A to win. The probability for B to win (x,y,?) is 1 - P(x,y,?), because the probability of no win ever occuring is 0.

The first thing to do is to establish that when it's a player's turn, that player has a 2/3 probability of getting the next score
p(H) + p(T t H) + p(T t T t H) + p(T t T t T t H) + ... = 2/3
and the probability is 1/3 that the other player will get the next score
p(T h) + p(T t T h) + p(T t T t T h) + ... = 1/3

Now, say we're playing game (x,y,A). If A get the next score, then we'll be playing game (x-1,y,B). If B gets the next score, then we'll be playing game (x,y-1,A). So
P(x,y,A) = (2/3)*P(x-1,y,B) + (1/3)*P(x,y-1,A)
Similarly,
P(x,y,B) = (1/3)*P(x-1,y,B) + (2/3)*P(x,y-1,A)

These are double-induction formulas for calculating P(x,y,?). So we need a basis, which is
P(0,y,A) = P(0,y,B) = 1 for any y > 0, and
P(x,0,A) = P(x,0,B) = 0 for any x > 0.

Getting back to the original question, if my calculations are correct,
P(5,5,A) = 10802 / (3^9) = 0.548798.

P(n,n,A) converges to 0.5 as n increases, but it appears to converge extreeeeeemely slowly.
These calculations are tedious to do by hand, but are easy with a spreadsheet.

Answer 3

The probabilities here come from Negative Binomial distributions, not the Geometric. The geometric distribution is used for finding the probability that the first success will happen on a given trial. The Negative Binomial is a model for finding the probability that the rth success occurs on a given trial.

If X has the negative binomial distribution with success probability p then the probability the rth success occurs on the xth trial is:

P(X = x) = (x - 1) ! / ( (r-1)! (x - r)! ) * p^r * (1 - p) ^ (x - r)

The expectation of the negative Binomial is r/p
The variance of the negative Binomial is r (1-p) / p²

Since the negative binomial can be expressed as a sum of independent geometric random variable, and thanks to the wonders of the central limit theorem we are able to approximate the negative binomial with the normal distribution.

A ~ Normal( μ = r/p, σ² = r(1 - p)/p²)
A ~ Normal( μ = 10, σ² = 10)
B ~ Normal( μ = 10.5, σ² = 10)

now where did I get the mean for B to be 10.5? Well, think of each trial having two parts, the first part is A's flip, the second is B's flip. A would be expected to win on the 10th trial and B on the second half of the second trial, thus the mean of B is 10.5.

Find P(A < B) = P( A - B < 0)

A and B are independent random variables so

A - B ~ Normal( μ = -0.5, σ² = 20)

P( A - B < 0 ) = P( Z < 0.5 / sqrt(20))
= P( Z < 0.1118034)
= 0.5445104

To verify this calculation I wrote a simulation R. This simulation counts the number of times A wins a the number of times B wins.

A <- 0;
B <- 0;
Awins <- 0;
Bwins <- 0;
games <- 0;

flips <- 1000000;

for(i in 1:flips)
{
A <- A + rbinom(1,1,0.5);
B <- B + rbinom(1,1,0.5);

if(A == 5) {
Awins <- Awins + 1;
games <- games + 1;
A <- 0;
B <- 0;
}

if(B == 5 ){
Bwins <- Bwins + 1;
games <- games + 1;
A <- 0;
B <- 0;
}
}

Awins/games
Bwins/games

Three different runs of the code produced these outputs:

> Awins/games
[1] 0.550041
> Bwins/games
[1] 0.449959

> Awins/games
[1] 0.5490916
> Bwins/games
[1] 0.4509084

> Awins/games
[1] 0.5503858
> Bwins/games
[1] 0.4496142

so experimentally i get the probability that A wins to be about 55% and using the normal approximation to the negative binomial I get 54.5%, not a bad estimate

Answer 4

Hey, this seems quite tricky, I could answer it if the first person to get 1 heads (rather than 5 heads) wins. So I will tell you the method for that (in case you don't know), then perhaps it will help.

Probability of A winning on his 1st go: 1/2
Probability of A winning on his 2nd go: 1/2 * 1/2 * 1/2 = 1/8 (you can see where this comes from I hope)
Probability of A winning on his 3rd go: 1/2 * 1/2 * 1/2 * 1/2 * 1/2 = (1/2)^5 = 1/32
Probability of A winning on his 4th go: (1/2)^7 = 1/128

and so on...

Hence, overall probability of A winning is (1/2 + 1/8 + 1/32 + ...)

So we have a geometric series with 1st term 1/2 and common ratio 1/4.

The sum to infinity is (a / 1-r) where a is the first term and r is the common ratio.

Hence: 1/2 / (1-1/4) = 2/3.

The probability of A winning is 2/3. Like I said this is for the case where 1 heads wins, not sure about the case where you have to get 5 heads... I will add more if I think of anything else.

Answer 5

I don't think that your series correctly represents the probability - you simply need the first series since B loses on even rolls and you can easily compute the first geometric series. (See below) However, if you're interested in series in general, the series you have there, Σ (as n = 0 to ∞) [(-1)^n*][1/6*(5/6)^n] is just an alternating geometric series and is fairly easy to compute. It's a good thing that you split this series up into sums with even and odd powers respectively as you can easily compute both sums and add them. As you noticed, the series is positive for even powers of 5/6 and negative for odd powers of 5/6. Recall that the sum of a convergent infinite geometric series is a/(1 - r) where a is the first term and r is the common ratio. This formula works provided |r| < 1, otherwise the series is divergent. So, looking at the split up series you have Σ (as n = 0 to ∞) [(1/6)(5/6)^(2n)] - Σ (as n = 0 to ∞) [(1/6)(5/6)^(2n+1)] So, the first sum has common ratio 25/36 and the first term of the series, when you evaluate at n = 0, is just 1/6. To see that the common ratio is 25/36, recall the general form of the geometric series is Σ (as n = 0 to ∞) [ar^n] So, to find the common ratio, I need to get it into that form. Just look at the (5/6)^(2n) term, which you can rewrite as [(5/6)^2]^n, by using a property of exponents that a^(mn) = (a^m)^n. Therefore, you get [(5/6)^2]^n = (25/36)^n. So, if you want to rewrite the first series you get Σ (as n = 0 to ∞) [(1/6)(25/36)^n] As we said, the common ratio is 25/36 and the first term is 1/6, so a/(1 - r) = (1/6)/(1 - 25/36) = (1/6)/(11/36) = 36/66 = 6/11. For the other series, we do something similar. Σ (as n = 0 to ∞) [(1/6)(5/6)^(2n+1)] We can change (5/6)^(2n+1) to (5/6)(5/6)^(2n) since we can use the property that a^(m+n) = (a^m)*(a^n). And we do the same thing as before on (5/6)^(2n) to make it (25/36)^n. So, we have Σ (as n = 0 to ∞) [(1/6)(5/6)(25/36)^n] We can go ahead and multiply 1/6 and 5/6 and we get Σ (as n = 0 to ∞) [(5/36)(25/36)^n] So, the first term is 5/36 and the common ratio is 25/36 so, a/(1 - r) = (5/36)/(1 - 25/36) = (5/36)/(11/36) = 5/11. So, in the end we have Σ (as n = 0 to ∞) [(1/6)(5/6)^(2n)] - Σ (as n = 0 to ∞) [(1/6)(5/6)^(2n+1)] Where Σ (as n = 0 to ∞) [(1/6)(5/6)^(2n)] = 6/11 and Σ (as n = 0 to ∞) [(1/6)(5/6)^(2n+1)] = 5/11. Therefore their difference is just 1/11. Hope that helps!

Answer 6

Keep this open

Brilliant work by Martin We and Merlin!

I need some time to digest these approaches, but it's great to learn something new.

In Martin We's explanation, he mentions that the probability simplifies to 10802/e^9. However, when I factor 10802 into its primes, I get 2 X 11 X 491, which is strange, given that it consists of multiplying a lot of small numbers together.

Answer 7

It has to be a long answer. However A will definitely have the edge over B as he starts the game and his winning would be more than 0.5 probability.

The approach would be to sum up the probabilities of A winning as = A wins in 5 chances + (A wins in 6th chance * B does not win in 5th chance) + (A wins in 7 chances * B does not win it in 6th chance).....infinite series

This I am sure will result in a mathematical progression....just expand and see...

Answer 8

A probability of 1/2 says that you are likely to get heads half the time that you flip a coin. People also sometimes say that the probability of getting heads is fifty-fifty. The fraction, 1/2, can be converted into a decimal number. Divide 2 into 1 and you get .5. Convert this to a percentage by multiplying by 100. You get 50%. Heads will turn up 50% of the time, which is why people say the chances are fifty-fifty.

The probability of getting heads on any coin toss is 1/2 even if you've tossed the coin ten times and it has come up heads every time. You still have a fifty-fifty chance of getting heads on the eleventh toss. Each coin toss is independent of all the others. Hope you got it.

Answer 9

I am not sure of my answer. If your question were, "The first one to get one head wins," the situation would be the same. We do not know how many times they toss the coin. In any one toss, the probability of throwing a head is 1/2 for both.
We want the number of tosses required before 5 heads show up. This may range anywhere from 5 to infinity for both. If n1 and n2 represent the number of tosses for A and B, A wins if n1 > n2 and B wins if n2 > n1.
See if you can figure this out using the answers and reading the description of the geometric distribution.

Answer 10

Both A and B have equal chances of winning. The chance of winning is 1/2^5 = 1/32.
The chance of winning head in one throw is 1/2. To win heads five times consecutively you should multiply 1/2 by 1/2 5 times = 1/2^5 = 1/32
-TJ