A Math Problem / General Chatting / Forums

Forums

4hv.org :: Forums :: General Chatting

« Previous topic | Next topic »

A Math Problem

previous 1 2

Move Thread

LAN_403

IamSmooth

Fri Mar 13 2009, 12:36PM

Registered Member #190 Joined: Fri Feb 17 2006, 12:00AM
Location:
Posts: 1567

What does the ratio of (Bob winning 2nd turn)/(Bob winning general) tell you?

neuralinhibitor

Fri Mar 13 2009, 05:02PM

Registered Member #2023 Joined: Fri Mar 13 2009, 05:53AM
Location:
Posts: 7

Well, we know that Bob won (this is an assumption of the problem) and we want to know the probability that Bob won on his second turn so the ratio p(Bob winning on his second turn) / p(Bob wins) gives us the probability that Bob won on his second turn given that he won.

Steve Conner

Sat Mar 14 2009, 06:33PM

Registered Member #30 Joined: Fri Feb 03 2006, 10:52AM
Location: Glasgow, Scotland
Posts: 6706

Hi all,

I was feeling bored so I whipped up a quick C program to test Chris's solution. It makes a virtual Bob and Sue play the game 1 million times (takes about 2 seconds on my clunky old laptop) and keeps track of how many games they won. A cookie for anyone who finds a bug!

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int RollDice(void)
{
    return ((rand() % 6) + 1);
}

int main(int argc, char *argv[])
{

    unsigned long int TotalGames = 0;
    unsigned long int BobWonGames = 0;
    unsigned long int BobWonOnTurn2 = 0;
    unsigned long int SueWonGames = 0;
    unsigned long int Turns;
    
    for(TotalGames=0; TotalGames < 1000000; TotalGames++)
    {      
        for(Turns=1; Turns < 1000000; Turns++)
        {
                 if(RollDice() == 6) 
                 {
                               SueWonGames++; 
                               break;
                 }
        
                 if(RollDice() == 6) 
                 {
                               BobWonGames++;
                               if(Turns == 2) BobWonOnTurn2++; 
                               break;
                 }
        }
    }

    printf("Total games %d, Sue won %d, Bob won %d, of which %d on turn 2\n",
                  TotalGames, SueWonGames, BobWonGames, BobWonOnTurn2);
                  
    float BobProb;
    
    BobProb = (float)BobWonOnTurn2/(float)BobWonGames;
    
    printf("Games Bob won on turn 2 / Games Bob won in total %f\n", BobProb);
    printf("Chris's answer is (11/5)*(5^3)/(6^4) = %f\n", ((float)(5*5*5*11)/(float)(6*6*6*6*5)));
    
  
  system("PAUSE");	
  return 0;
}

The output is:

Total games 1000000, Sue won 545202, Bob won 454798, of which 96640 on turn 2
Games Bob won on turn 2 / Games Bob won in total 0.212490
Chris's answer is (11/5)*(5^3)/(6^4) = 0.212191
Press any key to continue . . .

Marko

Sun Mar 15 2009, 09:08PM

Registered Member #89 Joined: Thu Feb 09 2006, 02:40PM
Location: Zadar, Croatia
Posts: 3145

Guys... overwhelmed in your brainstorm, the only thought that I have is that those random numbers generated by clunky old finite state machine might not be random enough to completely fit the answer. Still it is within 0.01%... is that so bad after all?

I would play with the number of games a bit to see how it affects the output - does it make it tend closer to or further away from the answer, etc...

I would also expect the variations to be periodic after n games depending on the PRNG script's state.

Marko

Chris Russell

Sun Mar 15 2009, 09:43PM

... not Russel!
Registered Member #1 Joined: Thu Jan 26 2006, 12:18AM
Location: Tempe, Arizona
Posts: 1052

Steve McConner wrote ...

Hi all,

I was feeling bored so I whipped up a quick C program to test Chris's solution. It makes a virtual Bob and Sue play the game 1 million times (takes about 2 seconds on my clunky old laptop) and keeps track of how many games they won. A cookie for anyone who finds a bug!

The random number generator isn't initialized, so I always get the same output. All I did was to add:

srand ( time(NULL) );

To the top of int main. After that it gave a slightly different result each time. Here's the output with it set to 100 million games:

Total games 100000000, Sue won 54546726, Bob won 45453274, of which 9645701 on turn 2
Games Bob won on turn 2 / Games Bob won in total 0.212211
Chris's answer is (11/5)*(5^3)/(6^4) = 0.212191

Very good! And, just for fun, here's the result of one billion games played (took about 5 minutes on my oldish Athlon XP 2300+):

Total games 1000000000, Sue won 545493317, Bob won 454506683, of which 96431256 on turn 2
Games Bob won on turn 2 / Games Bob won in total 0.212167
Chris's answer is (11/5)*(5^3)/(6^4) = 0.212191

No real improvement over the 100M game version, but that is probably just the limitations of the random number generator showing through.

Steve Conner

Mon Mar 16 2009, 10:31AM

Registered Member #30 Joined: Fri Feb 03 2006, 10:52AM
Location: Glasgow, Scotland
Posts: 6706

Whee, this is fun. Has anyone spotted the irony yet of doing a Monte Carlo simulation of a dice game?

You're right, I forgot to seed the PRNG, cookies for Chris and Marko -> O O

The 0.01% error (whatever "error" means in this context) could be due to one of three things:

* The theoretical answer involves an infinite series with terms as (5/6)^n. This will converge slowly because 5/6 is nearly 1.

* The PRNG is "not random enough" (again, whatever that means)

* The algebra of conditional probabilities assumes an infinite sample size, but the number of games played in the program is not infinite. For example, when the sample size is limited, you must use a Student T distribution instead of the Gaussian, and you no longer get an exact answer, just an interval inside which you can state that the answer lies, with some level of confidence.

Condition 1 may be the same as Condition 3.

A whole packet of cookies to anyone who can use Student's T test or similar to work out the answer for finite sample sizes and a 95% confidence level. Or hook the program up to a higher grade (do I mean lower-grade?!) source of entropy. Either way, you are testing the "randomness" of the C library PRNG.

previous 1 2

Moderator(s): Chris Russell, Noelle, Alex, Tesladownunder, Dave Marshall, Dave Billington, Bjørn, Steve Conner, Wolfram, Kizmo, Mads Barnkob