CODEWITHSUNDEEP
pythonpython-2.7meancoin-flipping
Alessandro Gravellini
Alessandro Gravellini

Reputation: 19

Longest expected head streak in 200 coinflips

I was trying to calculate the expected value for the longest consecutive heads streak in 200 coin flips, using python. I came up with a code which I think does the job right but it's just not efficient because of the amount of calculations and data storage it requires, and I was wondering if someone could help me out with this, making it faster and more efficient (I took only one course of python programming in last semester without any previous knowledge of the subject).

My code was

import numpy as np
from itertools import permutations

counter = 0
sett = 0
rle = []

matrix = np.zeros(200)

for i in range (0,200):
    matrix[i] = 1
    for j in permutations(matrix):
        for k in j:
            if k == 1:
               counter += 1
            else:
               if counter > sett:
                  sett == counter
               counter == 0
        rle.append(sett)

After finding rle, I'd iterate over it to get how many streaks of which length there are, and their sum divided by 2^200 would give me the expected value I'm looking for.

Thanks in advance for help, much appreciated!

Upvotes: 0

Views: 1630

Answers (2)

frederick99
frederick99

Reputation: 1053

This is an answer to a slightly different question. But, as I had invested an hour and half of my time into it, I didn't wanna scrape it off.

Let E(k) denote a k head streak, i.e., you get k consecutive heads from the first toss onwards.

E(0): T { another 199 tosses that we do not care about }
E(1): H T { another 198 tosses... }
.
.
E(198): { 198 heads } T H
E(199): { 199 heads } T
E(200): { 200 heads }

Note that P(0) = 0.5, which is P(tails in first toss)
whereas P(1) = 0.25 , i.e., P(heads in first toss and tails in the second)

P(0) = 2**-1
P(1) = 2**-2
.
.
.
P(198) = 2**-199
P(199) = 2**-200
P(200) = 2**-200    #same as P(199)

Which means if you toss a coin 2**200 times, you'd get

E(0) 2**199 times
E(1) 2**198 times
.
.
E(198) 2**1 times
E(199) 2**0 times and
E(200) 2**0 times.

Thus, the expected value reduces to

(0*(2**199) + 1*(2**198) + 2*(2**197) + ... + 198*(2**1) + 199*(2**0) + 200*(2**0))/2**200

This number is virtually equal to 1.

Expected_value = 1 - 2**-200

How I got the difference.

>>> diff = 2**200 - sum([ k*(2**(199-k)) for k in range(200)], 200*(2**0))
>>> diff
1

This can be generalized to n tosses as

f(n) = 1 - 2**(-n)

Upvotes: 0

Robert Eckhaus
Robert Eckhaus

Reputation: 161

You don't have to try all the permutations (in fact you cannot), but you can do a simple Monte Carlo style simulation. Repeat the 200 coin flips many times. Average the lengths of longest streaks you get and this will be a good approximation of the expected value.

def oneTrial (noOfCoinFlips):
    s = numpy.random.binomial(1, 0.5, noOfCoinFlips)
    maxCount = 0
    count = 0
    for x in s:
        if x == 1:
            count += 1
        if x == 0:
            count = 0
        maxCount = max(maxCount, count)
    return maxCount


numpy.mean([oneTrial(200) for x in range(10000)])

Output: 6.9843

Also see this thread for exact computation without using Python simulation.

Upvotes: 2

Related Questions