Math Is Fun Forum

mpthomas

Member

Registered: 2007-07-27

Posts: 7

Tough one...

A: You throw a coin multiple times. What's the average amount of throws required to obtain 2 heads in a row?

B: Starting at number zero, you throw a coin.
Tails means you go down one (therefore equalling -1)
Heads means you go up one (therefore equalling 1)

You repeat this procedure infinite times, so here's an example variation:
0, 1, 2, 3, 2, 3, 4, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 7.........

Question is: (b) - how many times on average would 0 have been 'hit' if you threw the coin 100 times? The highest possible answer is 50 (0, 1, 0, 1, 0, 1 etc.), and the lowest answer is 0 (many, many ways of getting this), but I want the /average/.

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Tough one...

For the second one, I know from a reputable source that tossing the coin N times will make you get to 0 an average of (√N)/3 times, not including the 0 that you started at. No proof though, sorry.

So, tossing the coin 100 times makes you get to zero around 10/3 times, on average.

Edit: On closer inspection, the book has a 'roughly' in there, so it's not an exact formula. It probably gets more accurate for higher N though, so I'd guess the value for 100 would be fairly good.

---

Why did the vector cross the road?
It wanted to be normal.

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Tough one...

A is quite interesting.

I started making lists of sequences of coin tosses that would fit that description, and Fibonacci has popped up.

2 [1]: HH
3 [1]: THH
4 [2]: HTHH, TTHH
5 [3]: HTTHH, THTHH, TTTHH
6 [5]: HTHTHH, HTTTHH, THTTHH, TTHTHH, TTTTHH
7 [8]: HTHTTHH, HTTHTHH, HTTTTHH, THTHTHH, THTTTHH, TTHTTHH, TTTHTHH, TTTTTHH

...and so on.

The chance of each individual sequence happening is 2^(-n), where n is the amount of tosses in the sequence.

That means that the chance of you needing exactly n throws before getting 2 heads is [(n-1)th Fibonacci number] * 2^(-n).

That in turn means that your final answer is this beastly thing (where Φ is the Golden Ratio):

Using Excel, that seems to converge to 6.
Sorry for the horribly complex method, but at least it gets an answer. Maybe someone else will come along with a much easier way.

---

Why did the vector cross the road?
It wanted to be normal.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Tough one...

My simulation is showing a convergence to 2.5.

CoinToss[] := (r = 2; previous = Random[Integer, {0, 1}]; current = \
Random[Integer, {0, 1}];  While[previous ≠ 1 && 
    current ≠ 1, r++; previous = current; current = Random[Integer, {0, 1}]]; \
Return[r])

sum = 0; Do[sum += CoinToss[], {i, 0, 100000}]; sum/100000.0

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Tough one...

I don't understand coding, but the answer it's given should be intuitively wrong.

The only way of doing it with 2 tosses is HH, which has a 1/4 chance.
The only way of doing it with 3 tosses is THH, which has a 1/8 chance.
That leaves a 5/8 chance of needing at least 4 tosses.

That means that the answer is at least 2*1/4 + 3*1/8 + 4*5/8 = 3.375.

---

Why did the vector cross the road?
It wanted to be normal.

krassi_holmz

Real Member

Registered: 2005-12-02

Posts: 1,905

Re: Tough one...

My simulation is showing a convergence to 2.5.

CoinToss[] := (r = 2; previous = Random[Integer, {0, 1}]; current = \
Random[Integer, {0, 1}];  While[previous ≠ 1 && 
    current ≠ 1, r++; previous = current; current = Random[Integer, {0, 1}]]; \
Return[r])

sum = 0; Do[sum += CoinToss[], {i, 0, 100000}]; sum/100000.0

OOh! MAthematica code!
Thats fine!
You are the first person I see writing Mathematica code except me
The problem is interesting, but I thing something simular had been posted before...
mathsy is on the right track, but he must have mistake somewhere...
[EDIT]Sorry mathsy, you're right, I'm wrong! (again)
I got answer 6 in interesting way, I'll post it.
to Ricky - what a mistake! It sertiantly is not easy-recognisible, but here is it:
----
While[previous ≠ 1 &&
    current ≠ 1,
-----
This should not be AND, this should be OR!
Now:

CoinToss[] := (r = 2; previous = Random[Integer, {0, 1}]; current = \
Random[Integer, {0, 1}];  While[previous ≠ 1 ||
    current ≠ 1, r++; previous = current; current = Random[Integer, {0, 1}]]; \
Return[r])

sum = 0; Do[sum += CoinToss[], {i, 0, 100000}]; sum/100000.0

which works just fine. And it gives 6!

Last edited by krassi_holmz (2007-08-02 10:57:19)

---

IPBLE:  Increasing Performance By Lowering Expectations.

krassi_holmz

Real Member

Registered: 2005-12-02

Posts: 1,905

Re: Tough one...

Now here is my really simple argument:
OK. Call the average amount of trows P.
Now look at this:

    +-->H X
+-->H
|   +-->T
0
|
+-->T

this is the beginning of the graph for our possible first cases - begins at 0 then goes to H or T with probability 1/2, ect.
Now, here's my reasoning:
1) If at the first move you go to T (you throw tail), which happens with probability 1/2, then it's most likely to finish in P+1 steps (because you already made one and this case is exacly as in the beginning)
This adds

2) The other opportunity is to go to the H (throw heads), which happens again with probability 1/2. At this stage you have 2 cases:
2.1) to go to the next H, (probability 1/2) , and then the path you travel will end, and will be 2 steps long.
This adds

2.2) if you go to T, you are in the same positinon as in the beginning, but you have already traveled 2 steps, so this will add:

Since these are the only cases, the solution will satisfy:

Solving it gives

Cool and simple!

---

IPBLE:  Increasing Performance By Lowering Expectations.

krassi_holmz

Real Member

Registered: 2005-12-02

Posts: 1,905

Re: Tough one...

For the second question, direct computation gives 7:

F[] := (r = n = 0; 
  Do[n += 2 Random[Integer, {0, 1}] - 1; 
   If[n == 0, r++];, {i, 1, 100}]; Return[r];)
Mean[Table[F[],{i,1,10000}]]

---

IPBLE:  Increasing Performance By Lowering Expectations.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Tough one...

Good find Krassi.  I always did have trouble with boolean logic...

6 it is, nice work mathsy.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

krassi_holmz

Real Member

Registered: 2005-12-02

Posts: 1,905

Re: Tough one...

Now I understood my method can be used for harder problems. I give you this one:
You throw a dice multiple times. What's the average amonth of throws, required to obtain to consecutive equal numbers?
For example, one may have:
1 2 3 6 5 1 1 -> stop

I'm waiting for a solution...

---

IPBLE:  Increasing Performance By Lowering Expectations.

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Tough one...

Ah, ingenius. Much simpler than mine.

So if I've got this right, there's always a 1/6 chance of throwing the number that you just threw.
There's a 5/6 chance of going back to the beginning, and you being likely to need P+1 throws.

Therefore, the answer is found by P = 1/6 + 5(P+1)/6.

P/6 = 1
P = 6

And then add the first throw because it didn't have anything to match, giving the final answer as an average of 7.

---

Why did the vector cross the road?
It wanted to be normal.

krassi_holmz

Real Member

Registered: 2005-12-02

Posts: 1,905

Re: Tough one...

Exaactly!

---

IPBLE:  Increasing Performance By Lowering Expectations.

mpthomas

Member

Registered: 2007-07-27

Posts: 7

Re: Tough one...

So close...but so far away...

krassi_holmz

Real Member

Registered: 2005-12-02

Posts: 1,905

Re: Tough one...

So close...but so far away...

What do you mean?

---

IPBLE:  Increasing Performance By Lowering Expectations.