In this paper we consider the Markov process defined by

P1,1=1, Pn,[lscr]=(1−λn,[lscr])·Pn−1,[lscr]+λn,[lscr]−1·Pn−1,[lscr]−1

for transition probabilities λn,[lscr]=q[lscr] and λn,[lscr]=qn−1. 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.