Markov Processes Involving q-Stirling Numbers

Abstract

In this paper we consider the Markov process defined by

P_1,1=1, P_n,_{[lscr ]}=(1−λ_{n,[lscr ]}) ·P_{n−1,[lscr ]} +λ_{n,[lscr ]−1} ·P_{n−1,[lscr ]−1}

for transition probabilities λ_{n,[lscr ]}=q^{[lscr ]} and λ_{n,[lscr ]}=qⁿ⁻¹. We give closed forms for the distributions and the moments of the underlying random variables. Thereby we observe that the distributions can be easily described in terms of q-Stirling numbers of the second kind. Their occurrence in a purely time dependent Markov process allows a natural approximation for these numbers through the normal distribution. We also show that these Markov processes describe some parameters related to the study of random graphs as well as to the analysis of algorithms.