CODEWITHSUNDEEP
javamathrandomprobability
Derek Zheng
Derek Zheng

Reputation: 33

Why is my simulation not finding infinite expected value?

In the Youtube video Numberphile Infinity (starting at 6:09) there is an experiment described (the St. Petersburg Paradox) in which a game has infinite expected value.

I tried to write a Java program to find out a long-run expected value (average). The theoretical expectation is infinity, but what I get is some numbers around 10. Is it because my program is wrong? Because I think when the number of experiment is large enough, the experimental average will be very close to the mathematical expectation. Here is my program.

public class Main {
    public static final int NUM_EXPERIMENT = 1000000;
    public static void main(String[] args) {
        int total = 0;
        for (int i = 0; i < NUM_EXPERIMENT; i++) {
            int counter = 1;
            int subtotal = 1;
            while ((int) (Math.random() * 2) == 0) {
                subtotal *= 2;
                counter++;
            }
            total += subtotal;
        }
        double expectation = total / (double) NUM_EXPERIMENT;
        System.out.println("The expectation of this experiment is " + expectation);
    }
}

Upvotes: 3

Views: 457

Answers (3)

templatetypedef
templatetypedef

Reputation: 372724

I think this has everything to do with math and little to do with ints.

One thing you might notice is that if you run more and more trials, the expected value will get larger and larger. The expected value is infinite because there are extraordinarily unlikely events that yield extraordinarily large payoffs. You're unlikely to get this to happen because the probability of earning 2n profit is 2-n. For example, this means that the probability of getting $1,000,000 (approximately $220) is about 1 in 220. On expectation, you'd need to run one million trials before you ever see this occur. Consequently, if you only run one hundred thousand trials, you wouldn't expect to see something like this happen. However, as the number of trials increases, the probability that you hit one of these sorts of sequences grows, and so the expected value will increase.

Think of it this way: you will never, ever see infinite profit because eventually the coin tosses the wrong way and you collect your winnings. Therefore, you won't ever get infinite profit reported by your program. However, as you play more and more games, the average will increase. The law of large numbers does indeed say that as you play more games you'll approach the average more and more closely, but it doesn't say that a small number of trials will suffice. Since your expected value is infinite, you're going to need a lot of trials before you're going to converge to infinity. ^_^

Other answers have noted that you might be overflowing the maximum value of an int, which is true but I think irrelevant here. You should switch to using something like a double or long to hold the values, but the reason you're not seeing infinite payout is because it's exponentially unlikely that you'll see one of the sequences that yields extreme payouts.

Hope this helps!

Upvotes: 4

libik
libik

Reputation: 23029

Range of integer value is ~ -2 147 000 000 to 2 147 000 000, if you exceed the max value of an integer, it is overflowed to the min value of an integer.

Upvotes: 0

Neil Neyman
Neil Neyman

Reputation: 2158

You are overflowing the integer data-types. They hit a max value and cycle back to the minimum value. Can't do infinite equations literally like that.

Upvotes: 1

Related Questions