1
$\begingroup$

Here's yet another question from my probability textbook:

In a company of sixty members, each member votes for one of the members to fill an office. If the votes be regarded as given at random, what is the chance that some member shall get a majority of the whole number of votes?

Assuming majority (i.e. at least $31$ votes) and not plurality (i.e. more votes than the candidate with the second most votes), then I ended up getting$${{\binom{60}{31} 59^{29} + \binom{60}{32} 59^{28} + \ldots + \binom{60}{59}59 + \binom{60}{60}}\over{60^{60}}}.$$The numerator recognizably looks like a fraction of $(59 + 1)^{60}$. I've messed around with trying to simplify it, not to any success. Could anyone help?

EDIT: Robert Shore writes helpfully in the comments:

I think your fraction gives the probability that a specific member gets a majority of votes, so you need to multiply it by $60$.

So the expression I want to simplify is actually$$60\left({{\binom{60}{31} 59^{29} + \binom{60}{32} 59^{28} + \ldots + \binom{60}{59}59 + \binom{60}{60}}\over{60^{60}}}\right) = {{\binom{60}{31} 59^{29} + \binom{60}{32} 59^{28} + \ldots + \binom{60}{59}59 + \binom{60}{60}}\over{60^{59}}}.$$

$\endgroup$
8
  • $\begingroup$ I think your fraction gives the probability that a specific member gets a majority of votes, so you need to multiply it by $60$. $\endgroup$ Commented Sep 3, 2021 at 15:35
  • $\begingroup$ Your expression still has mistakes but in any case I do not think it can be simplified. It does lead to a hypergeometric function. $\endgroup$
    – Math Lover
    Commented Sep 3, 2021 at 15:56
  • $\begingroup$ @MathLover What are the mistakes? $\endgroup$ Commented Sep 3, 2021 at 15:56
  • $\begingroup$ It should be ${60 \cdot 59 \cdot\big[{\binom{59}{31} 58^{28} + \binom{59}{32} 58^{27} + \ldots + \binom{59}{58}58 + \binom{59}{59}\big]}\over{59^{60}}}$ $\endgroup$
    – Math Lover
    Commented Sep 3, 2021 at 16:01
  • 2
    $\begingroup$ @MathLover Nowhere in the problem statement does it say one can't vote for oneself though. $\endgroup$ Commented Sep 3, 2021 at 16:04

2 Answers 2

1
$\begingroup$

Let $X$ be a random variable with the $\text{Binomial}(60, \frac1{60})$ distribution: we do $60$ trials, each with probability of success $\frac1{60}$, and we want to know the number of successes. In particular, this is the distribution of the number of votes that any specific member gets. So $\Pr[X \ge 31]$ is the probability that a specific person gets a majority of the votes, and $60 \cdot \Pr[X \ge 31]$ is the probability that this happens to anyone.

Since we cannot exactly compute $\Pr[X \ge 31]$ except with the very long sum $\sum_{k=31}^{60} \binom{60}{k} (\frac1{60})^k (\frac{59}{60})^{n-k}$, we want to find approximations.


First, we can observe that if $\Pr[X \ge 31]$, then the likeliest outcome by far is that $\Pr[X=31]$ exactly. (And we can be more precise about how insignificant the other terms are.)

How does $\Pr[X=31]$ compare to $\Pr[X=32]$? The first is $\binom{60}{31} (\frac1{60})^{31} (\frac{59}{60})^{29}$. The second is $\binom{60}{32} (\frac1{60})^{32} (\frac{59}{60})^{28}$. We can say $\binom{60}{31} > \binom{60}{32}$, but there's actually not a huge relative difference there: $\binom{60}{32} = \frac{29}{32} \binom{60}{31}$. On the other hand, $ (\frac1{60})^{31} (\frac{59}{60})^{29}$ is bigger than $(\frac1{60})^{32} (\frac{59}{60})^{28}$ by a factor of $59$.

So we can say that $\Pr[X=32] = \frac{29}{32\cdot 59} \Pr[X=31] < \frac1{65} \Pr[X=31]$. In future steps, the decrease will be even steeper, because the binomial coefficients will begin to fall off even faster! So we can say that $\Pr[X=31+k] < (\frac1{65})^k \Pr[X=31]$. And in conclusion $$ \Pr[X=31] \le \Pr[X \ge 31] \le \Pr[X=31]\left(1 + \frac1{65} + \frac1{65^2}+ \dots \right) = \frac{65}{64} \Pr[X \ge 31]. $$ So if we estimate $\Pr[X \ge 31]$ just by the first term $\binom{60}{31} \frac{59^{29}}{60^{60}}$, and then multiply by $60$ because we want $60 \cdot \Pr[X \ge 31]$, we'll get the answer to within a relative error of $\frac1{64}$.

If we take the first two terms into account, the error becomes even better than that.


It might still be annoying to compute $60 \cdot \binom{60}{31} \frac{59^{29}}{60^{60}}$. So we can approximate this further.

We can estimate $\binom{n}{n/2} \approx \frac{2^n}{\sqrt{\pi n/2}}$ in two ways:

  1. By applying Stirling's approximation to the factorials $n!$ and $(n/2)!$.
  2. By applying a normal approximation to $\text{Binomial}(n, \frac12)$ and estimating the probability that it is equal to $n/2$.

Very imprecisely, $\binom{60}{31}$ is about equal to $\binom{60}{30}$, so it is approximately $\frac{2^{60}}{\sqrt{30\pi}}$. This gives us a final approximation of $$ 60 \cdot \frac{2^{60} \cdot 59^{29}}{\sqrt{30\pi} \cdot 60^{60}} \approx 3.2995 \cdot 10^{-37}. $$ We can be a little more precise and add that $\binom{60}{31} = \frac{30}{31} \binom{60}{30}$, which gives $$ \frac{30}{31} \cdot 60 \cdot \frac{2^{60} \cdot 59^{29}}{\sqrt{30\pi} \cdot 60^{60}} \approx 3.1931 \cdot 10^{-37}. $$ For comparison, the exact value is approximately $3.2294 \cdot 10^{-37}$.

$\endgroup$
1
$\begingroup$

The probability P(K,n) that person #K (1 ≤ K ≤ 60) gets exactly n votes out of 60 is

P(K,n) = 60_C_n (1/60)n (59/60)60-n.

Let E(K) be the event that person #K gets a majority of the votes. Then the probability P(K) of this is

P(K) = ∑ P(n,K).

And because the events E(K) are mutually exclusive, the probability that someone gets a majority of the votes is

P = ∑ P(K) = 60 P(1).

$\endgroup$
1
  • $\begingroup$ This is the same as the expression already given in the question. $\endgroup$ Commented Sep 3, 2021 at 17:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .