Probability Problem - Coin Tossing

[The Investor]

Glad that it was useful for you Techmologist and thanks for the help. And thanks D H.

By the way, if you are interested in getting the average number of occurrences of a run of at least H heads in N tosses, there is a very simple formula for N≥H

[(N-H)*(0.5) +1] * [0.5^H]

For N=20 and H=5 This leads to
8.5*0.5^5There are 262008 combinations that contain a run of at least 5 heads in 20 tosses from a total of 2^20.
Within the full set of 2^20 possibilities, a run of at least 5 heads occurs 278528 times.

 

[EnumaElish]

You can use the following as an Excel template as long as number of throws < 20. To change the number of throws from 20 to (say) 19, ignore the last column and rows > 10^19.

In Excel 2007, enter 20 zeros on a row. Copy on to the next row (row 2), change 20th cell to "1" on row 2.

Copy the first two rows onto the next two rows (rows 3-4); on the new rows change the 19th column to 1's.

Copy the first four rows onto rows 5-8; on the new rows change the 18th column to 1's.
...
Copy the first 2^k rows onto rows (2^k)+1 thru 2^(k+1); on the new rows change the (20 - k)th column to 1's. Stop at k = 20.

On the next column (e.g. col. 21), sum columns 1-5. On col. 22, sum cols. 2-6. ... On col. 36, sum cols. 16-20. On these columns you should see natural numbers less than or equal to 5.

On col. 37 first row enter =MATCH(5,u1:aj1,0)

(The expression "u1:aj1" denotes columns 21-36 if I am not mistaken.) Copy this formula all the way down. You should see lots of cells with the #N/A error message, with some interspersed integers.

On col. 38 enter =IF(ISNUMBER(AK1),1,0)

(The expression "AK1" denotes column 37 assuming I was right about u1:aj1.) Copy this formula all the way down. Each #N/A on the previous column should correspond to a zero on this column.

Anywhere on the worksheet, calculate the sum of column 38, then divide by 2^20.

 

[techmologist]

By the way, if you are interested in getting the average number of occurrences of a run of at least H heads in N tosses, there is a very simple formula for N≥H

[(N-H)*(0.5) +1] * [0.5^H]

That is surprisingly simple. Can you tell us how to get that?

 

[The Investor]

Copy the first four rows onto rows 5-8; on the new rows change the 18th column to 1's.
...

On the next column (e.g. col. 21), sum columns 1-5. On col. 22, sum cols. 2-6. ... On col. 36, sum cols. 16-20. On these columns you should see natural numbers less than or equal to 5.

I don't see how that works. All the 1's add up to more than 5?

 

[The Investor]

That is surprisingly simple. Can you tell us how to get that?

Sure. The procedure is the same as in post 4, except that you don't have to worry about double counting, making things a lot easier.

Going back to excel, in cell A1 =0.5^H
The value in each cell below this would be exactly half of this, as the sequences is always 'one longer'. For instance, when looking at at least 5 consecutive heads in 20 tosses, we're interested in 0.5^5 (HHHHH) in cell A1 and 0.5^6 (THHHHH) in cells A2 -A16. The sum of A1-A16 is the average number of occurences.

You start with [0.5^H] . As the other values will always be exactly half of this, you simply count how many there are of the 'half values' (N-H=15), you multiply this by half because it is half as likely as [0.5^H], you then add one before multiplying the first part by [0.5^H] to get a correct weighting [(N-H)*(0.5) applies to cells 2-16 +1 adds cell one which is not multiplied by .5 because the value is 2x times as high]

I'm sure there is a much clearer way of putting it, hope it's ok though :)

 

[EnumaElish]

I don't see how that works. All the 1's add up to more than 5?

In this part I am adding 5 cells at a time. The downside with this is it will count a 6-run as two 5-runs.

 

[D H]

The algorithms in posts #4 and #13 are essentially the same algorithm, just looking at things in different ways. Neither counts a 6 run as two five runs.

 

[techmologist]

Sure. The procedure is the same as in post 4, except that you don't have to worry about double counting, making things a lot easier.

Going back to excel, in cell A1 =0.5^H
The value in each cell below this would be exactly half of this, as the sequences is always 'one longer'. For instance, when looking at at least 5 consecutive heads in 20 tosses, we're interested in 0.5^5 (HHHHH) in cell A1 and 0.5^6 (THHHHH) in cells A2 -A16. The sum of A1-A16 is the average number of occurences.

You start with [0.5^H] . As the other values will always be exactly half of this, you simply count how many there are of the 'half values' (N-H=15), you multiply this by half because it is half as likely as [0.5^H], you then add one before multiplying the first part by [0.5^H] to get a correct weighting [(N-H)*(0.5) applies to cells 2-16 +1 adds cell one which is not multiplied by .5 because the value is 2x times as high]

I'm sure there is a much clearer way of putting it, hope it's ok though :)

Oh, I see. Indicator random variables for the win! That counts a sequence like THHHHHHHHH as one run of at least 5 heads, if I understand correctly. Very nice. Thanks.

 

[scalpmaster]

http://www.bjmath.com/bjmath/probable/flips.htm
http://en.wikipedia.org/wiki/Feller's_coin-tossing_constants

In the above 2 links, it's mentioned that if we toss a fair coin ten times then the exact probability that NO pair of heads come up in succession (i.e. n = 10 and k = 2) is p(10,2)= 0.140625.

Therefore, conceptually, the probability of at least 2 consecutive heads coming up in 10 coin tosses = 1-0.14 = 0.86. Will a spreadsheet simulation show roughly the same probability 0.86 after many 10tosses intervals range run?

Let 1 cycle= at least 2 consecutive heads coming up at least once in 10 coin tosses.
Is the probability of 4 cycles appearing consecutively = 0.86*0.86*0.86*0.86 = 0.54 ? Or how should it be calculated? If it is 0.54, does it mean that the probability of winning after winning 4 times in a row is reduced below 1/2?