Arriving at a close approximation of the probability using code

Question

I was given a math question on probability. It goes like this:

There are 1000 lotteries and each has 1000 tickets. You decide to buy 1 ticket per lottery. What is the probability that you win at least one lottery?

I was able to do it mathematically on paper (arrived at 1 - (999/1000)^1000), but an idea of carrying out large iterations of the random experiment on my computer occurred to me. So, I typed some code — two versions of it to be exact, and both malfunction.

Code 1:

#include<iostream>
#include <stdlib.h>

using namespace std;

int main() {
    int p2 = 0;
    int p1 = 0;
    srand(time(NULL));
    for (int i = 0; i<100000; i++){
        for(int j = 0; j<1000; j++){
            int s = 0;
            int x = rand()%1000;
            int y = rand()%1000;
            if(x == y)
                s = 1;
            p1 += s;
        }
        if(p1>0)
            p2++;
    }
    cout<<"The final probability is = "<< (p2/100000);
    return 0;
}

Code 2:

#include<iostream>

#include <stdlib.h>

using namespace std;

int main() {
    int p2 = 0;
    int p1 = 0;
    for (int i = 0; i<100000; i++){
        for(int j = 0; j<1000; j++){
            int s = 0;
            srand(time(NULL));
            int x = rand()%1000;
            srand(time(NULL));
            int y = rand()%1000;
            if(x == y)
                s = 1;
            p1 += s;
        }
        if(p1>0)
            p2++;
    }
    cout<<"The final probability is = "<< (p2/100000);
    return 0;
}

Code 3 (refered to some advanced text, but I don't understand most of it):

#include<iostream>

#include <random>

using namespace std;

int main() {
    int p2 = 0;
    int p1 = 0;
    random_device rd;
    mt19937 gen(rd());
    for (int i = 0; i<100000; i++){
        for(int j = 0; j<1000; j++){
            uniform_int_distribution<> dis(1, 1000);
            int s = 0;
            int x = dis(gen);
            int y = dis(gen);
            if(x == y)
                s = 1;
            p1 += s;
        }
        if(p1>0)
            p2++;
    }
    cout<<"The final probability is = "<< (p2/100000);
    return 0;
}

Now, all of these codes output the same text:

The final probability is = 1
Process finished with exit code 0

It seems that the rand() function has been outputting the same value over all the 100000 iterations of the loop. I haven't been able to fix this.

I also tried using randomize() function instead of the srand() function, but it doesn't seem to work and gives weird errors like:

error: ‘randomize’ was not declared in this scope
randomize();
           ^

I think that randomize() has been discontinued in the later versions of C++.

I know that I am wrong on many levels. I would really appreciate if you could patiently explain me my mistakes and let me know some possible corrections.

score 0 · Answer 1 · answered Jun 02 '17 at 13:08

0

Only seed the pseudorandom number generator by srand once at the beginning of your program. When you seed it over and over again you reset the pseudorandom number generator to the same initial state. time has a granularity measured in seconds, by default. Odds are you are getting all 1000 iterations - or most of them - within a single second.

answered Jun 02 '17 at 13:08

Patrick87

27,682
3
38
73

I see, and that is what I tried in the first code. How do I escape the problem of not being able to generate new random numbers in the same loop? For x and y – Pranshu Malik Jun 02 '17 at 13:16

score 0 · Answer 2 · answered Jun 02 '17 at 14:09

See this answer to someone else's question for a general description of how pseudorandom number generators work.

This means that you should be creating one instance of a PRNG in your program and seeding it one time. Don't do either of those tasks inside loops, or inside functions that get called multiple times, unless you really know what you're doing and are trying to do something sophisticated such as using correlation induction strategies such as common random numbers or antithetic variates to achieve "variance reduction".

Bob__ · Accepted Answer · 2017-06-02T15:02:00.033

You should reset your count (p1) at the beginning of the outer loop. Also, be aware of the final integer division p2/100000, any value of p2 < 100000 would result in 0.

Look at this modified version of your code:

#include <iostream>
#include <random>

int main()
{
    const int number_of_tests = 100000;
    const int lotteries = 1000;
    const int tickets_per_lottery = 1000;

    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> lottery(1, tickets_per_lottery);

    int winning_cases = 0;
    for (int i = 0; i < number_of_tests; ++i )
    {
        int wins = 0;                           // <- reset when each test start
        for(int j = 0; j < lotteries; ++j )
        {
            int my_ticket = lottery(gen);
            int winner = lottery(gen);
            if( my_ticket == winner )
                ++wins;
        }
        if ( wins > 0 )
            ++winning_cases;
    }
    // use the correct type to perform these calculations
    double expected = 1.0 - std::pow((lotteries - 1.0)/lotteries, lotteries);
    double probability = static_cast<double>(winning_cases) / number_of_tests;

    std::cout << "Expected: " << expected 
              << "\nCalculated: " << probability << '\n';

    return 0;
}

A tipical run would output something like:

Expected: 0.632305
Calculated: 0.63125

Arriving at a close approximation of the probability using code

3 Answers3