bug-gnubg
[Top][All Lists]

## Re: [Bug-gnubg] Rotating rolls in rollout

 From: Douglas Zare Subject: Re: [Bug-gnubg] Rotating rolls in rollout Date: Fri, 4 Oct 2002 15:06:49 -0400 User-agent: Internet Messaging Program (IMP) 3.1

```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

```