2004/04/13 by Edward A. Bender, Bender, Edward A., Gregory F. Lawler +5
Computer Science · Mathematics · #05A15 (Primary) 60C05 (Secondary) #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #Probability and Statistical Research #Stochastic processes and statistical mechanics #math.CO #math.PR #msc:05A15 #msc:60C05
paper · pdf · doi:10.48550/arxiv.math/0404253
arxiv created 2004/04/13 · openalex publication_date 2004/04/13 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 √(V/(2 π)) n-3/2. We prove this via two methods, one analytic and one probabilistic.