#####
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* = *b*_{1} + ... + *b*_{k} =
*b*_{1}' + ... + *b*_{k}' 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
*b*_{1} + ... + *b*_{j}
= *b*_{1}' + ... + *b*_{j}'.
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: