Unexpected results when counting how often sequences occur in a random distribution

Question

Given a coin game: you start with a dollar and a coin is flipped. If it's heads the dollar is doubled, if it's tails the game ends. However if head's is flipped again the payoff is now quadrupled and if head is flipped 3 times 8x and so on. The paradox is that the expect value is 1/2*1+1/4*2+1/8*4... = infinity. So you if you play the game long enough you should be getting progressively richer. Monte carlo simulation suggests not. This is simulation of the famous St. Petersburg Paradox

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Sorrow
{
    class Program
    {
        static void Main(string[] args)
        {
            Random rnd = new Random(Environment.TickCount);
            double totalSum = 0;
            int bigWins = 0;
            double iterations = 1000;
            for (int z = 0; z < 10; z++)
            {
                iterations *= 10;
                for (double i = 1; i < iterations; i++)
                {
                    int sum = 1;
                    int a = 1;
                    while (a == 1)
                    {
                        //generate a random number between 1 and 2
                        a = rnd.Next(1, 3);

                        if (a == 1)
                        {
                            sum *= 2;
                        }
                        if (sum > 8000&&sum<12000)// given discrete probability landing 13 times
                        {
                            // if the sum is over 8000 that means that it scored 1 13 times in a row (2^13) - that should happen
                            //once every 8192 times. Given that we run the simulation 100 000 000 times it should hover around 
                            // 100 000 000/8192
                            //However is much , much bigger
                            bigWins++;
                        }
                    }

                    totalSum += sum;

                }

                Console.WriteLine("Average gain over : "+iterations+" iterations is:" + totalSum / iterations);
                Console.WriteLine("Expected big wins: " + iterations / 8192 + " Actual big wins: " + bigWins);
                Console.WriteLine();
            }


        }
    }
}

As you can see we should expect 7 times smaller number. This makes me think that perhaps c# random is prone to choosing the same number over and over again? Is it true or there is something wrong with my code? How might I fix the issue?

I can't answer due to this being incorrectly marked as a duplicate, IMO. But your code example ran fine and does show the problem using `Random` for _strong_ randomness. This is exactly why Cryptography in C# does **not** use `Random`. — Zer0, Feb 26 '19 at 22:32
chains of 3x2 should happen if the last 3 numbers added to the total sum are 2. That should happen with frequency 1/8, exactly as chains of 3x1 — Goking, Feb 26 '19 at 22:37
Why did you divide by 8192? I assume that is 2 ^ 13? I am not sure that maths is accurate. 1 / 8192 is the probability of 13 random numbers all being 1, yes. But you can't divide the total number of iterations like that. Because a large sequence of numbers is not just blocks of 13 numbers connected together. If you have 13 adjacent ones, then the odds of having 14 of them (i.e. two 13 sequences) is quite high (in fact, 75%, since either a 1 at the front or back would be sufficient to get you there). I don't think you are considering that different sequences are **sharing** numbers. — mjwills, Feb 26 '19 at 22:42
What if there are 15 ones, all adjacent? That is the point I am making. Once you have 13 ones, all adjacent, then you have a 75% chance that you'll get at least 14 (looking at the digit before and after) and a >25% chance you'll get at least 15 of them. 14 means `bigWins` will be incremented twice. 15 means it will be incremented three times. etc etc — mjwills, Feb 26 '19 at 22:50
So what should be the probability then adjusting for sequences of 14 or more elements?However isn't it already correct 14 Times 1 will produce 2 13 times sequences, but its 2xtimes more unlikely, 15 times one will produce 3 13 times sequences , but is 8 times more unlikely(Far more than the 1/8192 chance once you get 13 right, so can we adjust fr that?) — Goking, Feb 26 '19 at 22:52
Those probabilities look bad yes (2 times more unlikely). But they are **much more probable** than starting the entire process again. You don't need 13 1s in a row once you have 13 1s already. **You only need 1 of them**. — mjwills, Feb 26 '19 at 22:54
I can't give you a solution, because I don't understand what you are trying to achieve. The point I am making is that your mathematical mental model might be flawed. Now, you might be right that `Random` isn't as random as you'd like - the point I am making is I don't think your code proves what you think it proves. — mjwills, Feb 26 '19 at 22:55
Simple fix to that is if (sum > 8000&&sum <12 000) Still 4 times higher though! Problem moved to http://www.talkstats.com/threads/coin-probability-problem.72982/ to see if something wrong with the math — Goking, Feb 26 '19 at 23:13
Your iterations will be off by one unless you start at 0 or loop until <= iterations. That won't really affect the overall calculations given the size of iterations, but it's a thing to keep in mind when making a loop. e.g. if you want to loop 10 times you can do `var i = 0; i<10; i++` or you can do `var i = 1; i <=10; i++` — TJ Rockefeller, Feb 26 '19 at 23:37

David Browne - Microsoft · Accepted Answer · 2019-02-27T00:16:19.327

You have two bugs. Your loop starts after a win, so the chance of a big win is 1/2^12, and you keep incrementing bigwins for additional wins after 12.

Try

   static void Main(string[] args)
    {

        Random rnd = new Random(Environment.TickCount);


        double iterations = 1000;
        for (int z = 0; z < 10; z++)
        {
            double totalSum = 0;
            int bigWins = 0;
            iterations *= 10;
            for (double i = 1; i < iterations; i++)
            {
                int sum = 2;
                int a = 1;

                while (a == 1)
                {
                    //generate a random number between 1 and 2
                    a = rnd.Next(1, 3);


                    if (a == 1)
                    {
                        sum *= 2;
                    }
                    if (sum > 8000)
                    {
                        // if the sum is over 8000 that means that it scored 1 12 times in a row (2^12) - that should happen
                        //once every 4096 times. Given that we run the simulation 100 000 000 times it should hover around 
                        // 100 000 000/4096
                        bigWins++;
                        break;
                    }
                }

                totalSum += sum;

            }

            Console.WriteLine("Average gain over : " + iterations + " iterations is:" + totalSum / iterations);
            Console.WriteLine("Expected big wins: " + iterations / 4096 + " Actual big wins: " + bigWins);
            Console.WriteLine();
        }


        Console.ReadKey();
    }

outputs something like:

Average gain over : 10000 iterations is:12.6774
Expected big wins: 2.44140625 Actual big wins: 1

Average gain over : 100000 iterations is:14.09468
Expected big wins: 24.4140625 Actual big wins: 21

Average gain over : 1000000 iterations is:14.022718
Expected big wins: 244.140625 Actual big wins: 249

Average gain over : 10000000 iterations is:14.0285748
Expected big wins: 2441.40625 Actual big wins: 2456

Average gain over : 100000000 iterations is:14.00012582
Expected big wins: 24414.0625 Actual big wins: 24574

Average gain over : 1000000000 iterations is:14.000105548
Expected big wins: 244140.625 Actual big wins: 244441

Average gain over : 10000000000 iterations is:13.9990068676
Expected big wins: 2441406.25 Actual big wins: 2440546

For simulation of the game it should not break if (sum > 8000) — Goking, Feb 27 '19 at 00:31

TJ Rockefeller · Answer 2 · 2019-02-26T23:33:47.567

What you are looking for is the probability that the game gets to or continues past $8000 which is 1 minus the sum of the probabilities of ending before $8000

Probability of ending after...

0 rounds 1/2 $2
1 round 1/4 $4
2 rounds 1/8 $8
3 rounds 1/16 $16 (same as 1/(2^(rounds+1))
...
12 rounds 1/2^13 $8192 (in your code you are off by one round, you get to $8192 after 12 wins, not 13

sum all of the probabilities of ending before $8192 and you get 0.999755859

So... your probability of a game getting to at least $8192 is 1-0.999756 or 0.000244141

Compare this to the probability of 1/8192 = 0.0001220703125 and you see you are off by about a factor of 2.

This doesn't change the fact that Random isn't a good approximation of random, and your expected results will still be off.

If you want to use RNGCryptoServiceProvider you can do the following

initialize a RNGCryptoServiceProvider somewhere in your class

RNGCryptoServiceProvider rngCsp = new RNGCryptoServiceProvider();

Then where you are assigning the value a you can do the following

//generate a random number between 1 and 2
//allocate an array of bytes to be populated by rngCsp
byte[] randomNumber = new byte[1];
//populate the array with a random byte
rngCsp.GetBytes(randomNumber);
//if the random byte is [0,125] return 1 and if [126,255] return 2
a = randomNumber[0] < 126 ? 1 : 2;

Yes but i already fixed that part " gets to or continues past $8000" to gets to $8000 by changing if((sum > 8000)) to if(sum>8000 && sum < 12 000) and the expected result is still much higher? Now that is the probability of landing exactly 13 times and not higher? — Goking, Feb 26 '19 at 23:47
@Goking This is covered in my answer and the accepted answer https://stackoverflow.com/a/54895961/4708150. The mistake is that you get to $8192 after 12 wins, not 13 wins — TJ Rockefeller, Feb 27 '19 at 00:22

mjwills · Answer 3 · 2019-02-27T02:51:14.327

If you are interested in calculating the count of how many times a sequence of 13 or more ones occur, the below code may be of interest to you. It may not be as fast as the original code, but I think it may be slightly easier to read and understand (which I think is important, but because part of the reason why it took so long to spot the bugs in the original code was that it was a little hard to follow the logic). Basically, it keeps a queue of the last 13 items, and checks whether they are all 1.

Note that the calculation I have used to determine the expected number of sequences is also different to yours. I don't just divide by 8192, instead I do (iterations - (iterations * (1 - (1m/8192m)))). I don't think that calculation is 100% right, but it is more accurate than the original.

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp4
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            var queue = new Queue<int>();
            var rnd = new Random(Environment.TickCount);

            int bigWins = 0;
            long iterations = 10000000;
            const int sequenceLength = 13;
            double probability = 1 / Math.Pow(2, sequenceLength);

            for (int z = 0; z < iterations; z++)
            {
                var a = rnd.Next(1, 3);
                queue.Enqueue(a);

                if (queue.Count == sequenceLength)
                {
                    if (queue.Distinct().Count() == 1 && queue.First() == 1)
                    {
                        bigWins++;
                    }
                    queue.Dequeue();
                }
            }

            Console.WriteLine("Expected big wins: " + (iterations - (iterations * (1 - probability))) + " Actual big wins: " + bigWins);

            Console.ReadLine();
        }
    }
}

Unexpected results when counting how often sequences occur in a random distribution

3 Answers3