Is a subset of a random sequence also random?

Question

Given:

• 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: 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).

Answer 1

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).

Answer 2

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.