1
$\begingroup$

I was having a chat with my friend. We were discussing the problem of producing an array of size $N$ filled with random numbers from $0$ to $N - 1$.

Here by filled with random numbers from $0$ to $N - 1$ , I mean,

  • Every number in the array should have been randomly selected with an equal probability of $1/N$

I suggested this,

  • Assuming I have a way to uniformly generate random number between $[0, 1)$, say $Rnd()$
  • Fill each element in the array as, $floor(Rnd() * N)$

My friend said this,

  • Assuming I have a way to shuffle the array.
  • Fill the array with numbers $0 .. N - 1$ at the indices $0 .. N-1$
  • Do a shuffle on the array.

My friend claims that his method is better because it ensures that every number between $0 .. N - 1$ will occur once and only once. Hence stratifying, the equal probability requirement.

Another difference that I see here is that in the way I suggested, it is possible for a number to be chosen 2 times whereas this is not possible in my friend's way. So the results each of our methods produce are different.

Given that we just have to produce an array of size $N$ which can only contain numbers between $0 .. N-1$ and the probability of occurrence of any number is equal, $1/N$. I couldn't find anything wrong with either of these methods though they are different and produce different results.

Who here, if any, is wrong and why ? Or are we both wrong ?

$\endgroup$
  • 3
    $\begingroup$ Your friends method does not produce the results youre looking for. Lets say you read his array from left to right. The first number does indeed fulfill the conditions you have listed. How about the second number? Do you still have $1/N$ chance of getting a number between $0$ and $N-1$? $\endgroup$ – Lundborg Mar 14 '16 at 8:26
  • $\begingroup$ I'm not sure what 'the probability of occurrence or any number is equal, 1/N' means. Is it about a probability of ocurrence of any number at arbitrarily chosen position (that is, at each item of an array it's the same probability of having any value $0\ldots(N-1)$) or is it a probability that any given number occurs anywhere in the array? $\endgroup$ – CiaPan Mar 14 '16 at 8:39
  • $\begingroup$ Both methods give the same probability of having any chosen value at any chosen position in the resulting array. However your method allows e.g. an array filled with zeros (with a probability of $1/n^n$) while your friend's method does not. His method produces only one of $n!$ permutations of $(0, 1, \ldots(N-1))$ sequence while yours produces any of $n^n$ possible $n$-term sequences of values from the $\{0, 1, \ldots N-1\}$ set. $\endgroup$ – CiaPan Mar 14 '16 at 8:44
  • $\begingroup$ @CiaPan I am sorry. That was a mistake, it was supposed to be occurrence of any number $\endgroup$ – Mohammad Ghazanfar Mar 14 '16 at 10:51
  • $\begingroup$ Easier: Choose a number $n$ at random between $0$ and $N-1$, and fill the array with consecutive numbers modulo $N$. The probability that a number $i$ appears in any position is then $\frac{1}{N}$. $\endgroup$ – Steve Kass Mar 14 '16 at 16:44
1
$\begingroup$

Your definition of "filled with random numbers from $0$ to $N-1$" specifies the marginal probability distribution of each entry (that is to say, if you look at any entry individually while ignoring the others, what is the probability of each outcome for that entry), but it says nothing about the dependence of different entries on each other.

The procedure you chose generates a set of $N$ iid (independent, identically distributed) uniform random variables on the set $[0..(N-1)]$. But if you leave out the word "independent" (which your definition did not mention or even indirectly imply), there are many other sets of identically distributed uniform random variables on $[0..(N-1)]$. Your friend's distribution is one such distribution.

Here's another such distribution: choose a number $X$ with uniform probability from $[0..(N-1)]$. Fill each entry in the array with $X$ (all entries the same value).

And another: choose a number $X$ with uniform probability from $[0..(N-1)]$. Fill entry $k$ in the array, $0 \leq k < N$, with $X + k \bmod N$. (That is, if $X+k<N$, let entry $k$ be $X+k$; otherwise let entry $k$ be $X+k-N$.)

Your distribution is more "interesting" than either of those. So is your friend's distribution. In fact, I would say that the two of you have picked the two most obviously desirable distributions fitting your description; each of these distributions is useful for different things, so I would not say one is better than the other.

$\endgroup$
0
$\begingroup$

You friend is correct in arguing that every number between $0$ and $N−1$ will occur once and only once, but he/she is wrong in arguing that this fact will ensure the equal-probability requirement.

For this, you both need to understand that the equal-probability requirement means that each one of the $n!$ different arrangements of the array must be generated with an equal probability (of $1/n!$).

So your friend's shuffling method should be designed carefully in order to ensure equal probability.

One way to do this (as very often appears in software-engineering job interviews by the way):

  • Repeat for $m=0$ to $n-1$:

    • Choose a random index $k$ from the range $[m+1,n-1]$
    • Swap between element at entry $m$ and element at entry $k$
$\endgroup$
  • $\begingroup$ More readable version of the routine (with 1-based indices): for $m = N$ downto $1$; choose a random number $k$ from $[1 .. m]$ and swap entry $m$ with $k$. With zero-based indices: for $m = N-1$ downto $0$; choose a random number $k$ from $[0 .. m]$ and swap entry $m$ with $k$. $\endgroup$ – CiaPan Mar 14 '16 at 8:51
  • $\begingroup$ @CiaPan: I agree about the $1$-based indices being more readable than $0$-based indices, but since OP has used the latter in his/her post, I had to stick to it. But in any case, I don't understand why you think that your "downto" method is more readable than my "upto" method. $\endgroup$ – barak manos Mar 14 '16 at 9:15
  • $\begingroup$ It reads simpler because choosing a random number from the range $0\dots(N-1)$ requires just one call to the number generator, without adding offset afterwards, and usually such call is done with one parameter $m$, which is already there as the current loop control variable (you do not need to calculate the range length, even if the whole calculation would be just one subtraction). $\endgroup$ – CiaPan Mar 14 '16 at 9:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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