| Séminaire Lotharingien de Combinatoire 52 (2004), Article B50h Irreducible compositions and the first return to the origin of a random walk (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract. Let n = b1 + · · · + bk = b ′ 1 + · · · + b ′ k be a pair of compositions of n into k positive parts. We say this pair is irreducible if there is no positive j < k for which b1 + · · · + bj = 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 � V/(2π)n−3/2. We prove this via two methods, one analytic and one probabilistic. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||