SHIFT TRANSFORM APPROACH TO THE TWO-SIDED BALLOT THEOREM

Abstract

We present a recursive formula for the two-sided ballot theorem using left and right shift transforms. In particular, we showed that the xth entry of the image of the d + 1 dimensional unit vector under the sum of the left and right shift operators is the number of walks in the lattice interval [0,d] that start at the origin and stop at the location x. This approach enables us to write a recursive formula for the number of possible n−walks between two obstacles that stop at a predetermined location.

Keywords

• ballot theorem
• random walk
• self-avoiding walk
• reflection method.

References

1. [1] A. Aeppli, Zur Theorie verketteter Wahrscheinlichkeitem, Markoffsche Ketten h ̈oherer Ordnung, Ph.D. Thesis, Eidgenössische Technische Hochschule, Zürich, 1924.
2. [2] D. Andr ́e, Solution directe du probl`eme r ́esolu par M. Bertrand, Comptes Rendus de l’Acad ́emie des Sciences, Paris 105 (1887) 436-437.
3. [3] E ́. Barbier, G ́en ́eralisation du probl`eme r ́esolu par M. J. Bertrand, Comptes Rendus de l’Acad ́emie des Sciences, Paris 105 (1887) p.407.
4. [4] J. Bertrand, Solution d’un probl`eme, Comptes Rendus de l’Acad ́emie des Sciences, Paris 105 (1887) p.369.
5. [5] W. Feller, An introduction to probability theory and its applications, Vol. 1, (third edition, revised), John Wiley and Sons, 1970.
6. [6] P. A. MacMahon, Memoir on the theory of the partitions of numbers, part iv: on the probability that the successful candidate at an election by ballot may never at anytime have fewer votes than the one who is unsuccessful; on a generalization of this question; and its connection with other questions of partition, permutation, and combination, Philosophical Transactions of the Royal Society of London, Series A 209 (1909) 153- 175.
7. [7] T. V. Narayana, Lattice path combinatorics with statistical applications, University of Toronto Press, 1979.
8. [8] M. Renault, Four proofs of the ballot theorem, Math. Mag. 80 (2007), 345-352.

9. [9] R. Srinivasan, On some results of Taka ́cs in ballot problems, Discrete Math. 28 (1979), 213-218.
10. [10] L. Tak ́acs, On the ballot theorems, Advances in Combinatorial Methods and Applications to Probability and Statistics, Birkha ̈user, 1997.