The relevant prefixes of coloured Motzkin walks: An average case analysis

In this paper we study some relevant prefixes of coloured Motzkin walks (otherwise called coloured Motzkin words). In these walks, the three kinds of step can have α,β and γ colours, respectively. In particular, when α=β=γ=1 we have the classical Motzkin walks while for α=γ=1 and β=0 we find the well-known Dyck walks. By using the concept of Riordan arrays and probability generating functions we find the average length of the relevant prefix in a walk of length n and the corresponding variance in terms of α,β and γ. This result is interesting from a combinatorial point of view and also provides an average case analysis of algorithms related to the problem of ranking and generating uniformly at random the coloured Motzkin words.