Re: probability puzzle

Brian Tung <brian@xxxxxxx> wrote:
A machine starts flipping a fair coin. It halts after 2n flips if and
only if the last n flips were all heads. Otherwise, it continues
flipping. For example, each of these would be complete flipping
sequences:

HH
TH
HTHH
HTTHHH
TTHTHHTHHHHHHH

What is the probability that the machine eventually halts?

More seriously:

I don't have a closed formula for the probability, but I do have a
Python program which I believe to be calculating it correctly to at
least 600 decimal places. The probability is 0.683315826347294...
which appears to be a decimal expansion not previously known to
Google or OEIS. Derivation follows.

It is tempting to sum the probabilities of termination at each n and
get 1/2 + 1/4 + 1/8 + 1/16 + ... = 1. However, this is clearly
flawed because those probabilities are not mutually exclusive: an
infinite sequence of flips can very well satisfy more than one of
the terminating conditions and hence be counted more than once by
the above sum.

Instead, I propose a method of analysis where, after every pair of
flips, we count the length of the _trailing sequence_ of heads. This
gives us a Markov model: each successive pair of flips has a 1/2
probability (HT, TT) of reducing the trailing head sequence to
length zero, a 1/4 probability (TH) of reducing it to one, and a 1/4
probability (HH) of increasing it by two. We then render this model
non-Markov by placing an absorbing state at position n during the
nth turn (violating the Markov condition that the transition
probabilities never change).

I generally find it easier, in fact, to count combinatorially rather
than probabilistically: so in fact my program will be counting the
_number of 2n-flip sequences_ with the property that after those 2n
flips either
- the game has terminated at some point
or
- it has not, and there is a trailing sequence of exactly i heads,
for 0 <= i < n.

I store these counts in an array a[], with a[i] (0 <= i < n) giving
the probability of a trailing sequence of exactly i heads, and a[n]
giving the probability of having terminated after 2n flips.

So we begin with the boundary case n=1: the number of 2-flip
sequences after which we terminate is 2 (HH, TH), and the number
after which we have a trailing head sequence of length zero is 2
(HT, TT). Hence our array is [2,2].

Thereafter, we transform the array as follows:

We count up the total number K of _non_-terminating cases (that is,
the sum of all elements of a except a[n], or equivalently 4^n-a[n]).
Each of those sequences, if the next two flips are TT or HT, will
produce a 0-head trailing sequence; each if followed by TH will
produce a 1-head sequence. Thus a[0] = 2*K, a[1] = K.

The only way to produce a trailing sequence of exactly i heads, for
2 <= i < n, is to start with a trailing sequence of exactly i-2 and
to flip HH. Thus, the new value of a[i] is equal to the old value of
a[i-2].

Finally, the number of termination cases is equal to the number of
prior cases in which the trailing sequence was at least n-2 (so that
it's now at least n), plus _four times_ the number of prior cases in
which the game had already terminated (because we're notionally
still flipping coins even if the machine has reported success, since
we need to keep all our cases equiprobable).

So the snippet of Python that implements these rules is as follows:

#!/usr/bin/env python
a = [2,2]
n = 1
total = 4
while 1:
K = total - a[n]
a = [K*2, K] + a[:n-1] + [a[n-1] + 4*a[n]]
n = n + 1
total = total * 4
assert sum(a) == total
print "0.%0600d" % (a[n]*10**600 / total)

And if you run it, it will visibly and rapidly converge to the
probability I quote above.

I don't have a proof that the probability does converge, or an
analytic derivation or closed formula for its limit; but the
numerical behaviour seems pretty clear from that demonstration.

(Note, incidentally, that no _approximate_ arithmetic whatsoever is
taking place in the above program, apart from the rounding to 600
decimal places on output. All the data propagated from iteration to
iteration is exact integer data, so there is no _cumulative_ error.)
--
Simon Tatham "Happiness is having a large, warm, loving,
<anakin@xxxxxxxxx> caring, close-knit family in another city."
.

Relevant Pages

  • Re: Linfords Fallacy
    ... it is not true that the probability of having all ... heads is the same as the probability as having any mixture of heads and ... or tails than there are series of coin flips with only heads. ... It is true that the probabiliy of any sequence is the same ...
    (sci.math)
  • Re: Linfords Fallacy
    ... He is comparing apples to apples and your comparing oranges ... He is talking about sequences of all heads or all tails verses sequences ... sequence to any other sequence. ... probability and the other has a very low probability. ...
    (sci.math)
  • Re: The Philosophy of War
    ... even one day in a class that covers probability theory to any extent. ... actual coin not being an exactly fair coin. ... The probability, in two coin flips, of getting exactly one head and one ... The probability of getting exactly two heads in four flips is 37.5% ...
    (rec.martial-arts)
  • Re: The last ancestor of all life
    ... what is the probability of flipping a quarter and landing ... What is the probability of flipping a quarter having heads on the ... Any specific sequence of heads and tails will have the same odds. ...
    (talk.origins)
  • Re: coin flips and prime number theory
    ... As I interpret your question, ... is the probability of ever seeing 100 heads in a row ... flips 1-100, or seeing a tail followed by 100 ...
    (sci.math)