Skip to main content
3 of 3
added 64 characters in body

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 On Fluctuations in Coin-Tossing, 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) $$ is equal to $$ \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,\dotsc,\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}\, , $$ for $$ u_0=1\, ,\ \text{ and }\ u_{2k}\, =\, \mathbf{P}(\mathsf{X}_{2k}=0)\, =\, \frac{1}{2^{2k}} \binom{2k}{k}\, ,\ \text{ for $k=1,2,\dots$,} $$ the generalization to odd times was performed somewhat recently by Gessel in slides

Chung–Feller Theorems last few slides,

and by Grünbaum 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:

Is it common for combinatorialists to not publish all their results? If so, why?