Simulating flipping a coin using list comprehension and randomness, code works at first then hangs

Question

Having problem with a coin flip simulation. This code should be counting the amount of flips on average it should take to flip a coin and get tails three times in a row (so a success = 3 't', 1 success satisfies the first experiment).

import random

experiments = [1, 10, 100, 1000, 10000, 100000]

for number in experiments:
    experiment = []
    success = 0
    while success < number:
        face = random.choice(['h','t'])
        experiment.append(face)
        success = ''.join(experiment).count('ttt')
    print(f'Experiments: {number}')
    print(f'Average flips: {len(experiment)/success}\n')

Output looks like this:

[evaluate troubleshooting.py]
Experiments: 1
Average flips: 27.0

Experiments: 10
Average flips: 6.4

Experiments: 100
Average flips: 14.39

Experiments: 1000

What is it doing instead? Are you getting any output at all? — glibdud
@glibdud I actually have been running it just to see if it works all the way through and it does, but I think using list comprehension is making it take longer than it should. It almost instantly gets to 100 experiments then it gets exponentially slower. So, I'm seeing if there's somewhere in this process I might be able to optimize or speed up? The Average flips statistically should be around 14. — papatri
Ok, so to clarify: You are trying to see on average how many flips it takes to get a string of 'ttt' (3 tails in a row) using 1,10,100,1000... flips? Am I understanding correctly? — Nick Vitha
10000 and 100000 flips will take much longer than 1000, and that is what causes the code to keep running, and you think it has hung. — Devesh Kumar Singh

Nick Vitha Nick Vitha · Accepted Answer · 2019-04-11T21:28:51

Well, I think the main problem is that success = ''.join(experiment).count('ttt') line will cause your program to search the entire list for each and every run through your while loop, which will be O(n^2) time complexity (AKA, BAD. Really really bad the more experiments you run).

I whipped up a (rudimentary) program that will do that part in linear (O(n)) time:

import random

experiment_size = [1,10,100,1000,10000,100000]

for number in experiment_size:
    last = False # track whether the last 3 flips were tails. False = don't care, 
                 # True = tails
    last_2 = False
    last_3 = False

    success = 0
    runs = 0
    while success < number:
        runs += 1
        last_3 = last_2 #bump the 3rd from last flip
        last_2 = last
        last = bool(random.getrandbits(1)) #get True or False, randomly
        if(last & last_2 & last_3): #if all are tails
            success += 1
            last, last_2, last_3 = False, False, False #reset so that you have to get 3
                                                       #in a row again
    print("Runs: " + str(runs) + "\nSuccesses: " + str(success) +"\nAverage: " + str(runs/success) + "\n")

Because we're not traversing an entire list for every repetition, it's a lot faster.

Simulating flipping a coin using list comprehension and randomness, code works at first then hangs

1 Answers