SHIFT TRANSFORM APPROACH TO THE TWO-SIDED BALLOT THEOREM

Year 2022, , 1 - 7, 30.06.2022

Kubilay Dagtoros

https://doi.org/10.54559/jauist.1070936

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] A. Aeppli, Zur Theorie verketteter Wahrscheinlichkeitem, Markoffsche Ketten h ̈oherer Ordnung, Ph.D. Thesis, Eidgenössische Technische Hochschule, Zürich, 1924.
• [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] 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] J. Bertrand, Solution d’un probl`eme, Comptes Rendus de l’Acad ́emie des Sciences, Paris 105 (1887) p.369.
• [5] W. Feller, An introduction to probability theory and its applications, Vol. 1, (third edition, revised), John Wiley and Sons, 1970.
• [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] T. V. Narayana, Lattice path combinatorics with statistical applications, University of Toronto Press, 1979.
• [8] M. Renault, Four proofs of the ballot theorem, Math. Mag. 80 (2007), 345-352.
• [9] R. Srinivasan, On some results of Taka ́cs in ballot problems, Discrete Math. 28 (1979), 213-218.
• [10] L. Tak ́acs, On the ballot theorems, Advances in Combinatorial Methods and Applications to Probability and Statistics, Birkha ̈user, 1997.