Generalized approximate counting revisited
A large class of q-distributions is defined on the stochastic model of Bernoulli trials in which the probability of success (= advancing to the next level) depends geometrically on the number of trials and the level already reached. If the dependency is only on the level already reached, this is an algorithm called approximate counting. Two random variables, X-n (level reached after n trials) and Y-k (number of trials to reach level k) are of interest. We rederive known results and obtain new ones in a consistent way, based on generating functions. We also discuss asymptotics. The classical instance of approximate counting is more interesting from a mathematical point of view. On the other hand, if the number of trials also decreases the probability of success (advancing to the next level), then the limits are constants which are straightforward to compute. (C) 2007 Elsevier B.V. All rights reserved.
approximate counting q-distribution q-analysis markov chain transition probability