3
$\begingroup$

This question seemed simple at first glance, but I quickly realized it was not.

You have a group of 25 candidates with 1 vote each; they cannot vote for themselves. What is the probability of a 25-way tie (that each voter casts their vote for in such a way that all 25 receive only 1 vote)?

Edit: More details. Voters are not aware of each others' votes. The reasoning behind each vote cast for a person is because that voter believes they are most deserving of the title/award.

$\endgroup$
3
  • 1
    $\begingroup$ How do they vote? Randomly (with uniform probability)? $\endgroup$ Sep 28 at 5:39
  • $\begingroup$ Yes , they are not aware of each others' votes $\endgroup$ Sep 28 at 5:39
  • 1
    $\begingroup$ Being "unaware" is not the same as random or uniform. Any definite answer to this question requires a strong assumption about how voters choose their votes. $\endgroup$
    – whuber
    Sep 28 at 13:48
3
$\begingroup$

Yes, it's not trivial because this is about derangements. Total number of choices is $24^{25}$. For everyone to get one vote, we need a permutation, but no one is allowed to vote on himself/herself. This is a derangement, and the number of possible derangements for $n$ is shown with $!n$. So, the answer is $$\frac{!25}{24^{25}}$$

The number of derangements is calculated several ways as laid out in the wikipedia entry. One of them is the simple recursive formula $$!n=(n-1)(!(n-1)+!(n-2))\rightarrow a_n=(n-1)(a_{n-1}+a_{n-2})$$ where $a_n$ is the number of derangements.

According to this series, we have results up to $a_{23}$, but you can easily calculate $a_{25}$.

We can test this for smaller numbers, i.e. for $n=6$, the probability is $$\frac{!6}{5^6}=\frac{265}{15625}\approx 0.017$$

An example matlab program to demostrate this is as follows:

n = 1000000;
c = 0;
m = 6;  % num people

ids = 1:m;
for i = 1:n
    votes = randi(m-1,1,m);
    inds = votes >= ids;
    votes(inds) = votes(inds) + 1;
    if length(unique(votes)) == m
        c = c + 1;
    end
end

disp(c / n)

The output is:

0.0170
$\endgroup$
5
  • 1
    $\begingroup$ Mathematica evaluates your expression to $1.7827\times 10^{-10}$. $\endgroup$ Sep 28 at 8:21
  • 1
    $\begingroup$ That is correct for $n=25$. $\endgroup$
    – gunes
    Sep 28 at 8:24
  • 2
    $\begingroup$ $[n!/e]/(n-1)^n$ where $[x]$ means round $x$ to the nearest integer gives the result $\endgroup$
    – Henry
    Sep 28 at 9:03
  • $\begingroup$ Yes, (+1) that’s one of the approximations in the wikipedia page. I didn’t try many of them. $\endgroup$
    – gunes
    Sep 28 at 9:07
  • $\begingroup$ It's a hugely accurate approximation! $\endgroup$
    – whuber
    Sep 28 at 13:49

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.