GENERALIZED WAITING TIME PROBLEMS ASSOCIATED WITH PATTERN IN POLYA’S URN SCHEME

KIYOSHI INOUE AND SIGEO AKI

Department of Informatics and Mathematical Science, Graduate School of Engineering Science, Osaka University, 1-3 Machikaneyama-cho, Toyonaka, Osaka 560-8531, Japan

(Received July 4, 2000; revised February 21, 200)

Abstract. Let X_{1}, X_{2}, … be a sequence obtained by Polya’s urn scheme. We consider a waiting time problem for the first occurrence of a pattern in the sequence X_{1}, X_{2}, …, which is generalized by a notion “score”. The main part of our results is derived by the method of generalized probability generating functions. In Polya’s urn scheme, the system of equations is composed of the infinite conditional probability generating functions, which can not be solved. Then, we present a new methodology to obtain the truncated probability generating function in a series up to an arbitrary order from the system of infinite equations. Numerical examples are also given in order to illustrate the feasibility of our results. Our results in this paper are not only new but also a first attempt to treat the system of infinite equations.

Key words and phrases: Polya’s urn scheme, pattern, generalized probability generating functions, conditional probability generating functions.