Analysis of bidirectional ballot sequences and random walks ending in their maximum (Q505696)

An admissible random walk (lattice path) is a non-negative random walk ending at its maximum. Let \(p_n^{(h)}\) \((q_n^{(h)})\) be the probability that a random walk on \(\mathbb{N}_0\) (\(\mathbb{Z}\)) is admissible of height \(h\). The probability that a random walk on \(\mathbb{N}_0\) (\(\mathbb{Z}\)) is admissible is defined by \(p_n:=\sum_{h\geq 0} p_n^{(h)}\) (\(q_n:=\sum_{h\geq 0} q_n^{(h)}\)). \textit{Y. Zhao} [J. Number Theory 130, No. 5, 1212--1220 (2010; Zbl 1218.11097)] introduced the notion of a bidirectional ballot sequence. It is a \(0\)-\(1\) sequence in which every prefix and suffix contains strictly more \(1\)'s than \(0\)'s. Let \(B_n\) be the number of bidertoral ballot sequences of length \(n\). One of the authors' motivations in this present paper is to prove a conjecture of \textit{Y. Zhao} [J. Number Theory 130, No. 5, 1212--1220 (2010; Zbl 1218.11097)] on the asymptotic behavior of the numbers \(B_n\) as \(n\to\infty\). The authors exploit a bijection between admissible random walks and bidirectoral ballot sequences. They show that the probabilities \(p_n^{(h)}, q_n^{(h)}, p_n\) and \(q_n\) are related to Chebyshev polynomials and focus on the asymptotic distribution of the length of admissible random walks. The asymptotic behavior of the expectation and the variance of the height are also studied.