In a two candidate election where votes are distributed uniformly at random between the candidates, the probability that the lead changes when tallying the $i$-th vote is the same as the probability that a random walk with $+1, -1$ steps returns to the origin on step $i-1$. The expected number of changes is well known, and is the sum of central binomial coefficients divided by the number of binary strings, and works out to be $O(\sqrt{n})$. I am interested in asymptotic bounds for the more general case when there are $k > 2$ candidates in the election: Asymptotically, what is the expected number of times the leader changes during the tallying of the votes? Is there an asymptotically tight bound for this expected value in terms of both $n$ and $k$?

In "Some Aspects of the Random Sequence" by D. E. Barton and C. L. Mallows, the authors state: "Another problem that yields to the reflection principle is that of finding the number of times the lead changes hands during the counting. Smirnov (1939) and Dwass (1961) give some asymptotic results; Mjihalevic (1952) and Feller (1957a) give some exact formulae. The corresponding problems with more than two candidates are not solved, and seem to be difficult." However, this paper is from 1965, and also talking about more general distributions of votes.

Any references on this topic would be appreciated.

  • $\begingroup$ If you fix $k$ and let $n\to\infty$, then the expectation is still $\Theta(\sqtr{n})$. (There are only $\log n$ times when 3 or more candidates share the lead.) If k$ and $n$ tend to infinity together other asymptotics are possible. Is this what you have in mind? $\endgroup$ – Omer Sep 13 '11 at 18:01
  • $\begingroup$ Yes, I am particularly interested in the asymptotic behavior when $k$ is a function of $n$. For example, is there a function of $n$ to which we can set $k$ such that the expected number of changes is $o(\sqrt{n})$ as $n->\infty$. $\endgroup$ – Kev Sep 13 '11 at 19:15
  • 2
    $\begingroup$ $k(n)=n$ would make the expected number of changes $o(\sqrt n)$ since the lead can only change at most once per possible total, and the probability someone has many more than $k/n$ votes is small. For other $k(n)$, perhaps you should count the values such that there is a tie for the lead with that many votes. $\endgroup$ – Douglas Zare Sep 13 '11 at 20:27

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.