Beginner Question--rand( )

[Cy Edmunds]

--
Cycho{HHR}
http://home.rochester.rr.com/cyhome/

I find this thread very confusing! What are you trying to say? I ask myself.

For random sequences the only guarentee is that the probability of any
specific number being presented is equal to any other number being
presented. For the roll of two balanced true dice the combination of numbers
facing on the two dies are equally probable. That means for any one roll any
of the combinations which can occur is of equal probability (with the order
of the dies being taken into account). The probabilty of a 1-1 coming up is
the same as a 3-4 coming up.
However, there are six of the 36 combinations totaling 7 (1-6, 2-5, 3-4,
4-3, 5-2, 6-1) which means the probability of 7 is actually 6/36 or 1/6.

For a single die (easier to think about) each of the single values is
equally probably. The die doesn't remember what it faced last; each time you
roll the probability remains exactly the same. If 4 comes up six times in a
row that is to be expected once in a while (once every 1296 times any four
rolls are recorded).
If five rolls produced 1, 2, 3, 4, 5 (not necessarily in that order) the
next roll has exactly probability 1/6 of being a 6, or any other number for
that matter.

The issue of when a repeat of a number is guaranteed to occur is another
matter entirely, called the pidgeon-hole principle. With only six possible
outcomes a duplicate number is guaranteed only on the next roll ONCE EACH OF
THE NUMBERS HAS OCCURRED. Thus, the possibility that there could be a
sequence of 1, 2, 4, 2, 2, 4, 5, 3, 2, 1, 2, 2, 2, etc. with 6 not occurring
until the 19th or 1000th roll is just that -- a possibility. It has a very
small probability of happening, but it perfectly possible. (The real problem
is that if such a thing started to be noticed, the wise gambler begins to
suspect loaded, shaved, or otherwise controlled dice!)

If you find any of these comments useful, great. Otherwise -- next thread
back to C++.

OK, I'll try to make it less confusing. It has nothing to do with dice. The
assertion in question is:

"Repeat values are a consequence of finite numbers of bits
computed by the algorithm, not randomness itself."

Actually it comes in two parts:

"Repeat values are a consequence of finite numbers of bits
computed by the algorithm, ..."

All that means is that if an algorithm's output is limited to some finite
number of bits then if you keep sampling sooner or later you are going to
get a repeat. Not very profound, but it seems to be causing some people a
lot of concern! LOL

The second part"

....not randomness itself."

This means that there exists at least one algorithm which never repeats. I
proved this conclusively by citing a well known example: sampling from an
infinite population.

Now to your point: is this thread worth the effort? You be the judge.
Probably not...

Cy

 

[Peter van Merkerk]

"Repeat values are a consequence of finite numbers of bits computed by

No, I didn't mean that. I meant duplicate values.

In that case I'm afraid I have to agree with the other posters here; you are
wrong. Your statement is only correct if the generated number reflects the
full state of the random number generator. This is the case with some
popular Linear Congruential Generator implementations.

However the internal state of a random number generator may consist of many
more bits than the number of bits in the generated number (e.g. Mersenne
Twister generators). The period of the generator is limited by the number of
bits to describe its state. If the generator has more states than possible
output values, the logical conclusion is that many states produce the same
value, and consequently duplicate values will exist within a full period of
the generator.

 

[ghl]

OK, I'll try to make it less confusing. It has nothing to do with dice. The
assertion in question is:

"Repeat values are a consequence of finite numbers of bits
computed by the algorithm, not randomness itself."

Actually may have something to do with dice. With a single die there 6
states represented by a 4-bit value computed by the algorithm. With two die
there are 36 states, represented by two 4-bit values computed by the
algorithm.

Repeat values are a consequence of the randomness of the algorithm itself.
If the algorithm does not produce equally probable outcomes in its range, it
is a poor algorithm. (Actually, some algorithms are purposely written to
produce results in some skewed fashion where some numbers in the range occur
with greater frequency than others; Gaussian distribution, for instance.)
For example, a die loaded to never show the 6 face could be used to generate
an infinite number of outcomes and NONE of them would be a 6. If it were
loaded to always show a 1 face, then there would never be anything BUT
repeated 1's. It wouldn't matter if it were a 40-sided die in this case. The
"randomness" is based on the algorithm.

Is that what was being argued about?

 

[Cy Edmunds]

Actually may have something to do with dice. With a single die there 6
states represented by a 4-bit value computed by the algorithm. With two die
there are 36 states, represented by two 4-bit values computed by the
algorithm.

Repeat values are a consequence of the randomness of the algorithm itself.
If the algorithm does not produce equally probable outcomes in its range, it
is a poor algorithm. (Actually, some algorithms are purposely written to
produce results in some skewed fashion where some numbers in the range occur
with greater frequency than others; Gaussian distribution, for instance.)
For example, a die loaded to never show the 6 face could be used to generate
an infinite number of outcomes and NONE of them would be a 6. If it were
loaded to always show a 1 face, then there would never be anything BUT
repeated 1's. It wouldn't matter if it were a 40-sided die in this case. The
"randomness" is based on the algorithm.

Is that what was being argued about?

No.