Roulette Color Streak Program

http://www.cs.uwm.edu/classes/cs151/Bacon/Lecture/HTML/ch06s09.html
says "integer(8) is 64 bit int" whatever that means. I stopped at F77 and am a little confused by the language now.

I knocked a little time off the C one with
wheelSpot = distribution(generator);
colorPicked = (colors)(wheelSpot/18+1); //GRB 123
streakCount = (colorPicked == lastColorPicked)*streakCount+1;
lastColorPicked = colorPicked;

which I think is doing the same thing as before.

its the distribution that is costing you.
rand()%38 is twice as fast on mine.
hardcoding wheelSpot to the same value every time in a flat assignment is 1/10 of a second.
hard to fix that... looking at the random lib now for any mad performance hax.

Putting 0-38 in a vector over and over (say 10 times) and shuffling it every few iterations (depending on number of copies), iterating to pick off next was about the same as rand(). I can't get <random> anywhere close with various engines but I am not an expert at it. Pre-generation might do better, but I don't see it (but havent tried it either).

granted, its a LOT of values being generated here.

Last edited on

Longest streak = 33

So that was FORTRAN, but the question from OP

There's nothing that I'm seeing that would cause a stop at 27

this suspected limit of 27 stays unanswered? In addition it's not only the racing car to make a great hullabaloo, it's also know a shortcut to the finishing line.

When I take a look at the well known wheels, there is a minor but not neglectable difference, the European (or French) single-zero vs the American double-O layout:
https://www.888casino.com/blog/sites/newblog.888casino.com/files/inline-images/EuropeanSingleZeroWheel-Image.png
https://www.888casino.com/blog/sites/newblog.888casino.com/files/inline-images/AmericanDoubleZeroWheel-Image_0.png
Most important regarding the colours, they are independent from the numbers. Every second colour is the same unless it's green. So why not use rand() % 2 to indicate the colour?

// same colour in consecutive roulettes jeu
#include <iostream>
#include <random>
#include <chrono>
using namespace std;

int main()
{
  const int wpo = 37;       // French or European Wheel = 37, American-double-O = 38
  unsigned long long i(1);  // number of jeu
  unsigned hit, maxStreak(0), Streak(1), prevClr, Clr;

// prepare the random engine
  unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
  std::default_random_engine generator (seed);
  std::uniform_int_distribution<int> distribution(0, wpo);

// run-in cycle
  do
  {
      hit = distribution(generator);
      prevClr = hit % 2;
//} while (hit / 19 == 0);  // green on American wheel
  } while (hit      == 0);  // 0 = green

  for (;i<99999999;++i)   // "do forever"
  {
      hit = distribution(generator);
      Clr = hit % 2;
//    if (hit / 19 == 0 || Clr != prevClr)  // American double O wheel
      if (hit      == 0 || Clr != prevClr)
      {
          if (Streak > maxStreak)
            cout << "New max " << Streak << " after " << i << "th jeu.\n";
          maxStreak = max(maxStreak, Streak);
          Streak = 1;
//        if (hit / 19 == 0)    // American double O wheel
          if (hit      == 0)
            prevClr -= 9;
          else
            prevClr = Clr;
      }
      else
        Streak++;
  }
//  return 0;
}

Green is so rare compared to rouge & noir I do not count streaks for it.
The limitation of the "do forever" loop to 99999999 is due to www.cpp.sh showing output only after program ends. One (of several) results:

New max 1 after 1th jeu.
New max 3 after 4th jeu.
New max 5 after 11th jeu.
New max 11 after 36th jeu.
New max 13 after 3356th jeu.
New max 14 after 5036th jeu.
New max 15 after 31642th jeu.
New max 21 after 323654th jeu.
New max 22 after 3467549th jeu.
New max 24 after 24890313th jeu.
New max 25 after 74547507th jeu.
New max 27 after 97397085th jeu.
New max 28 after 98814020th jeu.

I can not confirm a "27 limit."

This is such a great amount of information I'm going to be busy with all of this for a while! Thanks everyone for any tips, I'm going to keep playing with it too. I'm on an i7 CPU, Win10 64-bit, the PC is pretty zippy, tons of RAM, SSD, etc. I don't seem to have an issue with it tying up the PC either when it runs, even in the "slow" version. I want to play with the Fortran version more with the suggested compiler switches, if I can get that to go, I just have to find a way to let spinCount keep going up without filling up the variable/memory. I could always wrap a call to it in C++, so the file I/O and the counting can be done with something that can handle it.

I really never used Fortran so it takes me forever to get anywhere with it, it seems that syntax is old vs new all mixed together in some cases. I'll use the great example posted here to build from.

You guys all rock, this is a blast for me!

you are not wrong. The major living versions of fortran are 77 and 90 (and any newer, I know not). And those are the 19XX years of the revisions. Its one of the oldest languages, it was originally for engineering on punch card and mechanical(!) computers. It is a mix of old and new, indeed. If f77 were a person, it would be 43 years old... meaning programmers who used it back then would be 63ish ...

I don't think 27 is a limit. 27 is the answer from the original code if you only did one outer loop iteration, though, at least on my box. I got a 28 at least once playing with random generation. Remember that, for each value, there is only a 1 in 38 or whatever it is chance of a duplicate of the last value. That is pretty darn low. The odds of getting just 5 of the same thing in a row are daunting. 27 in a row... indicates a flawed random generator to me, possibly. Its a pretty hard number to beat.

Last edited on

@jonnin

Remember that, for each value, there is only a 1 in 38

Sorry - it's about the colours, not the numbers. Please have a look here:
https://www.888casino.com/blog/sites/newblog.888casino.com/files/inline-images/EuropeanSingleZeroWheel-Image.png and here: https://www.888casino.com/blog/sites/newblog.888casino.com/files/inline-images/AmericanDoubleZeroWheel-Image_0.png and forget the numbers. Can you see the pattern? The colour-pattern please. Now model it in code, something % 2 does comes to mind, doesn't it?

Well, it is challenging for the the pseudo random generator. 28..31, once even 34 odd or even results in one row (by srand(time(0)); and rand()) rouses oppositions: "this is not random!" It depends how often it occures.

In contrast, using

  unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
  std::default_random_engine generator (seed);
  std::uniform_int_distribution<int> distribution(0, wpo);
and
      hit = distribution(generator);

I do not get (up to now) more than 28 even or odd in one row. Could it be, that this default_random_engine takes care of this detail? Where are the random experts of this list?

web sez:
If a fair coin is flipped 21 times, the probability of 21 heads is 1 in 2,097,152.
Im sticking to bad PRNG theory. its possible, of course, given the huge number of tries we did...

Last edited on

If a fair coin is flipped 21 times, the probability of 21 heads is 1 in 2,097,152.

O, what a finding. That is pretty close to 2^-21, probably the probability of 22 heads in one row is 2^-22. There is a saying, the a chance is allways 50:50 (it works or it does not), it holds true for flipping a coin, so 50% is 1/2, 22 times a half is 2^-22. So far the theory.

The subject is not to prove the theory, it's about coding to get results which comply with theory. So when one PRNG limits consecutive even or odd RN to 28, it has limited usage. For fun I tried my 'Roulette Color Streak Program' again with a "very quick and very dirty" PRNG. Result: (up to now) never more than 31 in one row. Only a little better.

// same colour in consecutive roulettes jeu
#include <iostream>
using namespace std;

const unsigned multiplier(1664525), increment(1013904223);
unsigned idum(0);

unsigned vqvdran()  // based on 32 bit unsigned arithmetic
{
    idum = multiplier*idum+increment;
    return idum;
}

int main()
{
  const int wpo = 37;       // French or European Wheel: 37, American-double-O: 38
  unsigned long long i(1);  // number of jeu
  unsigned hit, maxStreak(0), Streak(1), prevClr, Clr;

// run-in cycle
  do
  {
      hit = vqvdran() % wpo;
      prevClr = hit % 2;
  } while (hit == 0);       // 0 = green

  for (;i<8000000000;++i)   // "do i=1 forever"
  {
      hit = vqvdran() % wpo;
      Clr = hit % 2;
      if (hit != 0 && Clr == prevClr)
        Streak++;
      else
      {
          if (Streak > maxStreak)
          {
              maxStreak = Streak;
              cout << "New max " << maxStreak << " after " << i << "th jeu.\n";
          }
          Streak = 1;
          prevClr = (hit == 0) ? 9 : Clr;
      }
  }
}

The question is now, how to find an appropriate RN generator.

lastchance (6980)

For the probability theory you can look at this paper:
https://www.maa.org/sites/default/files/pdf/upload%5flibrary/22/Polya/07468342.di020742.02p0021g.pdf

Equation 5 in that paper will give the expectation of the longest run of one colour (say, red). Actually, it gives an asymptotic expression (i.e. large n), but that is good enough here. The expectation of the longest run of reds isn't going to be very different from that of the longest run of one colour.

Basically, the longest run goes logarithmically with n ... so, simply grows very slowly.

Coding up equation 5 I get for n = 1 billion (1e9) that expected longest run of reds is 27, whilst for n=1e12 it is still only 36. So I wouldn't spend too long trying to simulate it!

If you find a longest run of 27 when n = 1 billion ... then your random number generator is behaving fine!

Note that you won't always get a longest run of 27 when n = 1 billion ... it's just what you would get on average. The cited paper also gives an (asymptotic) expression for the variance, from which you can get the standard deviation. From the laws of large numbers you can expect to see a scatter of about two standard deviations either side of the mean. In this instance that means about 24 to 30 for that value of n.

Here's my code for equations (5) and (6) in the paper - you can try it out:

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
   const double gamma = 0.57721566;    // Euler-Mascheroni constant
   const double pi    = 3.14159265;    // pi

   double p = 18.0 / 38.0;             // probability of, e.g, red
   double q = 1.0 - p;
   double log1p = log( 1.0 / p );

   unsigned long long n;
   cout << "Input n: ";   cin >> n;
   double expectation = log( n * q ) / log1p + gamma / log1p - 0.5;
   double variance = pi * pi / ( 6.0 * log1p * log1p ) + 1.0 / 12.0;
   double stddev = sqrt( variance );

   cout << "Asymptotic (large n) expectation is " << expectation << '\n';
   cout << "Standard deviation is " << stddev << '\n';
}

Last edited on

Why build a race car when you could calculate/simulate the race? I'll take the race car!

Quotation from http://www.cplusplus.com/forum/general/252371/#msg1111033
A sonorously Rrrrrr -- pure emotions! (BTW, today Good Friday is in German Karfreitag, some spell it Car-Freitag and meet for illegal racing on public roads.)

With the risk to bore you I repeat, "The subject is not to prove the theory, it's about coding to get results which comply with theory." As such your link to the coin tossing paper helps to identify flaws in PRNGs. IMO we should focus on the observed limit 27 of all longest runs mentioned in OP.

BTW, also equation (2) in the a. m. paper gives the longest run to be expected. Up to now I was not able to find a sufficing RN generator with much more than 31 runs of even or odds. According your program for 8e10 I should have seen LR=33 once in a while. (The lately observed 34 was probably a reading error by operator's tired eyes.)

Question: Where may I find the analysis of PRNGs available in C++?

I'm also still curious about the seemingly consistent stopping point for the streaks. I'm double curious as to why Powershell appears to have streaks produced all over the place. That's the only language I've used that got me into the 40s. Maybe it's not as random? Or maybe there is some reason why the compiled programs behave differently?

That's the only language I've used that got me into the 40s.

Are those 40s consistent with the theory? Or brief, with lastchance's routine here -- http://www.cplusplus.com/forum/general/252371/2/#msg1111268

The powershell program was considerably slower than anything done in this thread, so it actually is ahead of the math version with it getting into the 40s.

Sorry, that is beyond my English -- powershell program was slower but ahead of the math version? Even www.babelfish.de is not of much help in this case.
My question is, how many simulated roulette jeu or turns or rounds did it take to get a run of 40 times consecutively the same colour?

My Powershell script was only producing 450,000 spins per minute, and if I remember this right, I’m pretty sure it was under 50 Billion when I saw the 40+ streaks. It was on more than one computer too, I had a 43 streak for the highest ever, and I have 4 computers right now with 42 as their high. I have 2 at 41, and 4 at 40. Others are in the 30s.

I have more PCs running this program than you can guess, so I have a pretty good sampling. :)

it was under 50 Billion when I saw the 40+ streaks

Just to be sure, billion = thousand million. In that case the theory shows for 50 bn the chance of 32 (+/- 2) streaks, so if you encountered 33, 34, even 35 all is fine, with 36 I would say it smells fishy. But 40 and more the likelihood of a poor PRNG is obviously slightly to notedly increased, I guess. At least questionable.
But with probabilities you are never sure when you may experience it, as with verisimilitude of meltdown in nuclear power plants, once in 6000 years (?), alas it could happen today. And the remaining 6000 years you enjoy the silence? No, tomorrow the likeliness is the same as today.
Same with spinning roulettes, it could happen to see 33 times the same colour right at the beginning.

dhayden (5798)

[ edit - fix typo in seed length. See MikeStgt's comment below]
Regarding the PRNG, let me say again that if the PRNG uses a ~~3 bit~~ 32 bit seed then it's likely to have a cycle after around 2^32 calls. If it does that, then it doesn't matter if you call it 4 billion times or 10 quadrillion, you'll still get the same answer because it will cycle through the same set over and over.

Last edited on

what do you want from the result, though.
if you get a streak of 1000 ... well, its possible, but improbable. Does it mean your random numbers are bad, or does it mean that while hunting for statistical anomalies, you found one?
maybe a better test would be to give the stats on all the streaks not just the one biggest. If you had 2 streaks of 1000, what does that mean (is it the above, repeating randoms? Or a bad generator? Or ?). If the above worries you, reseed every 2^30 or so.

Last edited on