Time-complexity of cummulative sum of random numbers ( from uniform distribution ) as long as sum is less than 1

Question

What is the time-complexity of the following loop?

import random  
def cummulative_sum():
   a = 0
   while a < 1:
       a += random.random()
   return a

What promises me that the loop will stop? after all, random.random() could keep generating 0 all the time ( ofcourse, highly unprobable but still... ). How many times will it run? ( the answer depends on random.random() being a uniform probability, but I can't seem to link the mathematics to the complexity ).

Answer 1

How many times will it run?

Finding the expected number of iterations for this loop is a tricky math problem. You can see a few solutions in this post: https://math.stackexchange.com/questions/8508/expected-number-of-0-1-distributed-continuous-random-variables-required-to-sum

Apparently, this was even a question on the 1958 Putnam test (so you know it's a tough one): https://prase.cz/kalva/putnam/psoln/psol583.html

What promises me that the loop will stop?

Nothing! It's true that random.random() could return 0s forever, and the function would never terminate. This is reminiscent of a Las Vegas algorithm in some ways, since its expected runtime is finite, but its worst case runtime is unbounded.

---

You can even explore your average runtime experimentally, like so:

import random  
import math

def cummulative_sum():
    a = 0
    iterations = 0
    while a < 1:
        a += random.random()
        iterations += 1
    return iterations

def main():
    total_iterations = 0
    runs = 1_000_000
    for _ in range(runs):
        total_iterations += cummulative_sum()

    print('Average number of iterations:', total_iterations / runs)
    print('e:                           ', math.e)

main()