Local height in weighted Dyck models of random walks and the variability of the number of coalescent histories for caterpillar-shaped gene trees and species trees

We examine combinatorial parameters of three models of random lattice walks with up and down steps. In particular, we study the height yi measured after i up-steps in a random weighted Dyck path of size (semilength) n. For a fixed integer w ∈ {0, 1, 2} , the considered weighting scheme assigns to each Dyck path of size n a weight ∏_{ i=1}^n y_i^w that depends on the height of the up-steps of the path. We investigate the expected value E_n(y_i) of the height y_i in a random weighted Dyck path of size n, providing exact formulas for E_n(y_i) and E_n(y_i^2 ) when w = 0, 1, and estimates of the mean of y_i for w = 2 . Denoting by i^∗(n) the position i where E_n(y_i) reaches its maximum m(n) , our calculations indicate that, when n becomes large, the pair (i^∗(n),m(n)) grows like (n∕2, 2√n∕) if w = 0 , (3n∕4,n∕2) if w = 1 , and ((9 + √17)n∕16,(1 + √17)n∕8) if w = 2 . These results also contribute to the study of the variability of the number of “coalescent histories”: structures used in models of gene tree evolution to encode the combinatorially different configurations of a gene tree topology along the branches of a species tree. Relationships with other combinatorial and algebraic structures, such as alternating permutations and Meixner polynomials, are also discussed.