Geodesic
Irreducible Compositions and the First Return to the Origin of a Random Walk
Séminaire lotharingien de combinatoire, Tome 50 (2003-2005)

Voir la notice de l'acte provenant de la source Séminaire Lotharingien de Combinatoire website

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 jk 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 \sqrt{V/(2\pi)} n-3/2. We prove this via two methods, one analytic and one probabilistic. 

@article{SLC_2003-2005_50_a7,
     author = {Edward E. Bender and Gregory F. Lawler and Robin Pemantle and Herbert S. Wilf},
     title = {Irreducible {Compositions} and the {First} {Return} to the {Origin} of a {Random} {Walk}},
     journal = {S\'eminaire lotharingien de combinatoire},
     publisher = {mathdoc},
     volume = {50},
     year = {2003-2005},
     url = {http://geodesic.mathdoc.fr/item/SLC_2003-2005_50_a7/}
}
TY  - JOUR
AU  - Edward E. Bender
AU  - Gregory F. Lawler
AU  - Robin Pemantle
AU  - Herbert S. Wilf
TI  - Irreducible Compositions and the First Return to the Origin of a Random Walk
JO  - Séminaire lotharingien de combinatoire
PY  - 2003-2005
VL  - 50
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SLC_2003-2005_50_a7/
ID  - SLC_2003-2005_50_a7
ER  - 
%0 Journal Article
%A Edward E. Bender
%A Gregory F. Lawler
%A Robin Pemantle
%A Herbert S. Wilf
%T Irreducible Compositions and the First Return to the Origin of a Random Walk
%J Séminaire lotharingien de combinatoire
%D 2003-2005
%V 50
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SLC_2003-2005_50_a7/
%F SLC_2003-2005_50_a7
Edward E. Bender; Gregory F. Lawler; Robin Pemantle; Herbert S. Wilf. Irreducible Compositions and the First Return to the Origin of a Random Walk. Séminaire lotharingien de combinatoire, Tome 50 (2003-2005). http://geodesic.mathdoc.fr/item/SLC_2003-2005_50_a7/