In an election for the Peer Pressure High School student council president, there are $2019$ voters and
two candidates Alice and Celia (who are voters themselves). At the beginning, Alice and Celia both
vote for themselves, and Alice’s boyfriend Bob votes for Alice as well. Then one by one, each of the
remaining $2016$ voters votes for a candidate randomly, with probabilities proportional to the current
number of the respective candidate’s votes. For example, the first undecided voter David has a $2/3$ probability of voting for Alice and a $1/3$ probability of voting for Celia.
What is the probability that Alice wins the election (by having more votes than Celia)?
Let $P_n(m)$ be the probability that Alice receives $m$ votes after $n$ voters having voted. We are going to show that for $n\ge 3$, the following ratios holds $$P(2):P(3):\cdots:P(n-1)=1:2:\cdots:(n-2)$$
When $n=3$, $P(2)=1$ holds by the given information. Assuming that the claim also holds when $n=k$. Then $$P_k(m)=\frac{m}{1+2+\cdots+(k-2)}=\frac{2(m-1)}{(k-1)(k-2)}$$
Then when $n=k+1$, there are only two cases for Alice to receive $m$ votes.
- She has already received $m$ before this round and does not win the $(k+1)^{th}$ vote.
- She has only received $(m-1)$ votes before this round and wins the $(k+1)^{th}$ vote.
The probabilities that Alice has received $m$ and $(m-1)$ votes before this round equal $P_k(m)$ and $P_k(m-1)$, respectively. When Alice has already received $m$ votes, her chance of winning vs losing the next vote is $m:(k-m)$. When she has only received $(m-1)$ votes, her chance of winning vs losing the next vote is $(m-1):(k-m+1)$. Therefore, we find $$\begin{align*} P_{k+1}(m)=\ &\frac{k-m}{k}P_k(m)+\frac{m}{k}P_k(m-1)\\=\ &\frac{k-m}{k}\frac{2(m-1)}{(k-1)(k-2)} + \frac{m-1}{k}\frac{2(m-2)}{(k-1)(k-2)}\\=\ &\frac{2(m-1)}{k(k-1)}\end{align*}$$
Meanwhile the initial value $P_{k+1}(2)$, i.e. the chance that Alice loses all votes after her initial two votes is $$P_{k+1}(2)=P_3(2)\cdot\frac{1}{3}\cdot\frac{2}{4}\cdot\frac{3}{5}\cdot\frac{4}{6}\cdots\frac{k-3}{k-1}\frac{k-2}{k}=\frac{2}{k(k-1)}$$
This means that previously derived formula $P_{k+1}(m)=\frac{2(m-1)}{k(k-1)}$ holds for $m=2$. Similarly, it can also be shown that this formula holds for $m=k$ too. Therefore, it can be concluded that $$P(2):P(3):\cdots:P(k):P(k+1)=1:2:\cdots:(k-1):k$$
Hence, by the principle of mathematical induction, the ratio holds for all $n\ge 3$.
Note that Alice has received at least $2$ votes and can receive at most $2018$ votes (because Celia has voted for herself). Meanwhile, a minimal of $1010$ votes is necessary to win the election. We can verify that $$\sum_{k=2}^{2018}P_{2019}(k)=\sum_{k=2}^{2018}\frac{2(k-1)}{2018\times 2017}=1$$
Hence, the probability that Alice wins equals $$\sum_{k=1010}^{2018}P_{2019}(k) = \sum_{k=1010}^{2018}\frac{2(k-1)}{2018\times 2017}=\frac{(1009+2017)(2017-1009+1)}{2018\times 2017}=\boxed{\frac{1513}{2017}}$$