5
$\begingroup$

Suppose you have a sequence of N numbers. You check the sequence and see if it's sorted in ascending order . If not, you shuffle it (i.e., randomly permute the order of its elements) and check again. How many checks do you need to perform, in average, before seeing a sorted sequence? I believe the answer is N!, and (I think) I have a proof, but I would like to see how you would go around proving it, because I don't think my proof is the most elegant/straightforward.

$\endgroup$
  • 2
    $\begingroup$ N unique numbers? $\endgroup$ – shimao Nov 26 '19 at 19:18
  • $\begingroup$ @shimao good observation. Let's consider both case: unique vs non-unique (duplicates are allowed) $\endgroup$ – DeltaIV Nov 26 '19 at 22:27
7
$\begingroup$

Let us start by assuming $N$ unique entries in our vector.

The action of randomly shuffling a vector and checking whether it is sorted in a particular order afterwards is equivalent to picking a permutation at random and checking whether it is one very specific one, namely the one that orders the vector in the order we want.

The permutation group of a set with $N$ elements has $N!$ elements. By assumption, each permutation is equally probable.

Your experiment thus is an iterated sampling from a Bernoulli distribution with a success probability of $p=\frac{1}{N!}$. The number of trials until the first success is geometrically distributed, and the expectation you are looking for is the expected number of draws until the first success. Which is the expectation of our geometric distribution, namely $\frac{1}{p}=N!$.

We can extend the treatment for duplicates. Suppose the vector has $n$ unique entries, each one appearing $k_1, k_2, \dots, k_n$ times, so $k_1+k_2+\dots+k_n=N$. Then two permutations of the vector will yield the same vector if they only differ by reorderings within each separate entry. And there are $k_1!k_2!\cdots k_n!$ permutations within each entry. So the overall permutation group of our vector with multiplicities has $\frac{N!}{k_1!k_2!\cdots k_n!}$ permutations that actually result in different vectors. The rest of the analysis runs as above, so the result is that we expect to have to draw $\frac{N!}{k_1!k_2!\cdots k_n!}$ permutations before seeing an ordered vector.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ very similar to my proof, but I didn't know about the geometric distribution and its expectation, so I had to explictly compute the average number of Bernoulli trials to get a success. BTW, I believe there's an error in Wikipedia: it states that The expected value, expected number of failures before the first success, of a geometrically distributed random variable X is 1/p. However, this is the expected number of trials to get a success, i.e., the number of failures + 1. At least, if my calculations are correct. $\endgroup$ – DeltaIV Nov 26 '19 at 22:37
  • 1
    $\begingroup$ There is indeed an error in Wikipedia there. The expected number of trials is 1/p, the expected number of failures is one less, as you say. $\endgroup$ – Glen_b Nov 27 '19 at 0:35
  • 1
    $\begingroup$ Yes indeed. To me, "before seeing a sorted sequence" includes the final draw, because you have to run the last random permutation before actually finding out it was a success, so the result is correct, even if Wikipedia has an Obiwan error. $\endgroup$ – Stephan Kolassa Nov 27 '19 at 7:37
  • 1
    $\begingroup$ Thanks! To be honest, at first I took it for granted that the waiting time for a Bernoulli with parameter $p$ would be $\frac{1}{p}$ and handwaved that, but then started googling for "waiting time Bernoulli" and edited the answer. So whether you classify this as trivial would depend on whether you think the combinatorics are (I'd say yes) and whether you think the waiting time calculation with the geometric distribution is (I'd say no, but we can use established results). $\endgroup$ – Stephan Kolassa Nov 27 '19 at 8:19
  • 1
    $\begingroup$ And your edit is completely correct. Sorry for the typo. I'm getting confused about reloading and refreshing, too... $\endgroup$ – Stephan Kolassa Nov 27 '19 at 8:22

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.