Re: [Bug-gnubg] Rotating rolls in rollout

[Douglas Zare]

Quoting Jim Segrave <address@hidden>:

> On Fri 04 Oct 2002 (15:19 +0200), address@hidden wrote:
> > That is not a good randomization strategy. You should do
> > 
> > For i = 0 to 1295
> >  create random j between i and 1295
> >  swap array[i] and array[j]
> > Next
> > 
> > Then by a simple proof by induction, the array is as random as your random
> 
> > numbers.
> 
> I suspect both methods will produce similar levels of randomisation. I
> can't see that there is an inherent advantage of one over the
> other. Do you have reason to think differently? I'm not trying to be
> defensive, I'm just curious.

Yes, this is a well-known issue, and what Nis proposes is the standard 
solution. Among the ways to see that yours does not work, count the average 
number of elements that remain in their initial positions by your method. You 
should get several hundred, meaning at least that many fixed points of the 
permutation. (There is a small additional chance that something will be moved 
multiple times and end up in the original position.) The average number of 
fixed points of a uniformly chosen random permutation is 1.
 
> > This does not, however, provide the maximum stratification if the number of
> 
> > trials is not a multiple of 1296. 

More relevantly, it doesn't provide maximum stratification if the number of 
trials is, say, 288. In fact, there would be little benefit at all from this 
scheme, unlike if you make the first rolls cycle every 36, and avoid repeating 
the second rolls. There are some kluges you could use with one or two random 
permutations of 36 elements, but you could do something more sophisticated with 
37 random permutations of 36 elements, which would not require more of the 
processor than one random permutation of 1296.

> >Thus I would prefer to put a little more
> 
> > effort into creating the array of rolls. My best idea so far is to cycle 
> > the first roll through the same sequence of 36 rolls, and cycling the 
> > second roll through the same sequence, but 'sliding' the sequence before 
> > each sequence of 36. Something like (still pseudocode:
> > 
> > Create array36 containing 11,12,...,66
> > Randomize Rolls36 as described before
> > Create empty array of 1296
> > 
> > for i = 0 to 35
> > for j = 0 to 35
> > array[i*36+j] = (array36[j], array36[i+j mod 36])

I think that will work well most of the time, as long as you are getting a 
random permutation of 36. If not, you may get strange results.

> If the desired result is that for every 36 rollouts, every initial
> roll is present with the probability of that roll, this is a better
> way to do it. But I wonder if it's worth randomising the
> initial roll in that case. Does it gain you anything?

It reduces the bias if you interrupt a rollout after a number of trials not 
divisible by 36, or watch the rollout results as they come in. Suppose 4's hit, 
and the variance reduction is not perfect. You don't want to see a predictably 
low equity, and then suddenly a jump as you run into a bunch of 4's, then low, 
etc. If you do that, it will take much longer for the average square of the 
error at a "random" interruption point to be small.

> > I am not sure about "dropping the initial doubles" during the rollout. I 
> > think rather we should make an array of 30*36 for that case.

Dropping the doubles produces a uniform permutation of the non-doubles if you 
started with a uniform distribution.

Douglas Zare