You’re playing a game. You have a positive integer N and a coin. You start flipping the coin. If you flip heads N times in a row, you win. 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 N is 4, and your flipping goes TTHHT, you flipped 2 heads, and now N is 6, and it’s much harder to win.
The question is, what is the probability, given an infinite number of flips, that you will eventually win the game if N = 2?
Oog, that’s a doozy of a problem. I’ll think about it over the course of the evening, but just to ge this out of the way: is this a homework problem? I need to know how cagey to be when I give a response. (Granted, I’m not sure I know how to solve this, but I’ll see what I can do…)
Actually given an unlimited number of attempts eventually you must succeed no probability just a definite conclusion. Probably yes or, probably no; however in this case we have a definite yes. The key is an infinite number of flips so keep going until you succeed.
Ok, been a long time, and the college stat classes are a distant memory, but here goes:
First, I am running under the assumption that with N=2, the only sequence that immediately results in an increassed N is a single “heads” surrounded by “tails” on either end, and that as soon as N “heads” have happened, the game is won. So HHTHHH is a win, since N=2 and two consecutive “heads” were given at the beginning. HTHH would require more flips of the coin, since the single H at the beginning would make n=3. HTHHH would be a win. If i am wrong about the assumption, then I don’t know.
It seems to me that your probability with x tosses of the coin permitted, approaches 0.5.
If x=2, then P(win)= 1/4
possible results:
HH
HT
TH
TT
only the first result of “HH” gives a win.
with x=3, P(win)= 3/8
x=4, P(win)= 7/16
x=5, P(win)= 15/32
If someone wants to confirm or reject that data, feel free.
As I read it, the OP never stipulates how many times you flip the coin. N is just how many sequential heads you’re looking for, so if N=2, HH is a win, as is THH or TTHH. If you flipped HHTHHH with an initial N=6, you’d have your N increase to N=8 as soon as you flipped the first T in that sequence.
I think.
NPR had a story in the last few days about coin flipping. While it’s often used to represent a random occurence with two possible outcomes, some researcher has claimed that, due to the actual mechanics of how people flip coins, you’re more likely to wind up with whatever was on top to begin with.[/aside]
The more I think about this, the more it doesn’t seem like a reasonable homework problem, so I’ll do what I can to help.
Here’s what I’ve got so far: let P(N) be the probability of winning the game for an integer N. The probability that your first string of heads is of length M is 1/2[sup]M-1[/sup]. (The number of tails you get before your first head doesn’t matter.) So the probability that your first string of heads will be of length N is 1/2[sup]N-1[/sup]; the probability that your first string of heads will be of length M < N, and that you subsequently win the new game with a string of N + M heads is P(N+M) / 2[sup]M-1[/sup]. Thus, the total probability for winning the game with an initial value of N is (summing over M)
This is a recursion relation, of sorts, and it does give the correct answer for the obvious case of P(1) = 1. However, the problem is that the equation for P(N) depends on P(N + 1), P(N+2), … P(2N - 1), so the higher you go the more terms you have to calculate. For example, we have
and so forth. Probably a competent computer programmer could whip up some code that would give a good approximation to P(2), but I don’t see an obvious way to get a nice closed form.
I think this is all correct, but feel free to take issue with any or all of the above statements.
I think Q.E.D and 12 parsecs from home are correct. Consider a infinite string consists of H’s and T’s, the member at each location is determined by flipping a coin. The question is, can you locate a run of T’s (or H’s) of arbitrary length somewhere in the string?
The answer seems to be yes, although I can’t prove it.
Lance Turbo answered p=0.678 to win and independently, utilizing Monte Carlo simulation (103,000), answered p=0.684 to win. What’s the issue here, the language or the probabilty?
You simply can’t assume that because you have an infinite number of attempts you must eventually succeed, nor that the probability = 1. In the strictest sense those two things are not equal using traditional probability theory, so the phrase, “given an unlimited number of attempts eventually you must succeed…” would be wrong.
Consider the sequence TTTT…
It’s allowed by the rules, contains no heads, and you won’t win. Again, this doesn’t mean the probabilty of winning is less than 1 (this one, like any infinite sequence, has probabilty 0 of occurring). Even if you get an infinite number of heads you won’t necessarily win. (THTHTHTHTH…)
Still, it seems highly likely that the probabilty will be 1 (and it should not matter what N you start with). I think MikeS has the best statement of it, but it’d be nice to have a closed form for M finite ‘rounds’ (where a round begins with one head and ends with a tail.)
SwingWing & Lance Turbo, what formulation are you using to get those answers?
You missed something. Every time you flip a tail, the N value rquired to win increases by the H-run length just completed.
So, assuming your infinite string reads from left to right, for any particular run of Hs to be a winner, it must be longer than the original N plus the sum of all H-runs to the left of it.
So simply finding an H-sequence of arbitrary length somewhere in the infinite string isn’t good enough.
My take:
So the question becomes which grows faster, the N or the probablility of achieving the ever-growing N-in-a-row?
My qualitative approach is that as N increases the probability of N-in-a-row decreases (= 1/2 ^ (N-1) as MikeS said.) IOW, it’s monotonically decreasing (exponentially in fact).
Meanwhile, the likelihoood that N is increasing is essentially 1. The actual N-function is a monotonically increasing function, incrementing by the length of each H-run every time you throw a tail.
So they diverge from their simple beginnings where N=2.
As an approximation we can compute the first few terms and ignore the rest since they’re rapidly going to converge on zero.
As a practical matter when playing the game, yuo’ll win a couple at N=2. If you don’t win and N gets up to 4, quit now because you’ll waste the rest of the week, and more likely the rest of your life, continuing to try to win that round.
I tried to solve the equations set up by MikeS. As he has already pointed out, P(N) = 1 for all N is a solution. However, I think the case where you repeatedly have near misses in the number of heads so N grows and grows and you never win has a probability greater than 0 (as you guessed, panamajack, but showing single cases where this happens is no proof since the probability of every single case is 0 - nor do I have a proof), so I looked into a different solution.
Obviously, the sequence P(N) must converge to 0 for N growing to infinity in order to fulfill the equations. Therefore we can approximate the solution by setting all P(N) = 0 for N greater than a certain bound and solving the equation for the remaining finite number of variables.
This is quite straightforward (the equation system is a triangular matrix):
Let P(N) = 0 for all N > M
–> P(M-1) = 1/2[sup]M-2[/sup] (all further parts of the equation are 0)
–> P(M-2) = 1/2[sup]M-3[/sup] + 1/2 * P(M-1)
…
The following VBScript does just that (set the parameter iMax to fine tune the level of approximation):
Option Explicit
Call Main()
Sub Main()
Dim iMax, i, j
Dim p, d1, d2
Dim sResult
iMax = 1000
p = Array()
ReDim p(iMax)
d1 = 2
For i = 3 To iMax
d1 = d1 * 2
Next
sResult = ""
For i = iMax To 2 Step -1
p(i) = 1 / d1
d1 = d1 / 2
d2 = 2
For j = 1 To i-1
If i+j > iMax Then Exit For
p(i) = p(i) + p(i+j) / d2
d2 = d2 * 2
Next
sResult = sResult & i & ": " & p(i) & vbCRLF
Next
Call MsgBox(p(2) & vbCRLF & vbCRLF & sResult)
End Sub
I take the view the OP meant to stop a turn immediately after a T appears after any number of H. If my view is correct, then I don’t think the probability is 1.
The probability if N increments by one is the series:
1/2 + 1/4 + 1/8. . . . .
That series does equal 1, but the appearance of any term after the second is not assured, so the sum must be less than one.
(Granted, I’m not sure I know how to solve this, but I’ll see what I can do…)