Expected # of flips to get 10 heads in a row?

[Arslan7041]

So I wrote a program which gives you the expected number of coin flips needed to get 10 consecutive heads. Apparently the answer is 2046, but my program gives me 2,383. Can anyone tell me im doing wrong?

#include <iostream>
#include <cmath>
#include <ctime>
#include <cstdlib>


int main()
{
    srand(time(0));
    int SIZE = 10;
    bool arr[SIZE];

    int wins = 0;
    long int flips = 0;
    long double total = 0;
    int i = 0;

    while(true)
    {
        for(i = 0; i < SIZE; ++i)
        {
            arr[i] = rand() % 2; // 1 = heads, 0 = tails
            flips++;

            if(!arr[i]) break; // if 0 (tails), stop flipping and start from arr[0] again

        }

        if(i == SIZE) // if outcome was 10 heads in a row
        {
            wins++; // a 'win' is getting 10 consecutive heads
            total += flips; // add flips to total
            flips = 0; // reset flips back to 0 to count flips needed to get //another 10 heads in a row
        }

        if(wins == 100000) break; // stop the simulation once we hit 100,000 //wins
    }

    std::cout << "Wins = " << wins << std::endl;
    std::cout << "Total Flips = " << total << std::endl;
    std::cout << "Average # of flips needed to get 10 heads is : " <<   1.0*(total/wins) << std::endl;

}

Whats really weird is that the answer for getting 5 consecutive heads is 62 flips. So when I changed my program to calculate that (SIZE=5), I get 62 (i.e. the correct answer). So I expect my program to work for any SIZE. But when I changed by SIZE to 10, I get the incorrect answer.

I also have a slightly different coin-toss problem im trying to figure out, but I'll post that once this is resolved.

[shadder]

Hi,

Apparently the answer is 2046,

could you tell us how?

PS: Me+maths=bad

[Arslan7041]

In this video, from 6:20 to 9:15, he explains it: https://www.youtube.com/watch?v=-9FWBaWah28

[shadder]

compiling on cpp.sh i got this output

Wins = 100000
Total Flips = 2.04583e+08
Average # of flips needed to get 10 heads is : 2045.83

2nd time

Wins = 100000
Total Flips = 2.04022e+08
Average # of flips needed to get 10 heads is : 2040.22

this may be because of random variable in your code

[Arslan7041]

Oh snap, did not even think to check it on cpp.sh.

But if this is because of rand(), then why do I ALWAYS get 2,383? I rand this program at least 15 times and I always got 2,383.

Shouldn't I SOMETIMES get 2,046 or at least close to it?

[shadder]

IDK why are you getting 2313 always even when you are using srand, in my post above you see I got 2045.83 and 2040.22, they are pretty close to 2046...

BTW which IDE are you using?

[Arslan7041]

So I took advantage of c++11's <random> and modified my code as below;

#include <iostream>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <random>


int main()
{
    std::mt19937 generator(time(0));
    std::uniform_int_distribution<int> distribution(0,1);

    int SIZE = 10;
    bool arr[SIZE];

    int wins = 0;
    long int flips = 0;
    long double total = 0;
    int i = 0;

    while(true)
    {
        for(i = 0; i < SIZE; ++i)
        {
            arr[i] = distribution(generator); // 1 = heads, 0 = tails
            flips++;

            if(!arr[i]) break;
            //if(i%2 == 0 && !arr[i]) break; // if tails on an even toss, start over
            //if(i%2 != 0 && arr[i]) break; // if heads on an odd toss, start over

        }

        if(i == SIZE) // if outcome was 10 alternating H/T
        {
            wins++; // a 'win' is getting 10 alternating H/T
            if(wins%10000 == 0) std::cout << "wins: " << wins << std::endl;
            total += flips; // add flips to total
            flips = 0; // reset flips back to 0 to count flips needed to get another 10 heads in a row
        }

        if(wins == 100000) break; // stop the simulation once we hit 100,000 wins
    }

    std::cout << "Wins = " << wins << std::endl;
    std::cout << "Total Flips = " << total << std::endl;
    std::cout << "Average # of flips needed to get 10 alternating H/T : " << 1.0*(total/wins) << std::endl;
}

It works! Im getting 2,044 now. Much closer to the real answer. Only problem is that its extremely slow. It took 28 secs to run (compare that to the 6 secs it took the original). Why is this?

Is mt19937 slow, or is std::uniform_int_distribution<int> causing the program to slow? Dont know much about the <random> library so would be nice to know whats best to use for efficiency.

[Arslan7041]

Im using Code::Blocks by the way.

[Arslan7041]

Okay, so apparently, there is a problem with my IDE or something. I run the code on code::blocks and I get 2,383. I run the code on cpp.sh or on tutorialspoint online compiler, I get the correct answer of 2046. In both cases I used the rand() with mod.

[shadder]

But why will IDE's behave differently with srand()?

[a k n]

Because different IDE's use different compiler and implementation of the library. Different implementations may have bugs or some quirk

[JLBorges]

> Is mt19937 slow, or is std::uniform_int_distribution<int> causing the program to slow?

Measure it on the implementation that is used.

#include <iostream>
#include <random>
#include <ctime>

int main()
{
    const int n = 100'000'000 ;
    std::srand( std::time(nullptr) ) ;
    std::mt19937 twister( std::time(nullptr) ) ;
    std::uniform_int_distribution<int> distr(0,1) ;
    volatile int disable_opt = 0 ;

    {
        int cnt = 0 ;
        const auto start = std::clock() ;
        for( int i = 0 ; i < n ; ++i ) cnt += std::rand() % 2 ;
        const auto finish = std::clock() ;
        std::cout << "                 std::rand, modulo division: " << (finish-start) * 1000.0 / CLOCKS_PER_SEC << " msecs.\n" ;
        disable_opt += cnt ;
    }

    {
        int cnt = 0 ;
        const auto start = std::clock() ;
        for( int i = 0 ; i < n ; ++i ) cnt += twister() % 2 ;
        const auto finish = std::clock() ;
        std::cout << "              std::mt19937, modulo division: " << (finish-start) * 1000.0 / CLOCKS_PER_SEC << " msecs.\n" ;
        disable_opt += cnt ;
    }

    {
        int cnt = 0 ;
        const auto start = std::clock() ;
        for( int i = 0 ; i < n ; ++i ) cnt += distr(twister) ;
        const auto finish = std::clock() ;
        std::cout << "std::mt19937, std::uniform_int_distribution: " << (finish-start) * 1000.0 / CLOCKS_PER_SEC << " msecs.\n" ;
        disable_opt += cnt ;
    }

    return disable_opt - disable_opt ;
}

coliru (linux):

-------- clang++/libc++ ------------

                 std::rand, modulo division: 1590 msecs.
              std::mt19937, modulo division: 1490 msecs.
std::mt19937, std::uniform_int_distribution: 5430 msecs.

--------- g++/libstdc++ ------------

                 std::rand, modulo division: 1500 msecs.
              std::mt19937, modulo division: 740 msecs.
std::mt19937, std::uniform_int_distribution: 2270 msecs.

http://coliru.stacked-crooked.com/a/a996317dc947e323

[Arslan7041]

^ So I should scrap the use of std::uniform_int_distribution<int> and stick with using std::mt19937 object along with mod operator?

But does twister() % n guarantee equal probability for all numbers 0 to n-1?

[Arslan7041]

By the way, modulo with std::mt19937 is still running a bit slower for me than modulo with rand(). I guess this slight discrepancy is because we are using different machines?

[Peter87]

Arslan7041 wrote:

modulo with std::mt19937 is still running a bit slower for me than modulo with rand(). I guess this slight discrepancy is because we are using different machines?

rand() on Windows (when using MinGW or Visual C++) is famous for its low quality. It's fast but doesn't give you very good random properties.

rand() on Linux (when using GCC) is a bit more sophisticated. It gives you random numbers of better quality but that also means it's probably slower.

Arslan7041 wrote:

does twister() % n guarantee equal probability for all numbers 0 to n-1?

Only if n is a power of 2.

[Chervil]

So I should scrap the use of std::uniform_int_distribution<int> and stick with using std::mt19937 object along with mod operator?

Not unless execution time takes priority over accuracy of results.

For one thing, the timings are implementation-dependent, on my Windows machine I got these timings with the above code:

Compiler Name: TDM-GCC 4.8.1 64-bit Release

                 std::rand, modulo division: 1102 msecs.
              std::mt19937, modulo division: 500 msecs.
std::mt19937, std::uniform_int_distribution: 614 msecs.

For another, for anything but the simplest application, it is best to avoid rand(), especially with modulo operator.

[Arslan7041]

Understood.

I'll be posting another coin-flip problem Im working on soon. Stay tuned :)

[Peter87]

Note that std::mt19937 generates 32 bit numbers so if you really care about performance you could pull 32 coin flips from each number that you generate.

[Chervil]

Note that std::mt19937 generates 32 bit numbers so if you really care about performance you could pull 32 coin flips from each number that you generate.

I was wondering about this. I've not looked at the internal implementation of std::uniform_int_distribution, Perhaps in some implementations it uses this sort of optimisation?

[Arslan7041]

Note that std::mt19937 generates 32 bit numbers so if you really care about performance you could pull 32 coin flips from each number that you generate.

Im not sure I understand this. How would I implement this in my code?