wu :: forums - Coin tossing: no two consecutive heads

wu :: forums « wu :: forums - Coin tossing: no two consecutive heads » Welcome, Guest. Please Login or Register. Apr 29^th, 2024, 1:00am
RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

   wu :: forums
   riddles
   easy (Moderators: towr, Grimbal, Eigenray, Icarus, ThudnBlunder, SMQ, william wu)
   Coin tossing: no two consecutive heads

« Previous topic | Next topic »

Pages: 1

Notify of replies

Send Topic

Author

Topic: Coin tossing: no two consecutive heads (Read 8791 times)

NickH
Senior Riddler

Gender:

Posts: 341

Coin tossing: no two consecutive heads
« on: Jan 22^nd, 2003, 6:40pm »

Quote

Modify

An unbiased coin is tossed n times. What is the probability that no two consecutive heads appear?

IP Logged

Nick's Mathematical Puzzles

RexJacobus
Newbie

Gender:

Posts: 14

Re: Coin tossing: no two consecutive heads
« Reply #1 on: Jan 23^rd, 2003, 6:37am »

Quote

Modify

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

IP Logged

NickH
Senior Riddler

Gender:

Posts: 341

Re: Coin tossing: no two consecutive heads
« Reply #2 on: Jan 23^rd, 2003, 9:36am »

Quote

Modify

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_sug gestions;action=display;num=1043138466

Does the pattern you have noted continue?

IP Logged

Nick's Mathematical Puzzles

wowbagger
Uberpuzzler

Gender:

Posts: 727

Re: Coin tossing: no two consecutive heads
« Reply #3 on: Jan 23^rd, 2003, 9:43am »

Quote

Modify

First of all, here's my answer: p_n = 3/4 - n2^-n

I arrived at it by the recurrence relation RexJacobus mentioned. You can find a closed form expression for p_n 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.

IP Logged

"You're a jerk, <your surname>!"

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender: male

Posts: 13730

Re: Coin tossing: no two consecutive heads
« Reply #4 on: Jan 23^rd, 2003, 10:17am »

Quote

Modify

on Jan 23^rd, 2003, 9:43am, wowbagger wrote:

First of all, here's my answer: p_n = 3/4 - n2^-n

is p_n is the chance of not getting consecutive head, you'd expect p_n 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)..

« Last Edit: Jan 23^rd, 2003, 10:21am by towr »

IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB

wowbagger
Uberpuzzler

Gender:

Posts: 727

Re: Coin tossing: no two consecutive heads
« Reply #5 on: Jan 23^rd, 2003, 10:26am »

Quote

Modify

on Jan 23^rd, 2003, 10:17am, towr wrote:

is p_n is the chance of not getting consecutive head, you'd expect p_n 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 p_n = n/2ⁿ+1/4 then.

IP Logged

"You're a jerk, <your surname>!"

NickH
Senior Riddler

Gender:

Posts: 341

Re: Coin tossing: no two consecutive heads
« Reply #6 on: Jan 23^rd, 2003, 10:26am »

Quote

Modify

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

« Last Edit: Jan 23^rd, 2003, 10:29am by NickH »

IP Logged

Nick's Mathematical Puzzles

wowbagger
Uberpuzzler

Gender:

Posts: 727

Re: Coin tossing: no two consecutive heads
« Reply #7 on: Jan 23^rd, 2003, 10:45am »

Quote

Modify

Well, looks like my little formula does not give the same result as the brute force approach. Sad

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

I hope at least the asymptotic behaviour is correct...

IP Logged

"You're a jerk, <your surname>!"

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender: male

Posts: 13730

Re: Coin tossing: no two consecutive heads
« Reply #8 on: Jan 23^rd, 2003, 10:57am »

Quote

Modify

let's make ph_n the chance of getting n coins without consecutive heads and ending on heads, and pt_n the chance of getting n coins without consecutive heads and ending on tails.

ph₁=1/2
pt₁=1/2
ph_n= 1/2 * pt_n-1
pt_n= 1/2 * pt_n-1 + 1/2 * ph_n-1

then of course p_n = pt_n + ph_n

« Last Edit: Jan 23^rd, 2003, 10:59am by towr »

IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender: male

Posts: 13730

Re: Coin tossing: no two consecutive heads
« Reply #9 on: Jan 23^rd, 2003, 11:07am »

Quote

Modify

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)

« Last Edit: Jan 23^rd, 2003, 11:11am by towr »

IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender: male

Posts: 13730

Re: Coin tossing: no two consecutive heads
« Reply #10 on: Jan 23^rd, 2003, 11:47am »

Quote

Modify

at long last..

$\frac{1}{2^n}\sum_{m=0}^{\lfloor\frac{(n+1)}{2}\rfloor}\left(\begin{array}{c}n-m+1\\m\\\end{array}\right)$

IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender: male

Posts: 13730

Re: Coin tossing: no two consecutive heads
« Reply #11 on: Jan 23^rd, 2003, 12:09pm »

Quote

Modify

also it's fib(n+2)/2^n (granted, I lack proof, but it seems to be so nonetheless)
so,
$\frac{4(\frac{1+\sqrt{5}}{4})^{n + 2}-4(\frac{1-\sqrt{5}}{4})^{n + 2}}{\sqrt{5}}$

IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB

RexJacobus
Newbie

Gender:

Posts: 14

Re: Coin tossing: no two consecutive heads
« Reply #12 on: Jan 24^th, 2003, 1:41am »

Quote

Modify

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

IP Logged

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender: male

Posts: 13730

Re: Coin tossing: no two consecutive heads
« Reply #13 on: Jan 24^th, 2003, 7:21am »

Quote

Modify

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)

IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB

SWF
Uberpuzzler

Posts: 879

Re: Coin tossing: no two consecutive heads
« Reply #14 on: Jan 24^th, 2003, 6:03pm »

Quote

Modify

That is cool that the Fibonacci sequence comes out of this. Knowing that makes it easier to prove what the probablity is.

Let H_n be the number of acceptable (not two heads in a row) permuations of n flips with heads on the final flip. Let T_n 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 H_n+1=T_n.

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 T_n+1=T_n+H_n. By the result of previous paragraph this reduces to: T_n+1=T_n+T_n-1.

The results of the last two paragraphs give: H_n+1=T_n=T_n-1+T_n-2
=H_n+H_n-1.

By listing the possibilities, H₁=1 and H₂=1. With the recurrance relation above, this means H is the Fibonacci sequence: H_n=F_n. It also means T_n=F_n+1.

Total number of acceptalbe permuations of n flips is T_n+H_n=F_n+1+F_n=F_n+2. Probability is this divided by 2ⁿ, which is exactly the form towr inferred.

IP Logged