Irreducible compositions and the first return to the origin of a random walk
| dc.creator | Bender, Edward A. | |
| dc.creator | Lawler, Gregory F. | |
| dc.creator | Pemantle, Robin | |
| dc.creator | Wilf, Herbert S. | |
| dc.date | 2004-04-13 | |
| dc.date.accessioned | 2026-07-07T05:07:25Z | |
| dc.date.available | 2026-07-07T05:07:25Z | |
| dc.description | Let $n = b_1 + ... + b_k = b_1' + \cdot + 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 π)} n^{-3/2}$. We prove this via two methods, one analytic and one probabilistic. | |
| dc.identifier | https://arxiv.org/abs/math/0404253 | |
| dc.identifier | http://arxiv.org/abs/math/0404253 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/70855 | |
| dc.subject | Combinatorics | |
| dc.subject | Probability | |
| dc.subject | 05A15 (Primary) 60C05 (Secondary) | |
| dc.title | Irreducible compositions and the first return to the origin of a random walk | |
| dc.type | text |