Cyclic permutation of lattice paths and the Chung-Feller theorem

Abstract

Abstract A celebrated theorem of Chung and Feller [2, p. 72] may be stated as follows. Consider the minimal lattice paths from the origin to the point (, n). Let L2k·2n be the number of paths with 2k sides lying above the diagonal x = y (and 2 - 2k below) for k = 0,1, ... ,. Then independently of k. This result was first proved by complicated analytical methods in [1]. Simple induction proofs are given in [2], [3]. Yet another proof, which is applicable in much more general situations and also yields many deep results on the maximum of partial sums of random variables follows from Spitzer's work [4].