Why a shuffling algorithm is not uniformly random between [1, N)?

Question

I've been taught that simple shuffle algorithm will not be uniformly random if the interval for the random numbers is not [1, N), i.e. it can't be from 0 to N, it must be from 1 to N-1.

I'm trying to understand why and I know it has to do with shuffling the first and last items but I can't come up with a proof.

Reference method:

public static void shuffle(Object[] items) {
        int N = items.length;
        for (int i = 0; i < N; i++) {
            int r = randomUniform(1, N-1);
            exchange(items, i, r);
        }
}

Answer 1

Note that you've essentially taken as your random input $(N-1)^N$ equally likely values - you've picked from $1$ to $N-1$, $N$ times.

But the total number of shuffles is $N!$. And for each shuffle to be equally likely, you'd need $N!$ to be a divisor of $(N-1)^N$. This is not possible, because $N,$ a divisor of $N!$ is relatively prime to $(N-1)$, and hence not a divisor of $(N-1)^N$.

This shows something a bit stronger, actually - that if $D$ is a natural number and you shuffle a deck with $N$ cards by selecting repeated $k$ times a uniform random number from $1$ to $D$ and applying any operation based on that number, then, at minimum to assure pure randomness, $D$ has to be divisible by every prime from $1$ to $N$. That's because if $D^k$ needs to be divisible by $N!$ (so you can actually put stronger conditions, depending on what you know about $k$.)

The standard shuffling algorithm uses different ranges at each step, so that the product is divisible by $N!$. It does so in $N-1$ steps. Can you imagine what the ranges of the random numbers are for that algorithm?

Answer 2

With this shuffle, you will always have the first element out of place.

i.e. that probability of the first element staying in place is $0$, and is not $1/N$ as the uniform distribution requires.