Geodesic
On the Exit Time of a Random Walk with Positive Drift
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) (2007).

Voir la notice de l'article provenant de la source Episciences

We study a random walk with positive drift in the first quadrant of the plane. For a given connected region $\mathcal{C}$ of the first quadrant, we analyze the number of paths contained in $\mathcal{C}$ and the first exit time from $\mathcal{C}$. In our case, region $\mathcal{C}$ is bounded by two crossing lines. It is noted that such a walk is equivalent to a path in a tree from the root to a leaf not exceeding a given height. If this tree is the parsing tree of the Tunstall or Khodak variable-to-fixed code, then the exit time of the underlying random walk corresponds to the phrase length not exceeding a given length. We derive precise asymptotics of the number of paths and the asymptotic distribution of the exit time. Even for such a simple walk, the analysis turns out to be quite sophisticated and it involves Mellin transforms, Tauberian theorems, and infinite number of saddle points. 
@article{DMTCS_2007_special_253_a7,
     author = {Drmota, Michael and Szpankowski, Wojciech},
     title = {On the {Exit} {Time} of a {Random} {Walk} with {Positive} {Drift}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)},
     year = {2007},
     doi = {10.46298/dmtcs.3525},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3525/}
}
TY  - JOUR
AU  - Drmota, Michael
AU  - Szpankowski, Wojciech
TI  - On the Exit Time of a Random Walk with Positive Drift
JO  - Discrete mathematics & theoretical computer science
PY  - 2007
VL  - DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3525/
DO  - 10.46298/dmtcs.3525
LA  - en
ID  - DMTCS_2007_special_253_a7
ER  - 
%0 Journal Article
%A Drmota, Michael
%A Szpankowski, Wojciech
%T On the Exit Time of a Random Walk with Positive Drift
%J Discrete mathematics & theoretical computer science
%D 2007
%V DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3525/
%R 10.46298/dmtcs.3525
%G en
%F DMTCS_2007_special_253_a7
Drmota, Michael; Szpankowski, Wojciech. On the Exit Time of a Random Walk with Positive Drift. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) (2007). doi : 10.46298/dmtcs.3525. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3525/

Cité par Sources :