Séminaire Lotharingien de Combinatoire, B50h (2004), 13 pp.
Edward E. Bender, Gregory F. Lawler, Robin Pemantle and Herbert S. Wilf
Irreducible Compositions and the First Return to the Origin
of a Random Walk
Abstract.
Let n = b1 + ... + bk =
b1' + ... + bk' be a pair of
compositions of n into k positive parts. We say this pair is
{\em irreducible} if there is no positive j<k for which
b1 + ... + bj
= b1' + ... + bj'.
The probability that a random pair of compositions
of n is irreducible is shown to be asymptotic to 8/n. This problem
leads to a problem in probability theory. Two players move along a game
board by rolling a die, and we ask when the two players will first coincide.
A natural extension is to show that the probability of a first return to
the origin at time n for any mean-zero variance V random walk is
asymptotic to \sqrt{V/(2\pi)} n-3/2. We prove this via two
methods, one analytic and one probabilistic.
Received: April 13, 2004.
Accepted: September 1, 2004.
Final Version: September 19, 2004.
The following versions are available: