Random Numbers

Random Numbers

[Quorlia]

Is there anyway to seed a random number generator with a random value eg
system time or something?

--
 ________________________________________________ _________________________
|                                                |                         |
|  Kirsty Hollingworth                           |  "Forgive my inability  |
|  keh105@york.ac.uk                             |   to communicate, but   |
|  http://www.york.ac.uk/~keh105/                |   there are things you  |
|  http://www.geocities.com/CapeCanaveral/8080/  |   may not understand."  |
|  http://www.plan9.cs.york.ac.uk/usr/keh105/    |   -- Count Iblis        |
|________________________________________________|_________________________|

Re: Random Numbers

[Quorlia]

Quorlia (keh105@york.ac.uk) wrote:
: Is there anyway to seed a random number generator with a random value eg
: system time or something?

Where is the built in random number generator in Ada95 and is it any good?
I only want it to deal random cards for a card game!

--
 ________________________________________________ _________________________
|                                                |                         |
|  Kirsty Hollingworth                           |  "Forgive my inability  |
|  keh105@york.ac.uk                             |   to communicate, but   |
|  http://www.york.ac.uk/~keh105/                |   there are things you  |
|  http://www.geocities.com/CapeCanaveral/8080/  |   may not understand."  |
|  http://www.plan9.cs.york.ac.uk/usr/keh105/    |   -- Count Iblis        |
|________________________________________________|_________________________|

Re: Random Numbers

[Robert Dewar]

Kirsty says

<<Where is the built in random number generator in Ada95 and is it any good?
I only want it to deal random cards for a card game!>>

Get hold of annex A of the RM, it is available online (e.g. go to
www.gnathome.com). Reading the RM can be tricky, but Annex A is relatively
easy going, and will answer this and many other relatd questions.

Re: Random Numbers

[Robert Dewar]

Kirsty asks

<<Is there anyway to seed a random number generator with a random value eg
system time or something?>>

The answer is yes (of course). To get the detailed answer to this and
other questions, you really need to get your hands on Annex A of the 
reference manual which describes this and anything else you might want
to know about the Ada standard library in terms that are quite accessible
(unlike some other parts of the RM, to which I would not refer beginning
Ada programmers!)

You can find a browsable HTML version of the refernce manual at
www.adahome.com, and in many other locations.

Re: Random Numbers

[Robert I. Eachus]

In article <5frk9q$o18@netty.york.ac.uk> keh105@york.ac.uk (Quorlia) writes:

  > Where is the built in random number generator in Ada95 and is it any good?
  > I only want it to deal random cards for a card game!

  Look at a-nuflra.ads and a-nudira.ads in the rts directory, which
are the Gnat names for the standard packages.

     Now for the (bad) news.  Using any random number generator to
shuffle a deck of cards and come up with a random order is
problematical.  It can be done, but there are two issues you need to
keep track of.  One is that the possible number of different states
that you can generate may be much smaller than the number of different
possible hands.  You don't need to generate all cases, but you should
know how far off you are.

     Second is that whatever way you use to shuffle has to choose
cards without replacement.  If you use a different selection rule for
each card, you may lose theoretical properties of the RNG that you are
depending on.  In other words, it may be the case that choosing one of
52, then one of 51, etc. will mean that the generator you are using
will not be very random in practice.  One way that can work is to
assign a (floating point) number to each card then sort.

     Have fun.

--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: Random Numbers

[Doug Smith]

In article <dewar.857912167@merv>, dewar@merv.cs.nyu.edu (Robert Dewar) wrote:

> Kirsty asks
> 
> <<Is there anyway to seed a random number generator with a random value eg
> system time or something?>>
> 
> [snip]
> 
> You can find a browsable HTML version of the refernce manual at
> www.adahome.com, and in many other locations.

And the predefined packages are hyperlinked at:
 <http://sw-eng.falls-church.va.us/cgi-bin/webada/file?template=predefined.html>
or
 <http://sw-eng.falls-church.va.us/AdaIC/compilers/webada/f_predefined.html>

Doug
<mailto:dsmith@clark.net>

Re: Random Numbers

[Jim Balter]

Robert I. Eachus wrote:
> 
> In article <5frk9q$o18@netty.york.ac.uk> keh105@york.ac.uk (Quorlia) writes:
> 
>   > Where is the built in random number generator in Ada95 and is it any good?
>   > I only want it to deal random cards for a card game!
> 
>   Look at a-nuflra.ads and a-nudira.ads in the rts directory, which
> are the Gnat names for the standard packages.
> 
>      Now for the (bad) news.  Using any random number generator to
> shuffle a deck of cards and come up with a random order is
> problematical.  It can be done, but there are two issues you need to
> keep track of.  One is that the possible number of different states
> that you can generate may be much smaller than the number of different
> possible hands.  You don't need to generate all cases, but you should
> know how far off you are.

This is a subtle point that people are likely not to follow.
"states" here means "seed values", i.e., different random sequences.
To produce any possible deck on the first shuffle you need 226 seed
bits.  But you might not care if you can only generate a very small
fraction of the possible decks.  At *most* you only really need enough
seed bits to cover the number of decks that your program might
generate during its lifetime.

>      Second is that whatever way you use to shuffle has to choose
> cards without replacement.  If you use a different selection rule for
> each card, you may lose theoretical properties of the RNG that you are
> depending on.  In other words, it may be the case that choosing one of
> 52, then one of 51, etc. will mean that the generator you are using
> will not be very random in practice.  One way that can work is to
> assign a (floating point) number to each card then sort.

It's not that big a deal (urp).  You can effectively do an insertion
sort with random elements in one pass by simply switching card n with
card  n + floor((52-n) * r)  for n in 0..50,
where r is a random number in [0..1) 

--
<J Q B>

Re: Random Numbers

[Jeff Carter]

Jim Balter wrote:
> It's not that big a deal (urp).  You can effectively do an insertion
> sort with random elements in one pass by simply switching card n with
> card  n + floor((52-n) * r)  for n in 0..50,
> where r is a random number in [0..1)

I handle this simply:

Max_Cards : constant := 52;

subtype Card_Number is Positive range 1 .. Max_Cards;

type Card_Info is ...;

type Deck_Set is array (Card_Number) of Card_Info;

Standard_Deck : constant Deck_Set := ...;

Deck : Deck_Set := Standard_Deck;
Card : Card_Info;
Next_To_Deal : Positive := Deck'First;

package Random is new Ada.Numerics.Discrete_Random (Card_Number);

Gen : Random.Generator;

procedure Swap (Left, Right : in out Card_Info);
-- Postcondition: Left out = Right in and Right out = Left in

Random.Reset (Gen);

Shuffle : for I in Deck'range loop
   Swap (Deck (I), Deck (Random.Random (Gen) ) );
end loop Shuffle;

-- Deal a card

Card := Deck (Next_To_Deal);
Next_To_Deal := Next_To_Deal + 1;

This has the advantage that shuffling is O(N) in time and O(1) in space,
while dealing is O(1) in time and space.
-- 
Jeff Carter
Innovative Concepts, Inc.

Now go away, or I shall taunt you a second time.

Re: Random Numbers

[Robert Dewar]

Robert Eachus said

<<     Now for the (bad) news.  Using any random number generator to
shuffle a deck of cards and come up with a random order is
problematical.  It can be done, but there are two issues you need to
keep track of.  One is that the possible number of different states
that you can generate may be much smaller than the number of different
possible hands.  You don't need to generate all cases, but you should
know how far off you are.

     Second is that whatever way you use to shuffle has to choose
cards without replacement.  If you use a different selection rule for
each card, you may lose theoretical properties of the RNG that you are
depending on.  In other words, it may be the case that choosing one of
52, then one of 51, etc. will mean that the generator you are using
will not be very random in practice.  One way that can work is to
assign a (floating point) number to each card then sort.>>

Don't worry, Robert Eachus is a fanatic here (he wrote the random number
generator) :-)

The orignal questoin came from a student writing a simple card playing
program, and I think you will find that the random number routines
are quite fine for this purpose!

Re: Random Numbers

[Robert Dewar]

Adam says

<<Is this algorithm correct?  I'm suspicious.  The above code generates
a random number between 1 and 52 fifty-two times, meaning that number
of different possibile sequences of random numbers generated is
52**52.  However, the number of possible orderings of a deck is 52!.
This indicates to me that the above code does not generate the
possible deck orderings uniformly (although the discrepancy may be
slight).
>>

Your analysis is correct, and that is exactly what Robert Eachus was
talking about when he noted that this problem is a tricky one to get
exactly right. Of course for practical purposes the quoted algorithm
is probably just fine.

Re: Random Numbers

[Robert I. Eachus]

In article <5g6oqe$63n@wdl1.wdl.lmco.com> mab@dst17.wdl.loral.com (Mark A Biggar) writes:

	   Swap(Deck(I), Deck(some random number in the range 1..I);

   This is a serious mistake in theory, and is often a mistake in
practice.  No random number tests assume different ranges on each call
and to my knowledge no (integer) random number generators exist which
are unbiased in this situation (although the actual bias may be
small).  In effect each time you shuffle you use ONE value from each
of N different generators, each with a different bias.  With the
generator in gnat you are unlikely to get burned.  With an LCG or even
a SWB or an AWC you probably will.

    You might want to test this.  Start with an unshuffled deck each
time and keep a 52x52 array of results.  Basically count the number of
times the first card appears in the first position, etc.  Try runs of
1000 deals, do a chi-square test on each, then do a two-level test on
the distribution of the chi-square results.  Do this with both the
gnat generator and an LCM, and with several of the proposed shuffling
methods. 

   One unbiased algorithm is to assign each card a value from a
generator then sort the values into order and the cards into
randomness.  As long as the generator doesn't produce ties (and most
floating point generators have this property) there is no bias
introduced.  This is the way I do it.  Yes, the sort probably makes
this NlogN for large lists but you know I am a fanatic on the subject.

  > If you look at the 3 card case by hand, then you will find that
  > each possible arangement of cards is generated only once and that
  > all possible arangements are genreated.  The original algorithm
  > above does not have this property.

  The original code could swap a card with itself, or with an earlier
card in the list.  But as long as there are no bugs in the code, the
resulting list is unbiased if the underlying integer generator is
unbiased.  (Unfortunately, it is difficult to produce a discrete
generator that is totally unbiased.  The generator in GNAT does have a
small bias in this case but it is extremely small.  If you run the
generator through an entire cycle of the underlying algorithm, some of
the values in the range 1..52 could appear X times and others X+1,
where X is on the order of one billion.  With the sorting version,
that bias disappears. Told you I'm a fanatic. ;-)

--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: Random Numbers

[Adam Beneschan]

Jeff Carter <carter@innocon.com> writes:
 >
 >I handle this simply:
 >
 >Max_Cards : constant := 52;
 >
 >subtype Card_Number is Positive range 1 .. Max_Cards;
 >
 >type Card_Info is ...;
 >
 >type Deck_Set is array (Card_Number) of Card_Info;
 >
 >Standard_Deck : constant Deck_Set := ...;
 >
 >Deck : Deck_Set := Standard_Deck;
 >Card : Card_Info;
 >Next_To_Deal : Positive := Deck'First;
 >
 >package Random is new Ada.Numerics.Discrete_Random (Card_Number);
 >
 >Gen : Random.Generator;
 >
 >procedure Swap (Left, Right : in out Card_Info);
 >-- Postcondition: Left out = Right in and Right out = Left in
 >
 >Random.Reset (Gen);
 >
 >Shuffle : for I in Deck'range loop
 >   Swap (Deck (I), Deck (Random.Random (Gen) ) );
 >end loop Shuffle;
 >
 >-- Deal a card
 >
 >Card := Deck (Next_To_Deal);
 >Next_To_Deal := Next_To_Deal + 1;
 >
 >This has the advantage that shuffling is O(N) in time and O(1) in space,
 >while dealing is O(1) in time and space.

Is this algorithm correct?  I'm suspicious.  The above code generates
a random number between 1 and 52 fifty-two times, meaning that number
of different possibile sequences of random numbers generated is
52**52.  However, the number of possible orderings of a deck is 52!.
This indicates to me that the above code does not generate the
possible deck orderings uniformly (although the discrepancy may be
slight).

                                -- Adam

Re: Random Numbers

[Robert I. Eachus]

In article <dewar.858098083@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:

  > Don't worry, Robert Eachus is a fanatic here (he wrote the random number
  > generator) :-)

    A fanatic?  A FANATIC?  You dare to call ME a FANATIC on the subject?  

    Well, maybe. ;-)

  > The orignal question came from a student writing a simple card playing
  > program, and I think you will find that the random number routines
  > are quite fine for this purpose!

    Oh, they are probably fine for this purpose, even if not used
correctly.  But I would hope that a student would think about the
issues involved, even if the final decision was to ignore them.
Learning software engineering involves both learning to recognize the
issues, and learning to decide which potential problems can be ignored
in the case at hand.

    For example, my daughter had a similar assignment involving robots
moving one of eight directions in a limited field.  Her action if the
random next move was outside the field was to make a recursive call if
the direction chosen would take the robot out of the field.  Nice
properties from a bias point of view, but...  Her answer to the worst
case scenario was to put in a comment indicating that the risk of
stack overflow had been considered and deemed acceptable in this
environment.

    If I was the instructor who handed out either problem, I'd care
whether students were aware of the issues, not whether they wrote
perfect code for dealing with all the possibilities.  (The card
dealing problem is easy to handle, especially if the game is poker or
blackjack.   In the robot problem, there is a nasty tradeoff between
required stack size and bias.  You set one value and it determines the
other.  Having three generators is a different approach, but now you
have to insure that they are truly independent.)

     More than you probably wanted to know, but as Robert said, I am
somewhat of a fanatic on the subject.  I've never personally gotten
burned by a bad PRNG, or misuse of one, but I know several people who
have.  Withdrawing published papers is no fun, as happened to a friend
of mine who used RANDU.  Even worse was one case where the engineer
involved had to go to the NRC and say the nuclear reactor wasn't as
safe as they thought.  (In fact I don't think the Diablo Canyon
reactor was ever operated.  By the time they fixed the problems that
the wrong simulation had missed, new earthquake faults were found
running directly under the reactor.)

--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: Random Numbers

[Robert I. Eachus]

In article <5g56sj$tqq$1@krusty.irvine.com> adam@irvine.com (Adam Beneschan) writes:

  > Is this algorithm correct?  I'm suspicious.  The above code generates
  > a random number between 1 and 52 fifty-two times, meaning that number
  > of different possibile sequences of random numbers generated is
  > 52**52.  However, the number of possible orderings of a deck is 52!.
  > This indicates to me that the above code does not generate the
  > possible deck orderings uniformly (although the discrepancy may be
  > slight).

    Actually, the number of different deck orderings generated will
depend on the period of the underlying PRNG.  In other words, the
maximum number of different deck orders generated will depend on the
possible different states at the start of the shuffle.  Usually this
will be the number of different possible PRNG states which will be
much, much smaller than 52!.

    You can fix this by using more than one INDEPENDENTLY SEEDED
random number generator.  You can either choose successive values from
different generators, or shuffle with one generator as above then
shuffle again with the second, etc.

     In practice for any card games involving human players, the
number of different possibilities from one generator is enough.  If
you are planning to write a program and run it unattended for weeks to
compare two different playing strategies for say, blackjack, you
probably should use multiple generators.  (Incidently, there are
computer games with junk generators where I find that the ability to
predict the sequence gives me an enormous edge over the computer
player.)

--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: Random Numbers

[Mark A Biggar]

In article <3326BE5D.5076@netcom.com> Jim Balter <jqb@netcom.com> writes:
>Adam Beneschan wrote:
>> Jeff Carter <carter@innocon.com> writes:
>>  >I handle this simply:
>>  >Max_Cards : constant := 52;
>>  >subtype Card_Number is Positive range 1 .. Max_Cards;
>>  >type Card_Info is ...;
>>  >type Deck_Set is array (Card_Number) of Card_Info;
>>  >Standard_Deck : constant Deck_Set := ...;
>>  >Deck : Deck_Set := Standard_Deck;
>>  >Card : Card_Info;
>>  >Next_To_Deal : Positive := Deck'First;
>>  >package Random is new Ada.Numerics.Discrete_Random (Card_Number);
>>  >Gen : Random.Generator;
>>  >procedure Swap (Left, Right : in out Card_Info);
>>  >-- Postcondition: Left out = Right in and Right out = Left in
>>  >Random.Reset (Gen);
>>  >Shuffle : for I in Deck'range loop
>>  >   Swap (Deck (I), Deck (Random.Random (Gen) ) );
>>  >end loop Shuffle;
>>  >-- Deal a card
>>  >Card := Deck (Next_To_Deal);
>>  >Next_To_Deal := Next_To_Deal + 1;
>>  >This has the advantage that shuffling is O(N) in time and O(1) in space,
>>  >while dealing is O(1) in time and space.
>> Is this algorithm correct?  I'm suspicious.  The above code generates
>> a random number between 1 and 52 fifty-two times, meaning that number
>> of different possibile sequences of random numbers generated is
>> 52**52.  However, the number of possible orderings of a deck is 52!.
>> This indicates to me that the above code does not generate the
>> possible deck orderings uniformly (although the discrepancy may be
>> slight).
>Since every position receives exactly the same treatment,
>a symmetry argument indicates a uniform distribution.
>If not, which orderings could be more likely than the others?

The usual algorithm for shuffle is to do something like:

Shuffle: for I in reverse Deck'range loop
	Swap(Deck(I), Deck(some random number in the range 1..I);
end loop Shuffle;

Which can be translated into english as "Build a stack of cards by randoming
picking one of the remaining cards and adding it to the top of the stack".

If you look at the 3 card case by hand, then you will find that each possible 
arangement of cards is generated only once and that all possible arangements 
are genreated.  The original algorithm above does not have this property.

--
Mark Biggar
mab@wdl.lmco.com

Re: Random Numbers

[Jim Balter]

Adam Beneschan wrote:
> 
> Jeff Carter <carter@innocon.com> writes:
>  >
>  >I handle this simply:
>  >
>  >Max_Cards : constant := 52;
>  >
>  >subtype Card_Number is Positive range 1 .. Max_Cards;
>  >
>  >type Card_Info is ...;
>  >
>  >type Deck_Set is array (Card_Number) of Card_Info;
>  >
>  >Standard_Deck : constant Deck_Set := ...;
>  >
>  >Deck : Deck_Set := Standard_Deck;
>  >Card : Card_Info;
>  >Next_To_Deal : Positive := Deck'First;
>  >
>  >package Random is new Ada.Numerics.Discrete_Random (Card_Number);
>  >
>  >Gen : Random.Generator;
>  >
>  >procedure Swap (Left, Right : in out Card_Info);
>  >-- Postcondition: Left out = Right in and Right out = Left in
>  >
>  >Random.Reset (Gen);
>  >
>  >Shuffle : for I in Deck'range loop
>  >   Swap (Deck (I), Deck (Random.Random (Gen) ) );
>  >end loop Shuffle;
>  >
>  >-- Deal a card
>  >
>  >Card := Deck (Next_To_Deal);
>  >Next_To_Deal := Next_To_Deal + 1;
>  >
>  >This has the advantage that shuffling is O(N) in time and O(1) in space,
>  >while dealing is O(1) in time and space.
> 
> Is this algorithm correct?  I'm suspicious.  The above code generates
> a random number between 1 and 52 fifty-two times, meaning that number
> of different possibile sequences of random numbers generated is
> 52**52.  However, the number of possible orderings of a deck is 52!.
> This indicates to me that the above code does not generate the
> possible deck orderings uniformly (although the discrepancy may be
> slight).

Since every position receives exactly the same treatment,
a symmetry argument indicates a uniform distribution.
If not, which orderings could be more likely than the others?

--
<J Q B>

Re: Random Numbers

[Jim Balter]

Mark A Biggar wrote:

> The usual algorithm for shuffle is to do something like:
> 
> Shuffle: for I in reverse Deck'range loop
>         Swap(Deck(I), Deck(some random number in the range 1..I);
> end loop Shuffle;
> 
> Which can be translated into english as "Build a stack of cards by randoming
> picking one of the remaining cards and adding it to the top of the stack".

I gave such an algorithm, but with generating all random numbers
in the range [0..1) to avoid the problems with skew in the generation
of random numbers with integral ranges that Robert Eachus has mentioned.

> If you look at the 3 card case by hand, then you will find that each possible
> arangement of cards is generated only once and that all possible arangements
> are genreated.  The original algorithm above does not have this property.

The swap algorithm that Adam gave does produce permutations uniformly.
This can be shown by a symmetry argument, or by simulating it.
The fact that the target of the swap is 1..52 rather than i..52
does not destroy the uniformity of the distribution.

--
<J Q B>

Re: Random Numbers

[Jim Balter]

Robert Dewar wrote:
> 
> Adam says
> 
> <<Is this algorithm correct?  I'm suspicious.  The above code generates
> a random number between 1 and 52 fifty-two times, meaning that number
> of different possibile sequences of random numbers generated is
> 52**52.  However, the number of possible orderings of a deck is 52!.
> This indicates to me that the above code does not generate the
> possible deck orderings uniformly (although the discrepancy may be
> slight).
> >>
> 
> Your analysis is correct,

Wrong again.

> and that is exactly what Robert Eachus was
> talking about when he noted that this problem is a tricky one to get
> exactly right.

No it isn't.  He was talking about skew in the generation of random
numbers in integer ranges [e.g., in C programs, the common but
faulty #define oneof(n) (rand() % (n)], not about lack of distribution
due to using a range of 1..52 rather than i..52.  Swapping with
any card rather than only with cards not yet examined produces just
as uniform distribution, assuming that the random numbers are truly
uniformly generated.

--
<J Q B>

Re: Random Numbers

[Jim Balter]

Jim Balter wrote:

> The swap algorithm that Adam gave does produce permutations uniformly.

Whoops; that was Jeff Carter, not Adam Beneschan.  Sorry for the mixup.

--
<J Q B>

Re: Random Numbers

[John Briggs, VAX system manager, x4411]

In article <3326BE5D.5076@netcom.com>, Jim Balter <jqb@netcom.com> writes:
> Adam Beneschan wrote:
>> 
>> Jeff Carter <carter@innocon.com> writes:
>>  >
>>  >I handle this simply:
>>  >
>>  >Max_Cards : constant := 52;
>>  >
>>  >subtype Card_Number is Positive range 1 .. Max_Cards;
>>  >
>>  >type Card_Info is ...;
>>  >
>>  >type Deck_Set is array (Card_Number) of Card_Info;
>>  >
>>  >Standard_Deck : constant Deck_Set := ...;
>>  >
>>  >Deck : Deck_Set := Standard_Deck;
>>  >Card : Card_Info;
>>  >Next_To_Deal : Positive := Deck'First;
>>  >
>>  >package Random is new Ada.Numerics.Discrete_Random (Card_Number);
>>  >
>>  >Gen : Random.Generator;
>>  >
>>  >procedure Swap (Left, Right : in out Card_Info);
>>  >-- Postcondition: Left out = Right in and Right out = Left in
>>  >
>>  >Random.Reset (Gen);
>>  >
>>  >Shuffle : for I in Deck'range loop
>>  >   Swap (Deck (I), Deck (Random.Random (Gen) ) );
>>  >end loop Shuffle;
>>  >
>>  >-- Deal a card
>>  >
>>  >Card := Deck (Next_To_Deal);
>>  >Next_To_Deal := Next_To_Deal + 1;
>>  >
>>  >This has the advantage that shuffling is O(N) in time and O(1) in space,
>>  >while dealing is O(1) in time and space.
>> 
>> Is this algorithm correct?  I'm suspicious.  The above code generates
>> a random number between 1 and 52 fifty-two times, meaning that number
>> of different possibile sequences of random numbers generated is
>> 52**52.  However, the number of possible orderings of a deck is 52!.
>> This indicates to me that the above code does not generate the
>> possible deck orderings uniformly (although the discrepancy may be
>> slight).
> 
> Since every position receives exactly the same treatment,
> a symmetry argument indicates a uniform distribution.
> If not, which orderings could be more likely than the others?
> 
> --
> <J Q B>

Re: Random Numbers

[Robert Dewar]

Jim Balter says

<<The swap algorithm that Adam gave does produce permutations uniformly.
This can be shown by a symmetry argument, or by simulating it.
The fact that the target of the swap is 1..52 rather than i..52
does not destroy the uniformity of the distribution.>>

I trust though that, after reading Rober Eachus very nice post yesterday,
you understand the basic point that one is dependent on the underlying
cycle of the random number generator. If it is not large enough, then
you cannot help introducing bias into the selection of hands (not enough
to matter in practice most of the time, but you cannot in any easy way
produce a completely uniform distribution).

Re: Random Numbers

[Robert I. Eachus]

In article <3327A7C4.2C07@netcom.com> Jim Balter <jqb@netcom.com> writes:

  > > and that is exactly what Robert Eachus was talking about when he
  > > noted that this problem is a tricky one to get exactly right.

  > No it isn't.  He was talking about skew in the generation of random
  > numbers in integer ranges [e.g., in C programs, the common but
  > faulty #define oneof(n) (rand() % (n)], not about lack of distribution
  > due to using a range of 1..52 rather than i..52.

  Why don't you let me decide what I was talking about?  I mentioned
two tricky problems, the first was that you won't get all possible
permutations without expending some extra effort (what Robert Dewar
was agreeing with above), the second was the introduction of bias.

  >                                                      Swapping with
  > any card rather than only with cards not yet examined produces just
  > as uniform distribution, assuming that the random numbers are truly
  > uniformly generated.

    And the third, in a separate post, was this common fallacy.
Choosing from a decreasing set of integers using the same underlying
generator can--and often has--produced very non-random results.  The
two level test described in that post is almost certain to "fail" for
any decks generated using an LCG in this way.  Another easier test
that shows the problem is the runs test.  Count the number of runs up
and runs down in a deck prepared in this way.  (Again based on an
underlying LCG, SWB, or AWC generator, haven't tried it with others.)
The length of runs up will exceed the expected, often dramatically,
and the total number of runs, as a result, will be lower.

   Hmmm.  I have a PD version of Montana, a solitaire game on my
computer at home.  It was originally implemented this way.  (I didn't
write it, but I helped the author fix it...)  I'll have to see if I
still have the original source.  In the game, you redeal twice, each
time picking up the cards not in order and redealing them (plus the
Aces) into holes in the tableau.  The initial shuffle is done right,
but the redeals originally had an average of three or four cards
returned to their previous locations.  (A little bit of thinking
should show that in the general case the expectation is one, no matter
how many cards are involved.  In Montana the expectation is either
slightly above or below that depending on how you count the location
of the Aces which are immediately removed.  I'm excluding the
Aces/holes, so the expectation should always be less than one.)  This
is not a small, subtle error, this was gross and very noticable.


--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: Random Numbers

[Adam Beneschan]

In article <3326BE5D.5076@netcom.com> Jim Balter <jqb@netcom.com> writes:
 >Adam Beneschan wrote:
 >> 
 >> Jeff Carter <carter@innocon.com> writes:
 >>  >
 >>  >I handle this simply:
 >>  >
 >>  >Max_Cards : constant := 52;
 >>  >
 >>  >subtype Card_Number is Positive range 1 .. Max_Cards;
 >>  >
 >>  >type Card_Info is ...;
 >>  >
 >>  >type Deck_Set is array (Card_Number) of Card_Info;
 >>  >
 >>  >Standard_Deck : constant Deck_Set := ...;
 >>  >
 >>  >Deck : Deck_Set := Standard_Deck;
 >>  >Card : Card_Info;
 >>  >Next_To_Deal : Positive := Deck'First;
 >>  >
 >>  >package Random is new Ada.Numerics.Discrete_Random (Card_Number);
 >>  >
 >>  >Gen : Random.Generator;
 >>  >
 >>  >procedure Swap (Left, Right : in out Card_Info);
 >>  >-- Postcondition: Left out = Right in and Right out = Left in
 >>  >
 >>  >Random.Reset (Gen);
 >>  >
 >>  >Shuffle : for I in Deck'range loop
 >>  >   Swap (Deck (I), Deck (Random.Random (Gen) ) );
 >>  >end loop Shuffle;
 >>  >
 >>  >-- Deal a card
 >>  >
 >>  >Card := Deck (Next_To_Deal);
 >>  >Next_To_Deal := Next_To_Deal + 1;
 >>  >
 >>  >This has the advantage that shuffling is O(N) in time and O(1) in space,
 >>  >while dealing is O(1) in time and space.
 >> 
 >> Is this algorithm correct?  I'm suspicious.  The above code generates
 >> a random number between 1 and 52 fifty-two times, meaning that number
 >> of different possibile sequences of random numbers generated is
 >> 52**52.  However, the number of possible orderings of a deck is 52!.
 >> This indicates to me that the above code does not generate the
 >> possible deck orderings uniformly (although the discrepancy may be
 >> slight).
 >
 >Since every position receives exactly the same treatment,
 >a symmetry argument indicates a uniform distribution.
 >If not, which orderings could be more likely than the others?

You don't have to know which orderings are more likely; there's a
simple "existence proof" that shows that some orderings must be more
likely than others.  It goes like this: Suppose we run the above
algorithm 52**52 times; each run of the algorithm produces one
ordering.  Now, you're claiming that each ordering will occur the same
number of times.  Call this number N.  Since there are 52! possible
orderings, this means that 52! * N = 52**52.

However, there is no such integer N, since 52! is not a divisor of
52**52.  Therefore, it follows that the orderings cannot be generated
uniformly. 

Try it with Max_Cards = 3, so that there are 27 possible random number
sequences (3 random numbers generated, each one in 1..3) and 6
possible orderings.  Try running all possible 27 sequences, and look
at the resulting distributions of Deck.  I did try it, with Deck's
initial value being (1,2,3), and here are my results:
      
      1, 2, 3     4 times
      1, 3, 2     5 times
      2, 1, 3     5 times
      2, 3, 1     5 times
      3, 1, 2     4 times
      3, 2, 1     4 times
      -------     -------
                  27

Not only is the distribution non-uniform (it must be, since 6 doesn't
divide 27), but the three positions in the deck aren't treated
equally.  For example, the probability that Deck(I) = I [assume Deck's
index range is 1..3] is not the same for each position.  The number 1
stays in its original spot 9 times, as does the number 3; but the
number 2 only stays there 8 times.  So there must be some flaw in the
symmetry argument, although I haven't delved into it to figure out
what that flaw is.

The interesting question, for me, would be: if you use Jeff's
algorithm on 52 cards, the distribution will not be exactly
uniform---but how close will it be?  I'm pretty lame when it comes to
statistics, so someone else will have to figure out how "close" the
algorithm comes to uniform, and whether that's close enough for
practical purposes (if, say, you were using a computer to pre-deal
cards for a large bridge tournament).

                                -- Adam

Re: Random Numbers

[John Briggs, VAX system manager, x4411]

In article <3327A666.1FCD@netcom.com>, Jim Balter <jqb@netcom.com> writes:

> The swap algorithm that Adam gave does produce permutations uniformly.
> This can be shown by a symmetry argument, or by simulating it.
> The fact that the target of the swap is 1..52 rather than i..52
> does not destroy the uniformity of the distribution.

Yes, it does destroy the uniformity.
As can be shown by simulating it.
All available symmetry arguments are bogus.

	John Briggs			vaxs09@alpha.vitro.com

Re: Random Numbers

[Jeff Carter]

Robert I. Eachus wrote:
> 
> In article <3327A7C4.2C07@netcom.com> Jim Balter <jqb@netcom.com> writes:
> 
>   > > and that is exactly what Robert Eachus was talking about when he
>   > > noted that this problem is a tricky one to get exactly right.
> 
>   > No it isn't.  He was talking about skew in the generation of random
>   > numbers in integer ranges [e.g., in C programs, the common but
>   > faulty #define oneof(n) (rand() % (n)], not about lack of distribution
>   > due to using a range of 1..52 rather than i..52.
> 
>   Why don't you let me decide what I was talking about?  I mentioned
> two tricky problems, the first was that you won't get all possible
> permutations without expending some extra effort (what Robert Dewar
> was agreeing with above), the second was the introduction of bias.
> 
>   >                                                      Swapping with
>   > any card rather than only with cards not yet examined produces just
>   > as uniform distribution, assuming that the random numbers are truly
>   > uniformly generated.
> 
>     And the third, in a separate post, was this common fallacy.
> Choosing from a decreasing set of integers using the same underlying
> generator can--and often has--produced very non-random results.  The
> two level test described in that post is almost certain to "fail" for
> any decks generated using an LCG in this way.  Another easier test
> that shows the problem is the runs test.  Count the number of runs up
> and runs down in a deck prepared in this way.  (Again based on an
> underlying LCG, SWB, or AWC generator, haven't tried it with others.)
> The length of runs up will exceed the expected, often dramatically,
> and the total number of runs, as a result, will be lower.
> 
>    Hmmm.  I have a PD version of Montana, a solitaire game on my
> computer at home.  It was originally implemented this way.  (I didn't
> write it, but I helped the author fix it...)  I'll have to see if I
> still have the original source.  In the game, you redeal twice, each
> time picking up the cards not in order and redealing them (plus the
> Aces) into holes in the tableau.  The initial shuffle is done right,
> but the redeals originally had an average of three or four cards
> returned to their previous locations.  (A little bit of thinking
> should show that in the general case the expectation is one, no matter
> how many cards are involved.  In Montana the expectation is either
> slightly above or below that depending on how you count the location
> of the Aces which are immediately removed.  I'm excluding the
> Aces/holes, so the expectation should always be less than one.)  This
> is not a small, subtle error, this was gross and very noticable.
> 
> --
> 
>                                         Robert I. Eachus
> 
> with Standard_Disclaimer;
> use  Standard_Disclaimer;
> function Message (Text: in Clever_Ideas) return Better_Ideas is...

Thanks to Robert for providing an example of when my simple shuffling
algorithm fails to be "random enough." I have used it for several games in
which the deck is shuffled once per game without any noticable effect. I have
also used it for a blackjack game in which the deck is reshuffled when
exhausted without noticable effect. I presume this is because I never play
long enough to shuffle more than a tiny fraction of the 52! possible
combinations. Clearly, if one is doing a massive simulation of card games,
the extensive analysis discussed in this thread is appropriate.

And now, for your reading enjoyment, I enclose (with his permission) an email
reply from Robert to a message I sent him by accident when I intended to post
it here:

  > Since you are a self-confessed fanatic with more knowledge than me on
  > the subject, perhaps you would comment on the following idea for
  > generating a random integer in a given range, given a floting-point
  > random number:

   First, the "right" way to do this in Ada is to instantiate
Ada.Numerics.Discrete_Random, but let's assume for now you are either
writing this package, or need something special that the standard
doesn't provide. ;-)

[I was thinking of a tight loop that needs to generate a number in a
different range each time. One might not want to instantiate Discrete_Random
each time through the loop. -- JC]

  > Given r, a random value in [0, 1)
  >    i and j, integers, i <= j

  > Use |_r(j+1-i)+i_|

  This works given the condition above.  But there is a fun trick that
I use which works even if r can effectively be equal to one.  (I could
go into the pages of gory detail of which (legal) values of r less
than one can give a value r*k that compares equal to k for different
small values of k.  But don't worry about it.)

  Use:

  return Integer_Type(R*(j-i+1)) mod (j-i+1) + i;

  (Actually you want to precalulate the range value (j-i+1) ahead of
time.)  Notice that some large values of R will result in a return
value of i, but that's okay.  In fact with many generators such as
LCGs it produces a better sequence.  Start with two adjacent values of
R, you will generate similar sequences with an underlying LCG.  If you
use this tranformation, those "matching" sequences will be shorter.

  > The naive approach is to use round(r*float(j-i))+i, but this is biased
  > against the end points (if j>i+1). The approach above seems to eliminate
  > that bias.

  Yes it is.  You can fix it by using the mod operation as above, or
just do:

   k := round(r*float(j-i+1))+i);
   if k > j then k := i; end if;
   return k;

   Which is faster will depend on the underlying hardware.


                                        Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

-- 
Jeff Carter
Innovative Concepts, Inc.

Now go away, or I shall taunt you a second time.

Unsolicited commercial e-mail will be invoiced at US $500 per piece.

Re: Random Numbers

[Joel VanLaven]

Adam Beneschan (adam@irvine.com) wrote:
: Jeff Carter <carter@innocon.com> writes:
[code snipped]

: Is this algorithm correct?  I'm suspicious.  The above code generates
: a random number between 1 and 52 fifty-two times, meaning that number
: of different possibile sequences of random numbers generated is
: 52**52.  However, the number of possible orderings of a deck is 52!.
: This indicates to me that the above code does not generate the
: possible deck orderings uniformly (although the discrepancy may be
: slight).

:                                 -- Adam

Right you are to be suspicious.  Take a simpler case, a deck of three
cards.  This algorithm has 27 possible sequences and 6 possible card
states.  there is no way each card state happens with the same frequency.
These are the probabilities for where the last card shows up in the
shuffled deck:
1st: 8/27
2nd: 10/27
3rd: 1/3

For a 52 card deck.  The probability that the last card will be in the
first position is 1/52 * (51/52)^51 * 2 which comes out to a little less
that 3/4 * 1/52 whereas the probability that it will be in the 51st
position is 1/52 * (51/52 + (51/52)^51) which comes out to a little more
than 4/3 * 1/52.  So, The last card is more than 16/9 (more accurately
1.82 and so on) times as likely to be in the 51st position than in the 1st
position.  All of this is of course based on completely random numbers
being generated.  That seems a lot more problematic then problems with
the random number generator however I suppose a bad enough random number
generator could be worse.
-- 
-- Joel VanLaven

Re: Random Numbers

[Adam Beneschan]

NOTE: In my arguments on this thread, I'm assuming a perfect random
number generator--i.e. not a pseudo.  My argument has been that with
this assumption, the dealer program that Jeff posted isn't really
correct mathematically (although it might be close enough for
practical purposes).  Robert Eachus' points about the effects of a
real-life pseudo-RNG are very important, but not germane to my part of
the discussion.


In article <33294F11.4ADF@netcom.com> Jim Balter <jqb@netcom.com> writes:
 >Adam Beneschan wrote:
 >
 >> You don't have to know which orderings are more likely; there's a
 >> simple "existence proof" that shows that some orderings must be more
 >> likely than others.  It goes like this: Suppose we run the above
 >> algorithm 52**52 times; each run of the algorithm produces one
 >> ordering.  Now, you're claiming that each ordering will occur the same
 >> number of times.
 >
 >No, of course not, only that they occur the same number of times
 >*on average*.
 
Mea culpa---I misstated what I meant to say.  That should be:

Suppose we run the above algorithm 52**52 times, ONCE FOR EACH
POSSIBLE SEQUENCE OF RANDOM NUMBERS.  That is, we're not using the
random number generator any more.  Jeff's program generated a random
number from 1 to 52, and he did this 52 times.  So there are 52**52
possible sequences of random numbers generated in his algorithm.  Now,
imagine that we simply took all of these 52**52 sequences and used
Jeff's algorithm on each one in turn, without using the random number
generator.  Each run of the algorithm produces one ordering of the
deck.  Since there are 52! possible orderings of the deck, and since
52! doesn't divide 52**52, it follows that some orderings will occur
more than others.

What I'm claiming is that this computation *is* relevant to the
situation when you ARE using a pure random number generator.  To see
this, I'm going to go back to the 3-card example.  In this case,
Jeff's algorithm generates 3 random numbers, each from 1 to 3; so
there are 27 different sequences.  That is, (1,1,1), (1,1,2), (1,1,3),
(1,2,1), etc.---you get the picture.  When you use Jeff's algorithm on
all 27 sequences in turn, i.e. without using the random number
generator, the resulting deck orderings are distributed as follows:
 
 (a)   1, 2, 3     4 times
 (b)   1, 3, 2     5 times
 (c)   2, 1, 3     5 times
 (d)   2, 3, 1     5 times
 (e)   3, 1, 2     4 times
 (f)   3, 2, 1     4 times
       -------     -------
                   27
 
Now say we put the random number generator back in, and run the
algorithm about 27 trillion times.  Since this is a pure random number
generator, we can expect that the twenty-seven different sequences are
generated approximately the same number of times.  There is, of
course, no guarantee; but I'm talking about the EXPECTED value that
can be computed mathematically, and in this case, we can expect that
each sequence will be generated 1 trillion times.  This means that, if
each different sequence is generated one trillion times, the
distributions of the results, that I listed in the table above, will
each be multiplied by one trillion.  Thus: Since there are 4 random
sequences that produce the deck ordering (a), and each random sequence
can be expected to be generated one trillion times, we can expect that
the result will be (a) four trillion times.  Similarly, we can expect
that the deck ordering will be (b) five trillion times.

This means that, if we use Jeff's algorithm, we can expect that the
result will be (b) 25% more than it will be (a), on average.  This is
proof that the algorithm is not mathematically correct---the results
are not distributed uniformly.

Of course, with numbers this small, the differences (25% in this case)
will be much greater.  If we were to do it with 52 cards, we would run
the algorithm on 52**52 different sequences, and there are 52!
orderings.  If I produced a table similar to the one above, with all
52! deck orderings and the number of times they would be produced by
this algorithm, the number of occurrences for each deck ordering would
be approximately (52**52 / 52!), which is about 2.1 * 10**21 (quick
computation using Stirling's formula).  Obviously, if the differences
between the distributions are just 1 (as they are in the above table)
or some other very small number, the distributions of the results will
not be uniform but they will be extremely close.  However, this is the
part I have no idea about---how close are they?  That's what I was
asking about in my final question.

 >Answering this question would show you where your error is.
 >Jeff's algorithm will be uniform for a number of deals equal to
 >the greatest multiple of 52! < 52**52, and for the least multiple of  
 >52! > 52**52.  The "error" for n deals is (n mod 52!)/n, for Jeff's
 >algorithm or any other uniform algorithm.  

Right.  But Jeff's algorithm is not a uniform algorithm.  It is
probably close enough to uniform for practical purposes, when the
number of cards is large enough.  In fact, some of Robert's statements
seem to indicate that, when used with a real pseudo-RNG, Jeff's
algorithm may generate a closer-to-uniform distribution than the
"mathematically correct" one of generating a number 1..52, then 1..51,
then 1..50 and so on.  But my argument here has been primarily about
mathematical correctness.

                                -- Adam

Re: Random Numbers

[Robert I. Eachus]

In article <5g9j0e$q0b$1@krusty.irvine.com> adam@irvine.com (Adam Beneschan) writes:

  > You don't have to know which orderings are more likely; there's a
  > simple "existence proof" that shows that some orderings must be more
  > likely than others.  It goes like this: Suppose we run the above
  > algorithm 52**52 times; each run of the algorithm produces one
  > ordering.  Now, you're claiming that each ordering will occur the same
  > number of times.  Call this number N.  Since there are 52! possible
  > orderings, this means that 52! * N = 52**52.

  > However, there is no such integer N, since 52! is not a divisor of
  > 52**52.  Therefore, it follows that the orderings cannot be generated
  > uniformly. 

   Excellent existance proof.

  I had said:

  >   The original code could swap a card with itself, or with an earlier
  > card in the list.  But as long as there are no bugs in the code, the
  > resulting list is unbiased if the underlying integer generator is
  > unbiased. 

  I stand corrected, there is an unavoidable bias in this case.  For
fifty-two card decks it will be significantly less that that due to
any generator which maps a larger set of values to a small set of
integers.  But for very small decks:

  > Try it with Max_Cards = 3, so that there are 27 possible random
  > number sequences (3 random numbers generated, each one in 1..3)
  > and 6 possible orderings.  Try running all possible 27 sequences,
  > and look at the resulting distributions of Deck...

  ...the bias is not only theoretically noticeable, but will be easily
detected in practice.  So I will recommend again, if you want to
shuffle a deck of cards, do it like this:

   (quoted from the package ADAR_Statistics and reformated...)

   procedure Shuffling (List: in out List_Type; Gen: in Generator) is
      List_Copy : constant List_Type := List;
      type Rec is record Index: Index_Type; Rand: Float; end record;
      type Rec_Array is array (Index_Type range <>) of Rec;
      Temp : Rec_Array(List'Range);
      function "<" (L, R: Rec) return Boolean is
      begin return L.Rand < R.Rand; end "<";
      procedure Sort is new Sorting(Rec, Index_Type, Rec_Array, "<");
   
    begin
      for I in Temp'Range loop Temp(I) := (I, NFR.Random(Gen)); end loop;
      Sort(Temp);  -- Sort based on value of random number
      -- Now rearrange List based on the order of indices in Temp
      for I in List'Range loop List(I) := List_Copy(Temp(I).Index); end loop;
    end Shuffling;
--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: Random Numbers

[Jon S Anthony]

In article <5g9j0e$q0b$1@krusty.irvine.com> adam@irvine.com (Adam Beneschan) writes:

>  >Since every position receives exactly the same treatment,
>  >a symmetry argument indicates a uniform distribution.
>  >If not, which orderings could be more likely than the others?
> 
> You don't have to know which orderings are more likely; there's a
> simple "existence proof" that shows that some orderings must be more
          ^^^^^^^^^ reductio
> likely than others.  It goes like this: Suppose we run the above
> algorithm 52**52 times; each run of the algorithm produces one
> ordering.  Now, you're claiming that each ordering will occur the same
> number of times.  Call this number N.  Since there are 52! possible
> orderings, this means that 52! * N = 52**52.
>
> However, there is no such integer N, since 52! is not a divisor of
> 52**52.

[as there are all sorts of primes in it while 52 only has 2 and 13]

> Therefore, it follows that the orderings cannot be generated
> uniformly.

Nicely done.

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Random Numbers

[Jim Balter]

Robert I. Eachus wrote:
> 
> In article <3327A7C4.2C07@netcom.com> Jim Balter <jqb@netcom.com> writes:
> 
>   > > and that is exactly what Robert Eachus was talking about when he
>   > > noted that this problem is a tricky one to get exactly right.
> 
>   > No it isn't.  He was talking about skew in the generation of random
>   > numbers in integer ranges [e.g., in C programs, the common but
>   > faulty #define oneof(n) (rand() % (n)], not about lack of distribution
>   > due to using a range of 1..52 rather than i..52.
> 
>   Why don't you let me decide what I was talking about?  I mentioned
> two tricky problems, the first was that you won't get all possible
> permutations without expending some extra effort (what Robert Dewar
> was agreeing with above), the second was the introduction of bias.

You said:

"The original code could swap a card with itself, or with an earlier
card in the list.  But as long as there are no bugs in the code, the
resulting list is unbiased if the underlying integer generator is
unbiased."

which contradicts Robert Dewar and agrees with me.  Robert Dewar
was agreeing with Adam Beneschan, with whom you were disagreeing
in the above quote.  You can't have it both ways.


>   >                                                      Swapping with
>   > any card rather than only with cards not yet examined produces just
>   > as uniform distribution, assuming that the random numbers are truly
>   > uniformly generated.
> 
>     And the third, in a separate post, was this common fallacy.
> Choosing from a decreasing set of integers using the same underlying

There was no choosing from a decreasing set of integers;
every choice was from 1..52.  I agreed with what I quoted from you
immediately above.  You can't have it both ways.

--
<J Q B>

Re: Random Numbers

[Jim Balter]

Robert Dewar wrote:
> 
> Jim Balter says
> 
> <<The swap algorithm that Adam gave does produce permutations 

[that should be Jeff Carter]

> uniformly.
> This can be shown by a symmetry argument, or by simulating it.
> The fact that the target of the swap is 1..52 rather than i..52
> does not destroy the uniformity of the distribution.>>
> 
> I trust though that, after reading Rober Eachus very nice post yesterday,
> you understand the basic point that one is dependent on the underlying
> cycle of the random number generator. If it is not large enough, then
> you cannot help introducing bias into the selection of hands (not enough
> to matter in practice most of the time, but you cannot in any easy way
> produce a completely uniform distribution).

Yes, but that isn't the point here.  I have already noted and elaborated
on *that* point several times.  But I don't trust that a clear 
understanding of my posts will ensue.

[Adam Beneschan]
  > If you look at the 3 card case by hand, then you will find that
  > each possible arangement of cards is generated only once and that
  > all possible arangements are genreated.  The original algorithm
  > above does not have this property.

[Robert Eachan]
  The original code could swap a card with itself, or with an earlier
card in the list.  But as long as there are no bugs in the code, the
resulting list is unbiased if the underlying integer generator is
unbiased. 

--
<J Q B>

Re: Random Numbers

[Jim Balter]

Adam Beneschan wrote:

> You don't have to know which orderings are more likely; there's a
> simple "existence proof" that shows that some orderings must be more
> likely than others.  It goes like this: Suppose we run the above
> algorithm 52**52 times; each run of the algorithm produces one
> ordering.  Now, you're claiming that each ordering will occur the same
> number of times.

No, of course not, only that they occur the same number of times
*on average*.

> Call this number N.  Since there are 52! possible
> orderings, this means that 52! * N = 52**52.

This is totally ad hoc.  Of course, since 52**52 is not a multiple
of 52!, then that number of deals won't come out even, but the
next even multiple of 52! will.
 
> However, there is no such integer N, since 52! is not a divisor of
> 52**52.  Therefore, it follows that the orderings cannot be generated
> uniformly.

No, this is just wrong.  It's like saying that, if you only deal
once, the deal isn't uniform, because the results didn't all
occur equally as many times.  That's silly, since every possible
algorithm, including the ones you do think are uniform, won't produce
equal results for numbers of deals that aren't multiples of 52!.

> Try it with Max_Cards = 3, so that there are 27 possible random number
> sequences (3 random numbers generated, each one in 1..3) and 6
> possible orderings.  Try running all possible 27 sequences, and look
> at the resulting distributions of Deck.  I did try it, with Deck's
> initial value being (1,2,3), and here are my results:
> 
>       1, 2, 3     4 times
>       1, 3, 2     5 times
>       2, 1, 3     5 times
>       2, 3, 1     5 times
>       3, 1, 2     4 times
>       3, 2, 1     4 times
>       -------     -------
>                   27

*No* method will produce equal outcomes for 27 deals!
But that's not relevant to anything.  It would have come out even
for either 24 deals or 30 deals.

> Not only is the distribution non-uniform (it must be, since 6 doesn't
> divide 27), but the three positions in the deck aren't treated
> equally.  For example, the probability that Deck(I) = I [assume Deck's
> index range is 1..3] is not the same for each position.  The number 1
> stays in its original spot 9 times, as does the number 3; but the
> number 2 only stays there 8 times.  So there must be some flaw in the
> symmetry argument, although I haven't delved into it to figure out
> what that flaw is.
> 
> The interesting question, for me, would be: if you use Jeff's
> algorithm on 52 cards, the distribution will not be exactly
> uniform---but how close will it be?  I'm pretty lame when it comes to
> statistics,

It's good to keep that in mind.

> so someone else will have to figure out how "close" the
> algorithm comes to uniform, and whether that's close enough for
> practical purposes (if, say, you were using a computer to pre-deal
> cards for a large bridge tournament).

Answering this question would show you where your error is.
Jeff's algorithm will be uniform for a number of deals equal to
the greatest multiple of 52! < 52**52, and for the least multiple of  
52! > 52**52.  The "error" for n deals is (n mod 52!)/n, for Jeff's
algorithm or any other uniform algorithm.  All you are dealing with
here is that fact that not all rational numbers are integers.

--
<J Q B>

Re: Random Numbers

[Jim Balter]

Robert I. Eachus wrote:
> 
> In article <5g9j0e$q0b$1@krusty.irvine.com> adam@irvine.com (Adam Beneschan) writes:
> 
>   > You don't have to know which orderings are more likely; there's a
>   > simple "existence proof" that shows that some orderings must be more
>   > likely than others.  It goes like this: Suppose we run the above
>   > algorithm 52**52 times; each run of the algorithm produces one
>   > ordering.  Now, you're claiming that each ordering will occur the same
>   > number of times.  Call this number N.  Since there are 52! possible
>   > orderings, this means that 52! * N = 52**52.
> 
>   > However, there is no such integer N, since 52! is not a divisor of
>   > 52**52.  Therefore, it follows that the orderings cannot be generated
>   > uniformly.
> 
>    Excellent existance proof.

The same "proof" applies to *any* dealing algorithm.  You can't
distribute 52! different permutations evenly into 52**52 slots.
Why you guys think this is relevant, I don't know, but I won't
argue it further; you are free to mislead yourselves.

--
<J Q B>

Re: Random Numbers

[Jim Balter]

Adam Beneschan wrote:
> 
> NOTE: In my arguments on this thread, I'm assuming a perfect random
> number generator--i.e. not a pseudo.  My argument has been that with
> this assumption, the dealer program that Jeff posted isn't really
> correct mathematically (although it might be close enough for
> practical purposes).  Robert Eachus' points about the effects of a
> real-life pseudo-RNG are very important, but not germane to my part of
> the discussion.

Yes, I tried to make this point elsewhere; thanks for keeping it clear.

> What I'm claiming is that this computation *is* relevant to the
> situation when you ARE using a pure random number generator.  To see
> this, I'm going to go back to the 3-card example.  In this case,
> Jeff's algorithm generates 3 random numbers, each from 1 to 3; so
> there are 27 different sequences.  That is, (1,1,1), (1,1,2), (1,1,3),
> (1,2,1), etc.---you get the picture.  When you use Jeff's algorithm on
> all 27 sequences in turn, i.e. without using the random number
> generator, the resulting deck orderings are distributed as follows:
> 
>  (a)   1, 2, 3     4 times
>  (b)   1, 3, 2     5 times
>  (c)   2, 1, 3     5 times
>  (d)   2, 3, 1     5 times
>  (e)   3, 1, 2     4 times
>  (f)   3, 2, 1     4 times
>        -------     -------
>                    27
> 
> Now say we put the random number generator back in, and run the
> algorithm about 27 trillion times.  Since this is a pure random number
> generator, we can expect that the twenty-seven different sequences are
> generated approximately the same number of times.

Ok, I finally (duhhh) get it.

Point well made.

> Of course, with numbers this small, the differences (25% in this case)
> will be much greater.  If we were to do it with 52 cards, we would run
> the algorithm on 52**52 different sequences, and there are 52!
> orderings.  If I produced a table similar to the one above, with all
> 52! deck orderings and the number of times they would be produced by
> this algorithm, the number of occurrences for each deck ordering would
> be approximately (52**52 / 52!), which is about 2.1 * 10**21 (quick
> computation using Stirling's formula).  Obviously, if the differences
> between the distributions are just 1 (as they are in the above table)
> or some other very small number, the distributions of the results will
> not be uniform but they will be extremely close.  However, this is the
> part I have no idea about---how close are they?  That's what I was
> asking about in my final question.

Well, I ran it up to 8 cards and got outcomes that occurred anywhere
from (.3 * 8**8 / 8!) to (4.6 * 8**8 / 8!) times, so it looks rather
skewed, but I haven't attempted to actually do a formal calculation.

> In fact, some of Robert's statements
> seem to indicate that, when used with a real pseudo-RNG, Jeff's
> algorithm may generate a closer-to-uniform distribution than the
> "mathematically correct" one of generating a number 1..52, then 1..51,
> then 1..50 and so on.

One has to be careful how one generates such numbers.  My original post
on this subject, to which Jeff Carter's code was a response, gave

  You can effectively do an insertion
  sort with random elements in one pass by simply switching card n with
  card  n + floor((52-n) * r)  for n in 0..50,
  where r is a random number in [0..1) 

I should have stuck with that line instead of erroneously defending
Jeff's algorithm.

The latest from Robert Eachus, via Jeff Carter, takes care of problems
with r = 1 or r < 1 but r*k = k by applying an additional mod:

	return Integer_Type(R*(j-i+1)) mod (j-i+1) + i;

> But my argument here has been primarily about
> mathematical correctness.

Again, point well made.

--
<J Q B>

Re: Random Numbers

[Robert I. Eachus]

In article <1997Mar14.165015.11917@ocsystems.com> jvl@ocsystems.com (Joel VanLaven) writes:

  > Right you are to be suspicious.  Take a simpler case, a deck of three
  > cards.  This algorithm has 27 possible sequences and 6 possible card
  > states.  there is no way each card state happens with the same frequency...

  > For a 52 card deck.  The probability that the last card will be in the
  > first position is 1/52 * (51/52)^51 * 2 which comes out to a little less
  > that 3/4 * 1/52 whereas the probability that it will be in the 51st
  > position is 1/52 * (51/52 + (51/52)^51) which comes out to a little more
  > than 4/3 * 1/52.  So, The last card is more than 16/9 (more accurately
  > 1.82 and so on) times as likely to be in the 51st position than in the 1st
  > position.  All of this is of course based on completely random numbers
  > being generated.  That seems a lot more problematic then problems with
  > the random number generator however I suppose a bad enough random number
  > generator could be worse.

   I doubt it.  I had never analyzed this method in detail, but I just
wrote a short program to get the skinny...

   For N = 2, no problem, for N = 3 the distribution has already been
discussed: 

     4     5     5     5     4     4

   For N = 4 it gets worse:

    10    10    10    14    11     9    10    15    14    14    11    11
    11    11     9    11    11    10     8     9     9     8    10    10

   15/8 is almost 2 to 1!

    Now to N = 5:

    47/18 almost 3 to 1!

    26    26    26    28    22    24    26    27    28    42    32    25
    22    32    24    25    23    30    23    20    20    22    30    22
    26    27    27    47    37    25    28    47    42    42    33    33
    32    32    25    32    35    30    23    27    25    22    29    30
    22    37    32    33    25    26    24    25    25    33    26    22
    23    35    30    30    26    28    29    21    23    24    30    27
    23    23    20    25    29    23    20    27    22    22    21    24
    30    29    22    30    30    27    23    23    23    19    19    22
    16    20    18    18    21    25    20    18    18    20    25    20
    21    25    25    20    28    28    22    21    21    22    22    18

    I'll skip the data for N=6 but the range is 32 to 159 almost 5 to
1!  Now when N gets sufficiently large and N!  is greater than the
period of the random number generator, then the generator itself will
cause some permutations not to appear at all.  But this is BAD.  How
about it Joel (and anyone else following this), who wants to work on
making this into a paper.  We know the right method, and at least two
wrong methods...

--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: Random Numbers

[Jon S Anthony]

In article <EACHUS.97Mar14162152@spectre.mitre.org> eachus@spectre.mitre.org (Robert I. Eachus) writes:

>    Excellent existance proof.

Ummm, you mean *non*existence (making it a reductio proof - and a nice
one).

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com