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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ How do they vote? Randomly (with uniform probability)? $\endgroup$
    – user2974951
    Commented Sep 28, 2021 at 5:39
  • $\begingroup$ Yes , they are not aware of each others' votes $\endgroup$
    – Coel Locandro
    Commented Sep 28, 2021 at 5:39
  • 2
    $\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 ♦
    Commented Sep 28, 2021 at 13:48

1 Answer 1

Reset to default
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
Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Mathematica evaluates your expression to $1.7827\times 10^{-10}$. $\endgroup$
    – COOLSerdash
    Commented Sep 28, 2021 at 8:21
  • 1
    $\begingroup$ That is correct for $n=25$. $\endgroup$
    – gunes
    Commented Sep 28, 2021 at 8:24
  • 2
    $\begingroup$ $[n!/e]/(n-1)^n$ where $[x]$ means round $x$ to the nearest integer gives the result $\endgroup$
    – Henry
    Commented Sep 28, 2021 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
    Commented Sep 28, 2021 at 9:07
  • $\begingroup$ It's a hugely accurate approximation! $\endgroup$
    – whuber ♦
    Commented Sep 28, 2021 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.