HACKER Q&A
📣 aalhour

How many times will this loop run on average?


A friend of mine shared the following code snippet with me and asked me to guess how many times the loop will run on average:

  for(int i = 0; i < Random(1, 100); i++);
I tried to guess the answer analytically and gussed ~50 but the empirical test was surprising to me. Can someone explain why the average is around 12?

Runnable code: https://replit.com/@aalhour/RandomLoop#main.py

EDIT: Formatting.

  👤 Someone Accepted Answer ✓
In C (and your Python conversion), the i < Random(1, 100) part is evaluated each time through the loop, not once at start of the loop to determine the limit.

So, it’s 1% that the loop ends at i = 1, if it takes that hurdle 2% that it ends at i = 2, if it takes that hurdle 3% that it ends at i = 3, etc.

The calculation is easier if you phrase that this way:

It’s 99% that the loop continues at i = 1, if it takes that hurdle 98% of the rest that it continues at i = 2, if it takes that hurdle 97% that it continues at i = 3, etc.

So, the probability to make it past i = n is

  0,99 × 0,98 × 0,97 × … × (1 - n/100)
Note that this isn’t necessarily the case in all languages. Pascal, for example, has a real for loop where the limit is evaluated once and the index variable cannot be changed inside the loop, so that the compiler can determine the number of iterations before starting the first iteration.
👤 hardlianotion
Expected index given by

E [X] = \sum_{i \in [2,100)} p(X < i)\prod_{j < i}p (X \ge j)i.

Edit: Sorry rest of reply was wrong. Had to account for not hitting until i^th loop.

👤 orbz
You’re calculating a random number every time the loop runs. If you want an average of 50 you should call random outside the loop and save the value to be compared each time.
👤 haltist
The only random variable in that code is "Random(1, 100)" and its expected value is 50.