0
$\begingroup$

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.

$\endgroup$

closed as unclear what you're asking by Did, Peter, NCh, hunter, mrtaurho Jan 27 at 19:58

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ I think it's just a question of what you mean by random. One can speak of, say, a randomly chosen two digit number, or one can speak of a randomly chosen two digit number with no double digits. In each case, the uniform distribution makes complete sense. $\endgroup$ – lulu Jan 15 at 12:06
  • $\begingroup$ If, say, you mean that you want each digit to be equally probable in each slot then both cases satisfy that (well, you have to resolve how you handle $0$ in the first slot). $\endgroup$ – lulu Jan 15 at 12:09
  • $\begingroup$ @lulu : consider the case of 1,0 or heads and tails. I am guaranteed to win every bet except the first one with certainty, where is the randomness in that? $\endgroup$ – Arjang Jan 15 at 12:12
  • 2
    $\begingroup$ Once again: "random" depends on a specified probability distribution on a specified set. That distribution, and that set, will have specified properties. But so what? You'd agree, I expect, that we can speak of a random ordering of distinct objects. But in that case, knowing the placement of the first $n-1$ out of $n$ objects tells you where the $n^{th}$ is. But again...so what? $\endgroup$ – lulu Jan 15 at 12:29
  • 2
    $\begingroup$ What are you talking about? They are two different sets! You can speak of the uniform distribution on the set $00,01,10,11$ and you can speak of the uniform distribution on $01,10$. But as the sets are different, what sense does it make to ask if the distributions are the same? $\endgroup$ – lulu Jan 15 at 12:42
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ no finite sequence can be considered random or not. $\endgroup$ – Arjang Jan 15 at 12:28
  • $\begingroup$ @Arjang So a sequence of $6$ flips of a fair coin is not random? $\endgroup$ – 5xum Jan 15 at 12:29
  • $\begingroup$ would the result of those 6 flips have repetition or not? if no repetition is allowed then the result of last 5 filps have nothing random about them. $\endgroup$ – Arjang Jan 15 at 12:40
  • 2
    $\begingroup$ @Arjang And my point is that the flips themselves, not the individual result that they produce, are the thing that is random. $\endgroup$ – 5xum Jan 15 at 12:45
  • 2
    $\begingroup$ @Arjang Are you even listening to me? I will say this for the last time. The results are neither random nor non-random. The property "is random" cannot be assigned to them. The property can only be assigned to the process that creates the results. $\endgroup$ – 5xum Jan 15 at 12:51
3
$\begingroup$

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.

    https://xkcd.com/221/


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.

$\endgroup$
  • $\begingroup$ You could say a random process with a larger sample space is "more random" than a random process with a constrained sample space. This is just a corollary of what you are already saying, I guess. $\endgroup$ – tripleee Jan 24 at 9:58
  • $\begingroup$ @tripleee I'm not sure that I entirely agree about that. Consider two random processes: one is a single toss of a fair coin. The sample space consists of exactly two outcomes, each equally likely. Then consider a probability distribution defined the numbers $\{1,2,\dotsc,10^10\}$, where $P(1) = 0.99$ and the rest of the numbers are equally likely to be selected. The sample space in the second example is much larger, but the process "feels" much less random to me. Even more pathologically, consider a distribution defined on the interval $[0,1]$ with $P(0) = 1$. $\endgroup$ – Xander Henderson Jan 24 at 14:11
  • $\begingroup$ Isn't that apples and oranges, though? Let me rephrase: all other things being equal, a process with a smaller or otherwise more constrained sample space will be more predictable. $\endgroup$ – tripleee Jan 24 at 14:38
  • $\begingroup$ @tripleee I'm still not sure that I agree. A uniform process on a small sample space is exactly as "random" (whatever that even means) as a uniform process on a large sample space. Both processes are "uniformly" random. $\endgroup$ – Xander Henderson Jan 24 at 16:37

Not the answer you're looking for? Browse other questions tagged or ask your own question.