Is the sequence of non repeating random numbers still random?

Question

The original question was from a programming interview, they asked for a random player not playing same song until all other remaining songs have played in "Random" order.

This question is asking for non repeating random numbers, from what little i remember from doing probability almost 30 years ago, in a sequence of random numbers every sequence should happen infinitely many times, therefore any length of repetition of all numbers should be present.

My question is, are such sequences that are void of repetition, any less random ? should they not be called random as there is a rule that has changed the probability of next number not to be equally likely for all numbers, or some other reasoning applies?

for example a coin toss is no longer random if no repetition is allowed, after the first flip all other flips are known, so one would agree that makes the randomness of coin flipping to disappear.

Answer 1

Short answer:

There is no such thing as a random sequence.

Longer answer:

A sequence, in itself, cannot be random. What is random is the process that produces the sequence. Take, for example, the sequence

$2,5,1,6$.

Is it random? Well, if it is the product of a die roll, then people would call it "random". But what if I tell you that in fact, this sequence is part of my bread making recipe? (2 cups flour, 5 ounces salt, one cup water and 6 teaspoons yeast). Is the sequence still "random"? No, right? So if the same sequence can be both random and not at the same time, it's only reasonable that randomness cannot be the property of the sequence itself, but rather the process that produces it.

Answer 2

First, summarizing a few comments and fixing some ideas:

1. You need to know what you mean by "random." The typical way that this idea is introduced is via a sample space. If you conduct an experiment, the sample space is the set of all possible outcomes. For example, if you flip a coin, the sample space is $\{H,T\}$. If you flip a coin twice and keep track of the sequence of heads and tails, the sample space is $\{HH, HT, TH, TT\}$. If you flip a coin eight times and count the number of heads, the sample space is $\{0,1,2,\dotsc, 8\}$.

2. Once a sample space has been fixed, a random process is a process which selects an element from the sample space. Each subset of the sample space has some probability of being selected—in the case of tossing a coin, both $H$ and $T$ are equally likely. On the other hand, if we flip a coin eight times and count the heads, not all of the possible outcomes are equally likely—we are far more likely to get 4 heads than none. However, the process of flipping the coin (which is the process by which we select a result from our sample space) is still a random process.

3. Note that I have been very careful to refer to the process as being random, and not the outcome. If I toss a coin and get heads, then I got heads. This result is not a "random" result. It is the result of a random process, but once I have the result, it is entirely determined. Again, it is the process of selecting an outcome from the sample space of possible outcomes which is random, not the outcome itself.

   

---

Now, to attempt to answer your question: suppose that you have a program which creates playlists, where by a playlist, I mean an ordered list of all of the songs available on a device. If there are $n$ songs on the device, then there are a total of $n!$ possible playlists—there are $n$ choices for the first song, $n-1$ choices for the second song, and so on. Indeed, this outlines a random process for creating the playlist:

1. Select a song "at random" (say, uniformly) from among the $n$ possible songs as the first song.
2. Select a song "at random" from among the $n-1$ possible songs remaining as the second song.
3. Select a song "at random" from among the $n-2$ possible songs remaining as the third song.
4. And so on until a playlist of $n$ songs is created.

Another possible process is:

1. Select a song at random from among the $n$ possible songs as the first song.
2. Select a song at random from among the $n$ possible songs as the second song.
3. Select a song at random from among the $n$ possible songs as the third song.
4. And so on until a playlist of $n$ songs is created.

Both of these processes are random, and I would not say that either is any "more" or "less" random than the other. The first process selects an element from the sample of playlists of length $n$ without repetition, while the second process selects an element from the sample space of playlists of length $n$ with repetition. In either case, the process is uniform in that any outcome (from among the possible outcomes) is equally likely (assuming that each song is equally likely to be selected at each step).

Note that if the first process is used, then we can predict the next song more accurately than if the second process is used. As an edge case, after $n-1$ songs have been played, the first process can only make one choice (the sample space of possible "next songs" has been reduced to a single element), so the next song can be predicted with probability $1$—note that the process of selecting that last song is still random, even though the outcome is entirely determined. This may "feel" less random, but from a mathematical point of view, it still fits the definition of a random process.

It is also worth observing that the second process is, I think, what you have in mind when you suggest a "random" sequence. That is, we can build a sequence by observing a series of coin tosses. After each toss, record either $H$ or $T$. Repeat this forever. Now pick your favorite finite sequence of $H$s and $T$s (say, $TTTTT$). Probability theory predicts that, with probability $1$, this finite sequence (or any other finite sequence) will appear infinitely often in your infinite sequence. That being said, this does not mean that it will appear infinitely often—only that it will appear infinitely often with probability $1$. It is always possible (however unlikely) that you flip nothing but heads forever.