Skip to main content
1 of 3

What is the generalization of the formula for Chung and Feller's Theorem 2 to odd numbers of steps?

In their classical paper on fluctuations in coin tossing

https://www.pnas.org/content/35/10/605

Chung and Feller give a precise formula for the conditional probability of the number of positive ``sides'' of a random walk with an even number of steps, given a particular outcome for the endpoint. $$ \mathbf{P}\left(\sum_{j=1}^{2n} \mathbf{1}_{(0,\infty)}\left(\frac{\mathsf{X}_{j-1}+\mathsf{X}_j}{2}\right)=2k\, \bigg|\, \mathsf{X}_{2n}=2\ell\right)\, =\, \frac{\ell}{\binom{2n}{n-\ell}}\, \sum_{i=\ell}^{k} \binom{2i}{i-\ell} \binom{2n-2i}{n-i}\, \cdot \frac{1}{i(n-i+1)} $$ for a simple random walk $(\mathsf{X}_0,\mathsf{X}_1,\dots,\mathsf{X}_{2n})$.

For their Theorem 1 $$ \mathbf{P}\left(\sum_{j=1}^{2n} \mathbf{1}_{(0,\infty)}\left(\frac{\mathsf{X}_{j-1}+\mathsf{X}_j}{2}\right)=2k\right)\, =\, u_{2k} u_{2n-2k}\, ,\ \text{ for }\ u_{2k}\, =\, \mathbf{P}(\mathsf{X}_{2k}=0)\, =\, \frac{1}{2^{2k}} \binom{2k}{k}\, , $$ the generalization to odd times was performed somewhat recently by Gessel in slides

Chung -Feller Theorems last few slides,

and by Gr:unbaum in an article

A Feynman-Kac approach to a paper of Chung and Feller on fluctuations in the coin-tossing game

published in Proceedings of the American Mathematical Society. The answer for that generalization is $$ \mathbf{P}\left(\sum_{j=1}^{2n+1} \mathbf{1}_{(0,\infty)}\left(\frac{\mathsf{X}_{j-1}+\mathsf{X}_j}{2}\right)=2k+1\right)\, =\, u_{2k} u_{2n-2k} \cdot \frac{2k+1}{2(n+1)}\, . $$ Incidentally, the problem was apparently also stated as an exercise in McKean's textbook:

Probability: The classical limit theorems Exercise 3.4.2 on p139.

But to the best of my knowledge nobody has stated a generalization of Chung and Feller's conditional distribution results in Theorem 2 to odd numbers of steps. (I might have missed it somewhere.)

Note the analog of their Theorem 2a was the limit/specialization of their Theorem 2 to $\ell=0$ giving a uniform distribution. It makes sense from their Theorem 2a formula if you cancel the $\ell$ in the numerator outside their sum with the $i$ (which is necessarily $0$ in the single-summand sum) in the denominator inside the sum.

As a secondary question, I wonder why combinatorialists sometimes derive useful formulas and advertise them as Gessel (and possibly McKean?) did, but then do not publish them. I have asked that question specifically over at AcademiaSE with more references for an example related to this question

https://academia.stackexchange.com/questions/180689/is-it-common-for-combinatorialists-to-not-publish-all-their-results-if-so-why