Tough probability question

Factual Questions
21

Ok, here goes.

The number of tails you flip before the first head is unimportant. So we can ignore them and assume the first flip gives us a head.

When N=2, the chance of winning outright is 1/2, and the chance you will go to N=3 is also 1/2.

When N=3, the chance of winning is 1/4, there is a 1/2 chance of going to N=4, and a 1/4 chance of gooing to N=5.

When N=4:

1/8 Win
1/2 go to N=5
1/4 go to N=6
1/8 go to N=7

And so on.

What we want to do is add up all the probabilies of wins. The terms of this seris will be the probability of an outright win for a given N times the probability of ever getting to that N.

1/2 * 1 + 1/4 * 1/2 + 1/8 * 1/2 * 1/2 + 1/16 * 1/2 * 1/2 * 1/2 + 1/16 * 1/4 * 1/2 …

This last term is where things get interesting.

The last two terms both represent N=5. One term is the chance of winning N=5 when you were last at N=4, and the other is winning N=5 when you jumped from N=3 straight to N=5.

There are two ways to get to N=5 and N=6.

There are three ways to get to N=7 and N=8.

4 ways to 9 and 10 and so on…

However, we can just carefully order our terms like so to get the answer…

1/2 +

1/4 * 1/2 + 1/8 * 1/2 * 1/2 + 1/16 * 1/2 * 1/2 * 1/2 + 1/32 * 1/2 * 1/2 * 1/2 * 1/2 … + (this represents the probability of winning after being at N-1)

1/16 * 1/4 * 1/2 + 1/32 * 1/4 * 1/2 * 1/2 + 1/64 * 1/4 * 1/2 * 1/2 * 1/2 … + (this represents the probability of winning after being at N-2)

1/64 * 1/8 * 1/2 * 1/2 + 1/128 * 1/8 * 1/2 * 1/2 +1/2 …+ (this represents the probability of winning after being at N-3)

…and so on. The important thing to note is that each of these longer lines is a geometric series which has a sum that we can compute.

That gives us…

1/2 +
1/8*(1 + 1/4 + 1/16 + 1/64…) +
1/128*(1 + 1/4 + 1/16 + 1/64…) +
1/2048*(1 + 1/4 + 1/16 + 1/64…) + …

The sum of the geometric series in parenthesis is 1/(1-1/4) or 4/3

Substitute this in and we get

1/2 +

1/8 * 4/3 + 1/128 * 4/3 + 1/2048 * 4/3 + …

This is also a geometric series. We can rewrite it as:

1/2 + 1/6*(1 + 1/16 + 1/256 + …)

The sum of the geometric series in parenthesis is 1/(1-1/16) or 16/15.

When we substitute this in we get.

1/2 + 1/6*(16/15) = 61/90

This is the exact answer.

22

My answer is wrong, but not by much.

Crap.

23

Okay, first, let’s be clear about the semantics about this problem, because I sense a great deal of confusion.

This isn’t trivial to understand, since there’s no such thing as an “infinite number of flips” in real life. The way to interpret this is

"What is limit of the probability that you will win the game for N = 2 in M flips or less as M grows without bound?"

Now we have a real, unambiguous math problem to solve. Let’s get on to the solution. I can corroborate that the answer does exist and that it is about

0.683315826347294179781643427691711670

(those decimal places are all correct). A general explicit formula (not in closed form) is:

P(N) = 1/(2[sup]2[sup]1[/sup][/sup]-2)((2[sup]2[sup]1[/sup][/sup]-1)/2sup(N-1)[/sup] - 1/(2[sup]2[sup]2[/sup][/sup]-2)((2[sup]2[sup]2[/sup][/sup]-1)/2sup(N-1)[/sup] - 1/(2[sup]2[sup]3[/sup][/sup]-2)((2[sup]2[sup]3[/sup][/sup]-1)/2sup(N-1)[/sup] - 1/(2[sup]2[sup]4[/sup][/sup]-2)((2[sup]2[sup]4[/sup][/sup]-1)/2sup(N-1)[/sup] - …))))

(if your browser doesn’t display nested superscripts, you’re out of luck!)

By expanding, this expression can be written as an infinite sum whose summand involves a finite product:

3/(2)/2sup[/sup] - 15/(142)/2[sup]3(N-1)[/sup] + 255/(254142)/2[sup]7(N-1)[/sup] - 65535/(65534254142)/2[sup]15(N-1)[/sup] + …

This expression converges extremely fast: the approximation above for N = 2 (correct to 36 decimal places) can be obtained using only the first 5 terms. Frankly, that expression is good enough for me, but if someone has a nontrivial simplification, I’d be really interested.

Here’s an outline of how I did it, replete with exercises for the reader ;):

I. Let P[sub]k/sub be the probability of winning the game for the given N in k flips or less, and let P(N) be the limit (if it exists) of P[sub]k/sub as k approaches infinity. We have the following relations:
[ul]
[li]P[sub]0/sub = 0[/li][li]P[sub]k/sub = 1/2[sup]N-1[/sup] + Sum from M = 1 to M = N-1 of (P[sub]k-1/sub/2[sup]M[/sup])[/li][/ul]

II. Now we observe that for each k, P[sub]k/sub has the form

c[sub]k,1[/sub]/2sup(N-1)[/sup] + c[sub]k,2[/sub]/2sup(N-1)[/sup] + … + c[sub]k,k[/sub]/2sup(N-1)[/sup]

where the c’s are all constant. This is easy to prove using mathematical induction, the recurrence formulas of I, and the summation of finite geometric series.

III. By using the recurrence relations of I and induction, we find that actually
[ul]
[li]c[sub]1,1[/sub] = 1[/li][li]c[sub]k,k[/sub] = -c[sub]k-1,k-1[/sub]/(2[sup]2[sup]k-1[/sup][/sup]-1) (for k > 1)[/li][li]c[sub]k,1[/sub] = 1 + c[sub]k-1,1[/sub]/3 (for k > 1)[/li][li]c[sub]k,j[/sub] = c[sub]k-1,j[/sub]/(2[sup]2[sup]j[/sup][/sup]-1) - c[sub]k-1,j-1[/sub]/(2[sup]2[sup]j-1[/sup][/sup]-1) (for k > 1, j > k)[/li][/ul]
Let a[sub]j[/sub] be the limit of c[sub]k,j[/sub] as k approaches infinity (if it exists). It isn’t completely obvious, but with a bit of analysis, the above actually implies that
[ul]
[li]a[sub]1[/sub] = 3/2[/li][li]a[sub]j[/sub] = -a[sub]j-1/sub/((2[sup]2[sup]j[/sup][/sup]-2)(2[sup]2[sup]j-1[/sup][/sup]-1)[/li][/ul]
This lets us find a[sub]j[/sub] explicitly once we know a[sub]j-1[/sub], and solving this recurrence gives us that a[sub]j[/sub] is

(-1)[sup]j+1/sup/(Product from i = 1 to i = j of (2[sup]2[sup]i[/sup][/sup]-2))

IV. Now we want to be able to say that

lim[sub]k->oo[/sub]P[sub]k/sub = Sum from j = 0 to infinity of a[sub]j[/sub]/2sup(N-1)[/sup]

The statement is true, but justifying it requires a uniform convergence argument that I won’t state here :wink: So now we have an explicit formula as an infinite sum for lim[sub]k->oo[/sub]P[sub]k/sub, which is P(N). This gives us the expressions I wrote above.

24

That should be “rounds,” not “flips,” as rounds are defined in panamajack’s post above.

25

Maybe I’m missing something, but I think the correct answer is zero. You’ll never win where N is 2 (or any higher number).

Consider the implications of this rule as it’s written: “If you flip some sequence of heads in a row that is fewer than N, you increase N by the length of that sequence, and start over.”

So if everytime you get a head, you’ve created a sequence of one head in a row. One is less than two, so you now increase N by one and start over. In other words, N is increasing one step ahead of whatever amount of heads you get.

26

I guess that’s one way of interpreting the question, but it’s probably the least interesting one. When a problem is stated ambiguously, I go by the “most interesting interpretation” principle, reasoning that the most interesting interpretation is probably the intended one. I think the most interesting interpretation here is the one posted by Ringo way up there.

27

Damn, you’ve beaten me to it.

Ah well, this is why I hate [strike]sadistics[/strike] probability theory. It’s all just measures anyhow…

28

Thanks to everyone who thought about this problem… a few clarifications:

(1) no, this is not homework of any sort. It’s just an interesting question that came up, actually in regards to a situation in a game of Magic: The Gathering

(2) the interpretation that most folks have made is the correct one… once you start flipping a sequene of heads, you keep going until you either (i) get N heads and win, or (ii) get a tail, at which point N increases
As for what the answer is, The Weak Force sure seems to know what he’s talking about…

29

Do you mean flips or trials?
At first instance of TTHT does that stop the trial and add 1 to required number of heads to win?

The problem does not seem to be explicitly stated and/or explained for clarity.

30

Given this interpretation, your answer is correct. But, I disagree with this interpretation. There are situations where doing something an infinite number of times gives a different result than doing it a finite (but arbitrarily large) number of times. Think of it as a discontinuity at infinity.

I analyzed this in terms of Kolmogorov’s zero-one law, which states that the probability of a tail event occurring is either zero or one.

(Disclaimer: I’ve been trying to figure this out and I may be misusing said law. There is an interesting discussion of it at the end of this page, in the section labeled “tail events”)

First, I re-define the game like this: in round X, flip N*2^X coins. If they all come up heads, you win that round, otherwise you lose that round. Note that the probability of winning in this game in round X is lower than the probability of winning the original game (although you will flip more coins), since the number of coins to flip at most doubles in each round.

The question now becomes “What is the probability that you eventually win?”

Let W be the probability of winning this new game in round X. P(W) = 1 / 2^(N * 2^X). Clearly this is greater than zero.

Let E be the event that you win in round X or later. E is a tail event. P(E) is the probability that you eventually win.

By the zero-one law, P(E) is either zero or one. But P(E) is clearly greater than zero since for all X, P(W) > 0 and P(E) >= P(W)

Therefore, P(E) = 1. You will almost surely eventually win this new game if you play an infinite number of rounds.

Let W0 be the probability of winning the original game in round X, with the additional rule that if you win in round X, you play again with the same number of coins in round X+1. Clearly, for all X, W0 >= W. So, since the probability of winning the new game is less than or equal to the probability of winning the original game, the probability of winning the original game is 1 as well.

31

Ok, now you have to tell us what cards brought this situation about.

I’m guessing Fungusaur + Pariah + some way of infinitely casting Mana clash. Am I close?

32

This thread is 18 months old. Let it die.