Take the 2-minute tour ×


  • a sequence of random numbers
  • X clients select Y numbers from the sequence, forming their own sub-sequences
  • the rules governing the selection process is not known

Is there a mathematical property that guarantees that each client will end up with a random sequence of numbers? That is, is a subset of a random sequence also guaranteed to be random regardless of the selection process?

UPDATE: I was trying to establish if I could use a single random-number generator to dish out values to multiple clients: http://stackoverflow.com/questions/203382/do-stateless-random-number-generators-exist -- That is, clients choose elements from the sequence without replacement. That being said, I was wondering about the general case as well (when the selection rules are not known).

share|improve this question
Are you saying that the selection process is random or that the selection process just isn't known, so it could be anything? –  Evan Shaw Jan 22 '09 at 22:48
I think you'll have enough difficulty establishing that the original sequence is random let alone the subsequences. –  cletus Jan 22 '09 at 23:12
Definitely need a bit more details like can two clients choose the same item twice, do they choose from the indice (not knowing the actual number) and is the sequence regenerated for each client? –  Loki Jan 23 '09 at 0:17
I think the point is that given that a sequence is random, shouldn't any arbitrary subset be random? As such, it shouldn't matter who selects what when. Or at least thats what the poster is asking whether that can be proven. –  cletus Jan 23 '09 at 5:03

7 Answers 7

up vote 2 down vote accepted

The word "random" in "a sequence of random numbers" is generally construed to mean that there is no additional information about any element of the sequence from looking at any other elements of the sequence. (i.e. the a priori and a posteriori probability distributions of element Xi are the same before and after studying any of the other elements.)

As long as none of the numbers are used by more than one client, you should be fine. (edit: and as others have mentioned, you can't decide to accept one of the elements after you look at its value.)

share|improve this answer
In practise many random number generators will not display such ideal behaviour. You may wish to write your own mersenne twister; they're simple to implement. –  user82238 Mar 29 '09 at 8:16

The subset will not be random if the rules governing the selection process include awareness of the actual values (which might be the case since these rules are not known).

share|improve this answer
For example, if the "selection process" is "pick one, look at it, and if it isn't 42 then discard it and pick another until it is 42". –  ChrisW Jan 22 '09 at 22:51
@ChrisW: well spoke. :) –  MusiGenesis Jan 22 '09 at 22:54
Right on MusiGenesis. I always chuckle when someone tells me to "just pick one at random" –  EvilTeach Jan 23 '09 at 15:40

Yes, your sub-sequence will be random (joint entropy), assuming the one restriction on your selection criteria is that you "do not put anything back". In other words, you cannot preferentially filter the sub-sequence as you pick it. The type of selection is then irrelevant... you can always pick the odd bits or the even bits or the first 10 bits or however you want to pick, and your sub-sequence will have exactly that many bits of entropy.

Of course, picking the same bit over does not add to your total entropy, in that there is no entropy left in that bit to add to your system. But the way in which the bit was picked a second time (i.e. if it was a random pick) may itself add some entropy.

That said, there's likely to be a high degree of correlation between each of the sub-sequences that each client gets, for the obvious reason that they may be using identical or overlapping selection criteria.

share|improve this answer

Is there a mathematical property that guarantees that ...

Excepting the counter-examples like the ones which 'MusiGenesis' and 'gs' gave, I think that there is a mathematical property (axiom or theorum, I don't know which) in statistics: which says something to the effect that the statistical properties of a parent population are more-or-less-well reflected in the properties of a randomly selected sample.

share|improve this answer

No, because if both clients select the same or an near position to start the sequence both have the same data. Individually they have random data, but not if you respect more than 1 user.

Random data could only be generated if you make sure that every number can only be accessed by one user and then maybe be removed from the list. Of course in this case you could also just use a normal random-number generator.

share|improve this answer
Good point. I'm glad I read your answer twice, because the first time it didn't make sense to me. –  MusiGenesis Jan 22 '09 at 23:57
I'm doing my best, but sometimes the English language prevents me from writing clearly. :) –  Georg Schölly Jan 23 '09 at 0:01
You're doing fine - the lack of understanding was totally in my head. :) –  MusiGenesis Jan 23 '09 at 2:12


  • the number of clients was random
  • the number of picks was random
  • the size of the first random sequence was random

Then... no it still doesn't seem like it would be because the client's number of picks might be larger than the first sequence, in which case the randomness would disappear because the client would have to decide what to do when it made a pick and got nothing.

Maybe it would work if the first sequence was of infinite size.

Edit: sorry, you're probably looking for something mathematical here, in the form of a proof. I have no such proof :)

share|improve this answer

I think part of what makes a sequence random is the ability to run the same algorithm and get different, unpredictable results.

In your description, if you repeated the process and the same X clients selected Y numbers from the original sequence, would they select the the same subsequences, and therefore get repeatable, predictable results?

If so, I would say it does NOT seem to be a random process. If however, your subsequence selection contains an element of randomness to it, then the subsequences would vary on sequential, otherwise identical runs, and the subsequences could be considered random.

share|improve this answer

Your Answer


