# Is my algorithm probabilistically fair?

Let $S(n)$ be a sequence of length $n$. I want to give a label in $\{0,1,2,3\}$ to each term of $S(n)$ so that each term is given its label randomly. From some reasons, I want to use the following algorithm:

1. Let $n_2$ be any integer such that $n < n_2 < 2n$ and $n_2$ is divisible by $4$.

2. Let $S(n_2)$ be the sequence of integers in the range $[1\,..\,n_2]$.

3. Let $S(n_2)[i] = S(n_2)[i \bmod 4 ]$ where $\bmod$ denotes the division remainder operator.

4. Shuffle $S(n_2)$ randomly using a known good algorithm.

5. Let $S(n)[i] = S(n_2)[i]$.

Is the algorithm random enough?

-
What does "enough" mean in "random enough"? The division of our sequence into slots $0$, $1$, $2$, $3$ is too uniform. In $10000$ tosses of a fair coin, there is probability $>60$% of having more than $5025$ or fewer than $4975$ heads. With small numbers, like a short multiple choice test with $4$ choices on each, one could do well by knowing just a few correct answers. –  André Nicolas Mar 6 '12 at 12:18
I made some copyedits to your question; could you please check that I didn't change the meaning of anything you wrote? –  Ilmari Karonen Mar 6 '12 at 12:50

If the algorithm in step 4 is good enough, then it's a qualified yes. Given nothing, the probability for each assignment is uniform, but if you know the index of some elements, then that changes the probability distribution of the other indexes. Let's do an example, with $n=3$:

$S(n) = [0, 1, 2]$, and $n_2$ has to be 4, so $S(n_2) = [0, 1, 2, 3]$. Let's shuffle $S(n_2)$, and see what happens to the indexes we get. Before we know any of the assignments, the first element in $S(n)$ has probability $\frac{1}{4}$ for each of the possible indexes, and so do all the other elements. But let's say we already know that the first element has index $3$. Then neither of the other elements can have index 3, and thus they have probability $\frac{1}{3}$ for each of the indexes 0, 1 and 2.

This goes on, and it generalizes to longer lists. And if this situation is OK with you, then your algorithm is fine.

-

As André and Arthur have pointed out, the labels generated by your algorithm will not be truly independent: knowing that, say, $S(n)[1] = 3$ reduces the probability that any other element of $S(n)$ will have the label $3$.

In particular, assume that we know the labels of $k = k_1 + k_2 + k_3 + k_4 < n$ elements of $S(n)$, such that $k_1$ of those elements have the label $1$, $k_2$ have the label $2$ and so on. I'll also assume that we know the value of $n_2$ used to generate the labels. Then the probability of some element of $S(n)$, other than one of those whose label we know, having the label $i$ is equal to $$P_i = \frac{\frac14 n_2-k_i}{n_2 - k}.$$ To see why this is so, note that $n_2 - k$ is the total number of labels in $S(n_2)$ that don't belong to any of the $k$ known elements, while $\frac14 n_2 - k_i$ is the number of those labels that have the value $i$.

In particular, this implies that, if we only know the labels of a few elements out of many, the conditional distribution of the other labels is still pretty close to uniform: $k \ll n_2 \implies P_i \approx \frac14$. Also, if the labels we do know are pretty evenly distributed, such that $k_i \approx \frac14 k$ (and, in particular, if $|k_i - \frac14 k| \ll n_2 - k$), then $P_i$ is also close to $\frac14$.

Thus, as long as there are many elements in $S(n)$, and we know the labels of only a few of them, the remaining labels will seem pretty close to random. However, this only holds if $n_2$ (and thus $n$) is large enough: for example, as Arthur demonstrates, if $n_2 = 4$ even knowing the label of just one element is enough to bias the distribution of the other labels significantly.

-