Sniff out biased random permutations

Question

The brilliant engineers at <enter company you love to hate> have struck again. This time they've "revolutionised" the generation of random permutations. "Every great invention is simple" they say and their magical new algorithm is as follows:

• Start with a list 1,2,3,...,n of numbers to permute.
• For each element x in the list draw a random index in the list and swap x and the element at the random index

Then they "prove" that this is unbiased because each element occurs at each position with equal frequency.

Obviously, their reasoning is flawed because their method has n^n equally likely outcomes which typically is not a multiple of n!

Your task is as follows: Write a program / function that accepts a list / stream / generator / iterator (whatever makes most sense in your language of choice) of permutations and decides whether they are a biased sample as created by the algorithm above or not. If not you may assume that the sample is unbiased.

n will be 3 or more. You can set a minimum sample size as you see fit,

Your program may err on small samples but must converge to the correct answer as the sample size increases.

You may output True/False or any two values (but not groups of values: so for example empty list vs. nonempty list is not allowed unless the nonempty list is always the same)

Apart from that standard rules apply.

This is code-golf, smallest function or program in bytes wins. Different languages compete independently.

Python 3 Test case generator

import random

def f(n,biased=True,repeats=10,one_based=False):
  OUT = []
  for c in range(repeats):
    out = [*range(one_based,n+one_based)]
    OUT.append(out)
    for i in range(n):
      o = random.randint(i-i*biased,n-1)
      out[o],out[i] = out[i],out[o]
  return OUT

Try it online!

Additional hints

Now that @AndersKaseorg has let the cat out of the bag I see no harm in giving a few more hints.

Even though it may look plausible at first sight it is not true that elements are uniformly distributed over positions.

We do know:

1. Directly after the nth element was swapped with a random position the element at position n is truly uniformly random. In particular, in the final state the last position is uniformly random.

2. Before that the nth element is guaranteed to be equal or smaller than n

3. Whatever is swapped downwards from position n to m can only be returned to n at the nth move. In particular, it can't be if the original move was the nth in the first place.

4. If we rank positions by their expectation after the kth move then positions m and n can overtake each other only at the mth or nth move.

5. Select values:

• The base (i.e. first or zeroth) element's position is uniformly random. This holds after the first swap and remains true from there on.

• The next element is over-represented in the first position: Out of n^n possible draws it occurs in (n-1) x n^(n-2) + (n-1)^(n-1) instances.

• The last element is under-represented in the first position: Out of n^n possible draws it occurs in 2 x (n-1)^(n-1) instances.

More demo / test code

5 can be used to solve this challenge in a similar but perhaps slightly less golfable way to Anders's answer.

Answer 1

Python 3, 45 43 bytes

(−2 bytes from xnor)

lambda v:sum(r<r[-1:]for r in v)/len(v)>.51

Try it online!

How it works

Computes the fraction of samples where the first entry is less than the last entry. For unbiased input, this converges to \$\frac12\$.

For biased input, the last entry is uniform, but the first entry is less than a uniform one with probability

$$\frac{(3n - 2)(n - 1)^{n - 1}}{2n^n},$$

which is \$\frac{14}{27} ≈ 0.518518\$ at \$n = 3\$, and increases toward \$\frac{3}{2e} ≈ 0.551819\$ as \$n → ∞\$.

This calculation ignores a slight anti-correlation between the first and last entries for \$n ≥ 4\$, but we can bound it and show that it’s much too small to affect correctness. Here are the exact probabilities computed by dynamic programming.

Answer 2

R, 94 78 74 56 bytes

Edit: -12 bytes thanks to Giuseppe, and -6 bytes and corrected (I hope) maths thanks to Anders Kaseorg

function(m,n=max(m))var(t<-table(n^(1:n)%*%m))/mean(t)>2

Try it online!

Input is a matrix m with each row representing a permutation.

If permutations are unbiased, then all permutations should occur with the same observed frequency t (with k samples, mean(t)==k/factorial(n)), and with an expected variance equal to the mean (binomial variance = k*p*q = k*(1/factorial(n))*(1-1/factorial(n)) = mean(t)*(1-1/factorial(n)) = mean(t) after correction for sample size factorial(n)).

We guess that sampling is biased if the variance is greater than twice the mean. Simulations indicate that this is sufficient to detect biased samples with n=3, and the difference becomes bigger (so, easier to detect) at larger n. As n increases, though, the number of permutations needs to be quite large for the guess to be reliable.

---

Addendum: Note that a port of Anders Kaseorg's approach, which is much better tailored to detect exactly this type of biased permutations (rather than simply any biased set of permutations) is 19 bytes shorter:
function(m)mean(m[1,]<m[max(m),])<.51 (try it).

Answer 3

Charcoal, 20 bytes

›₂⌈Ｅθ№θι⊕₂∕ＬθΠ…·¹Ｌ⊟θ

Try it online! Link is to verbose version of code. Outputs - if it thinks the list of permutations is biased. (Test case consists of 768 biased permutations of four elements.) Explanation:

    θ                   Input list
   Ｅ                    Map over elements
     №                  Count of
       ι                Current element
      θ                 In input list
  ⌈                     Maximum
 ₂                      Square root
›                       Is greater than
            θ           Input list
           Ｌ            Length
          ∕             Divided by
                   θ    Input list
                  ⊟     Last element
                 Ｌ      Length
             Π…·¹       Factorial
         ₂              Square root
        ⊕               Incremented
›                       Implicitly print

A port of @AndersKaesorg's answer would be just 16 bytes:

‹·⁵¹∕ΣＥ苧ι⁰⊟ιＬθ

Try it online! Link is to verbose version of code. Outputs - if it thinks the list of permutations is biased. (Test case consists of 256 biased permutations of four elements.)