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

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

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.

Answer 3

If

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

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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