Irreducible compositions and the first return to the origin of a random walk

Abstract

Let $n=b_1+...+b_k=b_1^{\prime }+\cdot +b_k^{\prime }$ 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^{\prime }+...b_j^{\prime }$. 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.