A puzzling function

This one made my brain itchy.

Consider this simple non-deterministic python function:

import random
def function():
    total = 1
    while random.randint(0,1) == 0:
        total *= 2
    return total

What it does is simple: It flips a coin. If it's heads, double the value of "total". If it's tails, return it.

I want to run the function n times and find the sum and expected value. Here's a helper that does just that:

def run(n):
    total = 0
    for i in xrange(n):
        total += function()
    print "Total:", total, "Expected:", float(total)/n

So far, just some basic concepts. We have a function called "function" and we have a tester ("run") which tests the expected value of the function. Run(200) would find the expected value using 200 trials of our function.

Now for the puzzling part. (This will work with ALMOST everyone)

Let's see the sum of 100 runs. And let's do it several times just to be sure:

>>> run(100)
Total: 328  Expected: 3.28
>>> run(100)
Total: 682  Expected: 6.82
>>> run(100)
Total: 372  Expected: 3.72
>>> 

It looks like the expected value appears to be roughly between 3 and 6!

Maybe we'll get a better reading with more runs. Let's try 10000:

>>> run(10000)
Total: 67577  Expected: 6.7577
>>> run(10000)
Total: 83447  Expected: 8.3447
>>> run(10000)
Total: 68674  Expected: 6.8674
>>> 

Wow, the expected value appear higher than before. Perhaps we got lucky with our 100 runs. Let's try the 100's again:

>>> run(100)
Total: 321  Expected: 3.21
>>> run(100)
Total: 441  Expected: 4.41
>>> run(100)
Total: 494  Expected: 4.94

Impossible! It appears that the expected value of the function changes depending on how many times we decide to run it! The more times "run" tests the function, the higher the expected value!

Doesn't make any sense? Try running it with 1000000 a few times and see for yourself. Compare that with the result you get with 100 runs.

>>> run(1000000)
Total: 12661099  Expected: 12.661099
>>> run(1000000)
Total: 9382031  Expected: 9.382031
>>> run(1000000)
Total: 9303708  Expected: 9.303708
>>> 

Surprisingly, the more trials you make to determine the expected value, the higher the expected value appears.

NO. WAY. Hint: St. Petersburg paradox