wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Coin tossing: no two consecutive heads
        
(Message started by: NickH on Jan 22nd, 2003, 6:40pm)
Title: Coin tossing: no two consecutive heads
Post by NickH on Jan 22nd, 2003, 6:40pm
An unbiased coin is tossed n times. What is the probability that no two consecutive heads appear?
Title: Re: Coin tossing: no two consecutive heads
Post by RexJacobus on Jan 23rd, 2003, 6:37am
Off the top of my head I saw that if you flip two coins only 1 of the permutations is false.  From there I intuitively saw the following progression:  (I am newbie, forgive me if I should hide the following.  I looked in the FAQs but couldn't find out how you do that. )

If you double number of false permutations for and add n-1 then you would have the next number of false permutations.  ie 1 out of 4 false for 2 flips; 3 flips double the one and add n-1 = 3 out 8 false; double the 3 and add n-1 for 8 out 16 false.

Writing that progression out mathematically is proving to be a pain in the arse though.   I'm still working on that and my lunch hour is up.

Rex
Title: Re: Coin tossing: no two consecutive heads
Post by NickH on Jan 23rd, 2003, 9:36am
I don't think hiding text is compulsory, especially when you're posting exploratory working.  Here's the reference for hiding:

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_suggestions;action=display;num=1043138466

Does the pattern you have noted continue?
Title: Re: Coin tossing: no two consecutive heads
Post by wowbagger on Jan 23rd, 2003, 9:43am
First of all, here's my answer: pn = [hide]3/4 - n2-n[/hide]

I arrived at it by the recurrence relation RexJacobus mentioned. You can find a closed form expression for pn if you look at the amount added when progressing from n to n+1. After that it's all about not getting consufed by all these 2s and ns.

It's a nice little practice to work it out by hand, I'd say.
Title: Re: Coin tossing: no two consecutive heads
Post by towr on Jan 23rd, 2003, 10:17am

on 01/23/03 at 09:43:12, wowbagger wrote:
First of all, here's my answer: pn = [hide]3/4 - n2-n[/hide]

is pn is the chance of not getting consecutive head, you'd expect pn to get smaller as n gets larger.. Your function does the opposite, it get's larger as n get's larger (than 1 / LN(2) ~= 1.44)..
Title: Re: Coin tossing: no two consecutive heads
Post by wowbagger on Jan 23rd, 2003, 10:26am

on 01/23/03 at 10:17:53, towr wrote:
is pn is the chance of not getting consecutive head, you'd expect pn to get smaller as n gets larger.. Your function does the opposite, it get's larger as n get's larger..

You're right, of course. I counted the wrong possible outcomes once again...
So the answer should be pn = [hide]n/2n+1/4[/hide] then.
Title: Re: Coin tossing: no two consecutive heads
Post by NickH on Jan 23rd, 2003, 10:26am
Here's a list of all the outcomes for 6 coins, with no consecutive heads in red.  There are only 21 such outcomes...

HHHHHH, HHHHHT, HHHHTH, HHHHTT, HHHTHH, HHHTHT, HHHTTH, HHHTTT, HHTHHH, HHTHHT, HHTHTH, HHTHTT, HHTTHH, HHTTHT, HHTTTH, HHTTTT, HTHHHH, HTHHHT, HTHHTH, HTHHTT, HTHTHH, HTHTHT, HTHTTH, HTHTTT, HTTHHH, HTTHHT, HTTHTH, HTTHTT, HTTTHH, HTTTHT, HTTTTH, HTTTTT, THHHHH, THHHHT, THHHTH, THHHTT, THHTHH, THHTHT, THHTTH, THHTTT, THTHHH, THTHHT, THTHTH, THTHTT, THTTHH, THTTHT, THTTTH, THTTTT, TTHHHH, TTHHHT, TTHHTH, TTHHTT, TTHTHH, TTHTHT, TTHTTH, TTHTTT, TTTHHH, TTTHHT, TTTHTH, TTTHTT, TTTTHH, TTTTHT, TTTTTH, TTTTTT
Title: Re: Coin tossing: no two consecutive heads
Post by wowbagger on Jan 23rd, 2003, 10:45am
Well, looks like my little formula does not give the same result as the brute force approach. :(

However, the error is below 5% in this case. ;)

I hope at least the asymptotic behaviour is correct...
Title: Re: Coin tossing: no two consecutive heads
Post by towr on Jan 23rd, 2003, 10:57am
let's make phn the chance of getting n coins without consecutive heads and ending on heads, and ptn the chance of getting n coins without consecutive heads and ending on tails.

ph1=1/2
pt1=1/2
phn= 1/2 * ptn-1
ptn= 1/2 * ptn-1 + 1/2 * phn-1

then of course pn = ptn + phn
Title: Re: Coin tossing: no two consecutive heads
Post by towr on Jan 23rd, 2003, 11:07am
hmm..  any valid sequence will be of the form
T*(HT+)*(H?)T*
the maximum number of H in n coinflips, will be (n+1) div 2. And given m H, you just need to distribute the remaining n-2m+1 (given m heads, you need m-1 tails to seperated them) tails between the heads, m+1 bins..
Of course I don't remember how to do that, but I've seen William do it somewhere else.. (just can't remember where)
Title: Re: Coin tossing: no two consecutive heads
Post by towr on Jan 23rd, 2003, 11:47am
at long last..

http://tcw2.ppsw.rug.nl/~towr/PHP/formula.php?formula=%5Cfrac%7B1%7D%7B2%5En%7D%5Csum_%7Bm%3D0%7D%5E%7B%5Clfloor%5Cfrac%7B%28n%2B1%29%7D%7B2%7D%5Crfloor%7D%5Cleft%28%5Cbegin%7Barray%7D%7Bc%7Dn-m%2B1%5C%5Cm%5C%5C%5Cend%7Barray%7D%5Cright%29%0D%0A
Title: Re: Coin tossing: no two consecutive heads
Post by towr on Jan 23rd, 2003, 12:09pm
also it's fib(n+2)/2^n (granted, I lack proof, but it seems to be so nonetheless)
so,
http://tcw2.ppsw.rug.nl/~towr/PHP/formula.php?formula=%5Cfrac%7B4%28%5Cfrac%7B1%2B%5Csqrt%7B5%7D%7D%7B4%7D%29%5E%7Bn+%2B+2%7D-4%28%5Cfrac%7B1-%5Csqrt%7B5%7D%7D%7B4%7D%29%5E%7Bn+%2B+2%7D%7D%7B%5Csqrt%7B5%7D%7D%0D%0A
Title: Re: Coin tossing: no two consecutive heads
Post by RexJacobus on Jan 24th, 2003, 1:41am
I am more of a verbal intuiter who is okay with numbers than a true math bod.  Is  (n+2)/2^n  the definition of a fibonacci sequence?

In the end I came up with

2(2^n + (2^(n-1) – 2)) – 2(n-1) /  2^(n+2)

Rex
Title: Re: Coin tossing: no two consecutive heads
Post by towr on Jan 24th, 2003, 7:21am
fibonacci sequence:
fib(0)=0
fib(1)=1
fib(n)=fib(n-1)+fib(n-2)

which is equal to (((1+sqrt5)/2)^n - ((1-sqrt5)/2)^n)/sqrt(5)
Title: Re: Coin tossing: no two consecutive heads
Post by SWF on Jan 24th, 2003, 6:03pm
That is cool that the Fibonacci sequence comes out of this. Knowing that makes it easier to prove what the probablity is.

Let Hn be the number of acceptable (not two heads in a row) permuations of n flips with heads on the final flip. Let Tn be the number of acceptable permutations of n flips with tails on the final flip.

Any sequence of n acceptable flips ending in tails can be turned in an acceptable sequence of n+1 flips ending in heads, by appending heads to the end of the sequence. This also gives every possible acceptable sequence of n+1 ending in heads, so Hn+1=Tn.

Any sequence of n acceptable flips can be turned in an acceptable sequence of n+1 flips ending in tails, by appending tails to the end of the sequence. So Tn+1=Tn+Hn. By the result of previous paragraph this reduces to: Tn+1=Tn+Tn-1.

The results of the last two paragraphs give: Hn+1=Tn=Tn-1+Tn-2
=Hn+Hn-1.

By listing the possibilities, H1=1 and H2=1. With the recurrance relation above, this means H is the Fibonacci sequence: Hn=Fn. It also means Tn=Fn+1.

Total number of acceptalbe permuations of n flips is Tn+Hn=Fn+1+Fn=Fn+2. Probability is this divided by 2n, which is exactly the form towr inferred.
Title: Re: Coin tossing: no two consecutive heads
Post by NickH on Jan 25th, 2003, 7:55am
It is cool that the Fibonacci sequence is involved!

See the solution (http://www.qbyte.org/puzzles/p040s.html) at my puzzle site for an alternative derivation.
Title: Re: Coin tossing: no two consecutive heads
Post by william wu on Jan 27th, 2003, 9:13pm
Those are some nice solution write-ups Nick!


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board