I've just begun learning C++ and I'm trying to write a program to shuffle a
deck of cards. I've succeeded....for the most part....but every now and
then rand() produces duplicate random numbers causing me to "lose" a card.
How do I avoid this??? I've attached my code below for reference. Thanks
in advance.
------------------------
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
string cardDeck[] = {"As", "Ah", "Ad", "Ac",
"2s", "2h", "2d", "2c",
"3s", "3h", "3d", "3c",
"4s", "4h", "4d", "4c",
"5s", "5h", "5d", "5c",
"6s", "6h", "6d", "6c",
"7s", "7h", "7d", "7c",
"8s", "8h", "8d", "8c",
"9s", "9h", "9d", "9c",
"Ts", "Th", "Td", "Tc",
"Js", "Jh", "Jd", "Jc",
"Qs", "Qh", "Qd", "Qc",
"Ks", "Kh", "Kd", "Kc"};
map<int,string> shuffledDeck;
int randomNumber[52]; //used for debug purposes
int main()
{
srand( time(NULL) );
cout << "Current seed value: "
<< time(NULL)
<< "\n\n";
for (int i=0; i<52; ++i)
{
randomNumber[i] = rand();
shuffledDeck[ randomNumber[i] ] = cardDeck[i];
}
for (map<int,string>::iterator p = shuffledDeck.begin(); p !=
shuffledDeck.end(); ++p)
{
cout << p->first
<< "\t"
<< p->second
<< endl;
}
if (shuffledDeck.size () != 52) //indicates duplicate random numbers
{
sort(randomNumber, randomNumber+52); //easy viewing
cout << endl
<< "DUPLICATE RANDOM NUMBERS!\n\n";
for (int i=0; i<52; ++i)
cout << randomNumber [i]
<< "\t";
cout << "\n";
}
cout << endl;
system("PAUSE");
return 0;
} 23  5976 
hedylogus wrote:
every now and
then rand() produces duplicate random numbers
Of course it does. If it didn't, the numbers wouldn't be random.
How do I avoid this???
std::random_shuffle.
--
"To delight in war is a merit in the soldier,
a dangerous quality in the captain, and a
positive crime in the statesman."
George Santayana
"Bring them on."
George W. Bush
"Pete Becker" <pe********@acm.org> wrote in message
news:3F***************@acm.org... hedylogus wrote:
every now and
then rand() produces duplicate random numbers
Of course it does. If it didn't, the numbers wouldn't be random.
Repeat values are a consequence of finite numbers of bits computed by the
algorithm, not randomness itself. Of course with certain lousy
implementations of rand() only a miserly 15 bits (the absolute minimum
allowed by the standard) are provided, resulting in repetition in very short
run lengths.
How do I avoid this???
std::random_shuffle.
Or get a decent random number generator (31 bits or more). They are readily
available. You will still get repeats if you let your program run for the
rest of your life.
--
Cy http://home.rochester.rr.com/cyhome/
Cy Edmunds wrote: "Pete Becker" <pe********@acm.org> wrote in message
news:3F***************@acm.org...
hedylogus wrote:
every now and
then rand() produces duplicate random numbers
Of course it does. If it didn't, the numbers wouldn't be random.
Repeat values are a consequence of finite numbers of bits computed by the
algorithm, not randomness itself. Of course with certain lousy
implementations of rand() only a miserly 15 bits (the absolute minimum
allowed by the standard) are provided, resulting in repetition in very short
run lengths.
That's silly. If the numbers were truly random, the expected number of
draws before a duplicate would be much less than the number of possible
results. How do I avoid this???
std::random_shuffle.
Or get a decent random number generator (31 bits or more). They are readily
available. You will still get repeats if you let your program run for the
rest of your life.
If only 52 draws are made, what difference does drawing from 2^32 values
rather than 2&16 make? The chance of some number occurring twice in
those 52 draws would presumably still be significantly greater than
zero in the latter case.
(To the OP:)
Search for Fisher-Yates shuffle for the usual (optimal) implementation
of random_shuffle.
Regards,
Buster
Buster Copley wrote: If only 52 draws are made, what difference does drawing from 2^32 values
rather than 2&16 make? The chance of some number occurring twice in
those 52 draws would presumably still be significantly greater than
zero in the latter case.
That is, 2^16, and I hope you can guess which case I meant.
Regards,
Buster
Cy Edmunds wrote:
"Pete Becker" <pe********@acm.org> wrote in message
news:3F***************@acm.org... hedylogus wrote:
every now and
then rand() produces duplicate random numbers
Of course it does. If it didn't, the numbers wouldn't be random.
Repeat values are a consequence of finite numbers of bits computed by the
algorithm, not randomness itself.
No. Suppose you roll a six-sided die five times and you get 5, 2, 3, 6,
and 1. Do you expect 4 to come up next?
Of course with certain lousy implementations of rand() only a miserly 15 bits (the absolute minimum
allowed by the standard) are provided, resulting in repetition in very short
run lengths.
How do I avoid this???
std::random_shuffle.
Or get a decent random number generator (31 bits or more).
Won't help, if your technique is wrong. That's why random_shuffle isn't
called rand. They do different things.
--
"To delight in war is a merit in the soldier,
a dangerous quality in the captain, and a
positive crime in the statesman."
George Santayana
"Bring them on."
George W. Bush
"hedylogus" <xx**********@yahoo.xxx> wrote in message
news:<%JhUa.147299$H17.51207@sccrnsc02> ....but every now and
then rand() produces duplicate random numbers causing me to "lose" a card.
How do I avoid this??? I've attached my code below for reference. Thanks
in advance.
Despite quite a few answers already, I will take a stab at this in a
'newbie' context, since I am barely, if at all, past that stage myself.
rand() produces a stream of psuedo-random numbers based on a seed, the
computer clock in your case.
rand() cannot ensure that there are no duplicates in that stream. I can
think of three options for you in this case:
1) Find a more sophisticated random number generator. This is reasonable,
but IMHO, you would be better off with #2 or #3
2) Develop a test condition so you can "draw again" if the random number
tries to draw more than once from the same spot in CardDeck[]. This is a
reasonable solution, except for the fact that your code show s that you
have at least a passing familiarity with STL.
3) Go for the double bonus: go for random_shuffle like Rolf suggested. Not
only will you solve your duplication problem, your code will be much smaller
and cleaner. The bonus-bonus is that your code will be very readable, a
definite plus as far as grading goes.
Danny Anderson wrote:
1) Find a more sophisticated random number generator. This is reasonable,
but IMHO, you would be better off with #2 or #3
This is not the problem.
2) Develop a test condition so you can "draw again" if the random number
tries to draw more than once from the same spot in CardDeck[]. This is a
reasonable solution, except for the fact that your code show s that you
have at least a passing familiarity with STL.
This becomes slower as you use up numbers. Bad approach.
3) Go for the double bonus: go for random_shuffle like Rolf suggested. Not
only will you solve your duplication problem, your code will be much smaller
and cleaner. The bonus-bonus is that your code will be very readable, a
definite plus as far as grading goes.
Or learn how to do it yourself. It's not that hard, and provides some
useful insights.
--
"To delight in war is a merit in the soldier,
a dangerous quality in the captain, and a
positive crime in the statesman."
George Santayana
"Bring them on."
George W. Bush
> > 3) Go for the double bonus: go for random_shuffle like Rolf suggested.
Not only will you solve your duplication problem, your code will be much
smaller and cleaner. The bonus-bonus is that your code will be very readable, a
definite plus as far as grading goes.
Or learn how to do it yourself. It's not that hard, and provides some
useful insights.
Maybe so- my take was that the guy was using STL structures and some general
algorithms like sort(), but didn't seem to know about random_shuffle. In
that case, I think random_shuffle is a really good choice. I understand the
DIY rationalization, but it seems to me a lot of stuff works in the opposite
order: learn to use the tools available first, the improve and fabricate new
better tools when the need arises.
Just an opinion, don't flog me for it too much. :)
Danny
"Pete Becker" <pe********@acm.org> wrote in message
news:3F***************@acm.org... Cy Edmunds wrote:
"Pete Becker" <pe********@acm.org> wrote in message
news:3F***************@acm.org... hedylogus wrote:
>
> every now and
> then rand() produces duplicate random numbers
Of course it does. If it didn't, the numbers wouldn't be random.
Repeat values are a consequence of finite numbers of bits computed by
the algorithm, not randomness itself.
No. Suppose you roll a six-sided die five times and you get 5, 2, 3, 6,
and 1. Do you expect 4 to come up next?
No, I don't. But if I did get a 4, on the seventh roll I would certainly get
a duplicate. This has nothing to do with randomness. It only has to do with
the fact that a die only has six sides. Hence:
"Repeat values are a consequence of finite numbers of bits computed by the
algorithm, not randomness itself."
<snip>
--
Cy http://home.rochester.rr.com/cyhome/
On Sun, 27 Jul 2003 13:23:34 GMT,
Cy Edmunds <ce******@spamless.rochester.rr.com> wrote: "Pete Becker" <pe********@acm.org> wrote in message
news:3F***************@acm.org... Cy Edmunds wrote: >
> "Pete Becker" <pe********@acm.org> wrote in message
> news:3F***************@acm.org...
> > hedylogus wrote:
> > >
> > > every now and
> > > then rand() produces duplicate random numbers
> >
> > Of course it does. If it didn't, the numbers wouldn't be random.
>
> Repeat values are a consequence of finite numbers of bits computed by the > algorithm, not randomness itself.
No. Suppose you roll a six-sided die five times and you get 5, 2, 3, 6,
and 1. Do you expect 4 to come up next?
No, I don't. But if I did get a 4, on the seventh roll I would certainly get
a duplicate. This has nothing to do with randomness. It only has to do with
the fact that a die only has six sides. Hence:
"Repeat values are a consequence of finite numbers of bits computed by the
algorithm, not randomness itself."
Don't let hundreds of years of mathematics stand in the way of your unique
of the universe, will you?
Here's an algorithm for generating an unlimited number of "bits" and hence
there is no finite limit to the number of bits.
Roll a die, if the result is not a one or two record the result. If the result
is anthing else roll two dice (or one die twice) and concatanate the results
given by applying this mechanism recursively.
If on our first "roll" we end up rolling:
3
4
1
3
2
1
6
3
4
1
2
6
2
4
1
1
Giving:
12112211
As my randombly generated result.
To be random it must be possible that that exact result will be repeated the
next time I try. Even though, there are an infinite number of potential
outcomes.
--
Sam Holden
On Sun, 27 Jul 2003 17:43:19 GMT,
Cy Edmunds <ce******@spamless.rochester.rr.com> wrote: Sam-
I suggest you read my original post. The perhaps you can formulate a
relevant reply.
No thanks.
Any random process can generate repeats, else it isn't random.
Simple mathematics.
You can claim otherwise, for all I care. You can claim pi is rational too,
it really doesn't bother me.
--
Sam Holden
"Sam Holden" <sh*****@flexal.cs.usyd.edu.au> wrote in message
news:slrnbi8jll.ud4.sh*****@flexal.cs.usyd.edu.au. .. On Sun, 27 Jul 2003 17:43:19 GMT,
Cy Edmunds <ce******@spamless.rochester.rr.com> wrote: Sam-
I suggest you read my original post. The perhaps you can formulate a
relevant reply.
No thanks.
Any random process can generate repeats, else it isn't random.
Simple mathematics.
You can claim otherwise, for all I care. You can claim pi is rational too,
it really doesn't bother me.
--
Sam Holden
sigh. OK, let's go over it one point at a time. But this time we will deal
with actual quotes rather than inuendos. Here is what I actually said:
1. "Repeat values are a consequence of finite numbers of bits computed by
the algorithm, not randomness itself."
In case English isn't your first language, let me explain what this means.
If an algorithm generates a sequence of values, each of which is described
by a finite number of bits, the sequence must eventually generate repeat
values. This is true for random number generators but also for any other
algorithm. It is a direct consequence of the fact that n bits can only
express 2^n different values.
Does this somehow contract "hundreds of years of mathematics?" If so, how?
2. "Of course with certain lousy implementations of rand() only a miserly 15
bits (the absolute minimum allowed by the standard) are provided, resulting
in repetition in very short run lengths."
The maximum run length before repeats must occur is 2^n. Obviously higher
for higher values of n. If you sample with replacement the situation is more
complex although easily analyzable. But the trend is still, more bits ->
longer cycle time.
Does this somehow contract "hundreds of years of mathematics?" If so, how?
That's it. Only two points, both of which are obviously true. Now to Pete's
response:
"No. Suppose you roll a six-sided die five times and you get 5, 2, 3, 6, and
1. Do you expect 4 to come up next?"
Now which of my two points was Pete addressing? It certainly doesn't
contradict point 1. It also has nothing to do with point 2. In fact his
assertion is certainly true but has nothing to do with either of my points.
Now my response:
"No, I don't."
In other words, I agree with his assertion.
"But if I did get a 4, on the seventh roll I would certainly get a
duplicate. This has nothing to do with randomness. It only has to do with
the fact that a die only has six sides."
Here I am using his own example to restate my point #1.
Now, to you. You assert:
"Any random process can generate repeats, else it isn't random."
Technically, this is incorrect. For instance, the mathematics of sampling
from a Normal distribution, whose variables are truly continuous, allows for
no repeats. But given the context of computer algorithms, which after all is
what we were talking about, the number of bits must be finite and your
assertion is certainly correct.
Now for the punch line: having reviewed the dialog so far I ask you, where
do you see me saying otherwise? I want a direct quote or an apology.
If you want to make snotty responses I suggest you actually read the posts.
Cy
On Sun, 27 Jul 2003 22:48:40 GMT,
Cy Edmunds <ce******@spamless.rochester.rr.com> wrote:
[snip]
sigh. OK, let's go over it one point at a time. But this time we will deal
with actual quotes rather than inuendos. Here is what I actually said:
1. "Repeat values are a consequence of finite numbers of bits computed by
the algorithm, not randomness itself."
In case English isn't your first language, let me explain what this means.
If an algorithm generates a sequence of values, each of which is described
by a finite number of bits, the sequence must eventually generate repeat
values. This is true for random number generators but also for any other
algorithm. It is a direct consequence of the fact that n bits can only
express 2^n different values.
I disagree on this point.
Yes, with a finite number of outcomes, repeats are required for infinite
(or a finite number greater than the number of outcomes) applications.
That's a given.
However, a random number generator which has the domain of the nonnegative
integers, for example, to be truly random must be capable of generating
repeats. Of course
the probability of a repeat is infinitesimal.
If repeats aren't possible then the process isn't random.
The disagreement is probably about the definition of "random" which, as
with most terms, means many quiet different things. In comp.lang.c++ the
two normal definitions are "wierd or uncertain" as in "my program is
randomly crashing", or "to select from a set with equal probability of
all elements being selected", as in "how do I generate a random number?".
Does this somehow contract "hundreds of years of mathematics?" If so, how?
2. "Of course with certain lousy implementations of rand() only a miserly 15
bits (the absolute minimum allowed by the standard) are provided, resulting
in repetition in very short run lengths."
The maximum run length before repeats must occur is 2^n. Obviously higher
for higher values of n. If you sample with replacement the situation is more
complex although easily analyzable. But the trend is still, more bits ->
longer cycle time.
Does this somehow contract "hundreds of years of mathematics?" If so, how?
That's it. Only two points, both of which are obviously true. Now to Pete's
response:
"No. Suppose you roll a six-sided die five times and you get 5, 2, 3, 6, and
1. Do you expect 4 to come up next?"
Now which of my two points was Pete addressing? It certainly doesn't
contradict point 1. It also has nothing to do with point 2. In fact his
assertion is certainly true but has nothing to do with either of my points.
Does everything have to be in response to your specific points?
Are people not allowed to go off on tangents, discuss misinterpretations,
ignore the actual point, discuss things from the perspective of C++, etc?
Now my response:
"No, I don't."
In other words, I agree with his assertion.
"But if I did get a 4, on the seventh roll I would certainly get a
duplicate. This has nothing to do with randomness. It only has to do with
the fact that a die only has six sides."
Here I am using his own example to restate my point #1.
Now, to you. You assert:
"Any random process can generate repeats, else it isn't random."
Technically, this is incorrect. For instance, the mathematics of sampling
from a Normal distribution, whose variables are truly continuous, allows for
no repeats. But given the context of computer algorithms, which after all is
what we were talking about, the number of bits must be finite and your
assertion is certainly correct.
Now for the punch line: having reviewed the dialog so far I ask you, where
do you see me saying otherwise? I want a direct quote or an apology.
If you want to make snotty responses I suggest you actually read the posts.
This is usenet, I'm free to jump in and reply to a post I read. Honestly
the back story doesn't worry me. If it isn't quoted in the message I'm
replying to. I'm replying to a particular point in a particular post, if
you don't like that then there is no obligation to read my posts.
--
Sam Holden
"Cy Edmunds" <ce******@spamless.rochester.rr.com> wrote in message
news:qn*******************@twister.nyroc.rr.com... "Pete Becker" <pe********@acm.org> wrote in message
news:3F***************@acm.org... Cy Edmunds wrote:
"Pete Becker" <pe********@acm.org> wrote in message
news:3F***************@acm.org...
> hedylogus wrote:
> >
> > every now and
> > then rand() produces duplicate random numbers
>
> Of course it does. If it didn't, the numbers wouldn't be random.
Repeat values are a consequence of finite numbers of bits computed
by the algorithm, not randomness itself.
No. Suppose you roll a six-sided die five times and you get 5, 2, 3,
6, and 1. Do you expect 4 to come up next?
No, I don't. But if I did get a 4, on the seventh roll I would
certainly get a duplicate. This has nothing to do with randomness. It only has to do
with the fact that a die only has six sides. Hence:
"Repeat values are a consequence of finite numbers of bits computed by
the algorithm, not randomness itself."
You probably mean "Repeating *sequences* of values are a consequence of
finite numbers of bits computed by the *pseudo random* algorithm.".
Within a pseudo random sequence the same value may occure multiple
times. Even if a algorithm would use an infinite number of bits to
compute a value, it could still produce many times the same value.
--
Peter van Merkerk
peter.van.merkerk(at)dse.nl
In article <bg************@ID-133164.news.uni-berlin.de>, Peter van Merkerk wrote: Within a pseudo random sequence the same value may occure multiple
times. Even if a algorithm would use an infinite number of bits to
compute a value, it could still produce many times the same value.
Note that even real random number generator might produce
sequence of million same numbers.
--
Wellu Mäkinen <we***@NOSPAMwellu.org>
gpg_key http://www.wellu.org/key.pgp
No tears please, it's a waste of good suffering.
>>> sigh. OK, let's go over it one point at a time. But this time we will deal with actual quotes rather than inuendos. Here is what I
actually said:
1. "Repeat values are a consequence of finite numbers of bits
computed by the algorithm, not randomness itself."
In case English isn't your first language, let me explain what
this means.
If an algorithm generates a sequence of values, each of which is
described by a finite number of bits, the sequence must eventually
generate repeat values. This is true for random number generators
but also for any other algorithm. It is a direct consequence of the
fact that n bits can only express 2^n different values.
Your quote above has TWO parts:
1 (a) "Repeat values are a consequence of finite numbers of bits computed
by the algorithm."
1 (b) "Repeat values are not a consequence of randomness itself."
The first part is true, and utterly vacuous. The second part, which is
false, has been the target of the arguments presented so far. If you
didn't notice this, you cannot have understood those arguments. If you
noticed it but decided to ignore it, then I can think of several apt
Latin words, along with any number in demotic anglo-saxon.
Does this somehow contract "hundreds of years of mathematics?" If so,
how?
No, but no one said it does. You're defending one half of your
statement while Pete and Simon question the other half.
Here's a demonstration that (b) is false.
Let X[0], X[1], ..., X[k-1] be discrete random variables uniformly
distributed on the set { 0, 1, 2, ..., n-1 }. Let A be the event
that there is at least one repetition in this collection, that is,
A = (X[i]==X[j]) for some i and j with 0 <= i < j < k. The complementary
event B is that all the X[i]'s are distinct:
B = (X[1]!=X[0]) && (X[2] is not in { X[0], X[1] })
&& (X[3] is not in { X[0], X[1], X[2] })
&& ...
&& (X[k-1] is not in { X[0], X[1], ..., X[k-2] })
We can see that B has probability
P (B) = ((n-1)/n) * ((n-2)/n) * ... * ((n-k+1)/n)
= n!/((n-k)! * pow (N, k-1)).
And of course P (A) = P (B) - 1.
We'll suppose k = 52 as in the original post. With n = 1 << 15,
P (A) comes to 0.03968, and with n = 1 << 31 it's 0.0000006175.
This is an approximation to the probability of the OP's algorithm failing
to do its job on any given run. If I were him I'd use the Fisher-Yates
shuffle instead. Then I'm absolutely certain to get what I want.
Caveat: for all I know, you can choose your pseudo-random number
generator in such a way that you are guaranteed not to get any
repetition during any run of k draws, whether k be 52 or 5002.
However, the OP had settled on using std::rand (), so he could rely
on no such guarantee.
Regards,
Buster Copley
> > Within a pseudo random sequence the same value may occure multiple times. Even if a algorithm would use an infinite number of bits to
compute a value, it could still produce many times the same value.
Note that even real random number generator might produce
sequence of million same numbers.
Though the probability of that happing is very small (but not
impossible).
--
Peter van Merkerk
peter.van.merkerk(at)dse.nl
"Buster" <rc*****@ukonline.co.uk> wrote in message
news:f5**************************@posting.google.c om... sigh. OK, let's go over it one point at a time. But this time we
will deal with actual quotes rather than inuendos. Here is what I
actually said:
1. "Repeat values are a consequence of finite numbers of bits
computed by the algorithm, not randomness itself."
In case English isn't your first language, let me explain what
this means.
If an algorithm generates a sequence of values, each of which is
described by a finite number of bits, the sequence must eventually
generate repeat values. This is true for random number generators
but also for any other algorithm. It is a direct consequence of the
fact that n bits can only express 2^n different values.
Your quote above has TWO parts:
1 (a) "Repeat values are a consequence of finite numbers of bits computed
by the algorithm."
1 (b) "Repeat values are not a consequence of randomness itself."
The first part is true, and utterly vacuous. The second part, which is
false, has been the target of the arguments presented so far. If you
didn't notice this, you cannot have understood those arguments. If you
noticed it but decided to ignore it, then I can think of several apt
Latin words, along with any number in demotic anglo-saxon.
Does this somehow contract "hundreds of years of mathematics?" If so, how?
No, but no one said it does. You're defending one half of your
statement while Pete and Simon question the other half.
Here's a demonstration that (b) is false.
Let X[0], X[1], ..., X[k-1] be discrete random variables uniformly
distributed on the set { 0, 1, 2, ..., n-1 }.
Note that this algorithm computes a finite number of bits. Thus the
remainder of your proof which quite correctly shows that duplicate values
are inevitable does not contradict 1b.
Let A be the event
that there is at least one repetition in this collection, that is,
A = (X[i]==X[j]) for some i and j with 0 <= i < j < k. The complementary
event B is that all the X[i]'s are distinct:
B = (X[1]!=X[0]) && (X[2] is not in { X[0], X[1] })
&& (X[3] is not in { X[0], X[1], X[2] })
&& ...
&& (X[k-1] is not in { X[0], X[1], ..., X[k-2] })
We can see that B has probability
P (B) = ((n-1)/n) * ((n-2)/n) * ... * ((n-k+1)/n)
= n!/((n-k)! * pow (N, k-1)).
And of course P (A) = P (B) - 1.
We'll suppose k = 52 as in the original post. With n = 1 << 15,
P (A) comes to 0.03968, and with n = 1 << 31 it's 0.0000006175.
This is an approximation to the probability of the OP's algorithm failing
to do its job on any given run. If I were him I'd use the Fisher-Yates
shuffle instead. Then I'm absolutely certain to get what I want.
Caveat: for all I know, you can choose your pseudo-random number
generator in such a way that you are guaranteed not to get any
repetition during any run of k draws, whether k be 52 or 5002.
However, the OP had settled on using std::rand (), so he could rely
on no such guarantee.
Regards,
Buster Copley
1b is just as "vacuous" as 1a.You get repeat values from algorithms which
have nothing to do with randomness. For instance, consider a generator which
produces j % 4 where j = 0, 1, 2, ... infinity. You get your first duplicate
at j = 4. Since an algorithm with absolutely no element of randomness can
generate duplicate values, we are safe in saying:
"Repeat values are not a consequence of randomness itself."
Go over your own proof in the case of an infinite population size. The
probability of a repeat value is 1/infinity which is zero (not
"infinitesimal" as someone else asserted). Thus duplicate values can never
happen unless the population from which you are sampling is finite. Or,
"Repeat values are a consequence of finite numbers of bits
computed by the algorithm, not randomness itself."
Cy
--
Cycho{HHR} http://home.rochester.rr.com/cyhome/
"ghl" <gl*******@comcast.net> wrote in message
news:DD********************@comcast.com... 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++.
--
Gary
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
> > > "Repeat values are a consequence of finite numbers of bits computed by the algorithm, not randomness itself."
You probably mean "Repeating *sequences* of values are a consequence of
finite numbers of bits computed by the *pseudo random* algorithm.".
Within a pseudo random sequence the same value may occure multiple
times. Even if a algorithm would use an infinite number of bits to
compute a value, it could still produce many times the same value.
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.
--
Peter van Merkerk
peter.van.merkerk(at)dse.nl
"Cy Edmunds" <ce******@spamless.rochester.rr.com> wrote in message
news:0b*******************@twister.nyroc.rr.com... 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?
--
Gary
"ghl" <gl*******@comcast.net> wrote in message
news:Dt********************@comcast.com... "Cy Edmunds" <ce******@spamless.rochester.rr.com> wrote in message
news:0b*******************@twister.nyroc.rr.com... 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?
--
Gary
No. :)
--
Cy http://home.rochester.rr.com/cyhome/ This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Richard B. Kreckel |
last post by:
Hi!
I was recently asked what book to recommend for a beginner in C++. I
am convinced that you needn't study C in depth before learning C++
(though it helps), but cannot find any beginner's...
|
by: Grrrbau |
last post by:
I'm a beginner.
I'm looking for a good C++ book.
Someone told me about Lafore's "Object-Oriented Programming in C++".
What do you think?
Grrrbau
|
by: Rensjuh |
last post by:
Hello, does someone have / know a good C++ tutorial for beginnners? I would prefer Dutch, but English is also fine.
Hoi, heeft / kent iemand nog een goede C++ tutorial voor beginners? Het liefste...
|
by: MHoffman |
last post by:
I am just learning to program, and hoping someone can help
me with the following:
for a simple calculator, a string is entered into a text
box ... how do I prevent the user from entering a text...
|
by: mitchellpal |
last post by:
Hi guys, am learning c as a beginner language and am finding it rough
especially with pointers and data files. What do you think, am i being
too pessimistic or thats how it happens for a beginner?...
|
by: weight gain 2000 |
last post by:
Hello all!
I'm looking for a very good book for an absolute beginner on
VB.net or VB 2005 with emphasis on databases. What would you
reccommend?
Thanks!
|
by: macca |
last post by:
Hi, I'm looking for a good book on PHP design patterns for a OOP
beginner - Reccommendations please?
Thanks
Paul
|
by: Roman Zeilinger |
last post by:
Hi
I have a beginner question concerning fscanf.
First I had a text file which just contained some
hex numbers:
0C100012
0C100012
....
|
by: hamza612 |
last post by:
I want to start learning how to program. But I dont know where to
start. From what I've heard so far c++ is not a good lang. to learn
as a beginner because its very complicated compared to others...
|
by: ddg_linux |
last post by:
I have been reading about and doing a lot of php code examples from
books but now I find myself wanting to do something practical with
some of the skills that I have learned.
I am a beginner php...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
| |
