ON WAITING TIME FOR REVERSED PATTERNS IN RANDOM SEQUENCES

SIGEO AKI^{1} AND KATUOMI HIRANO^{2}

1Department of Informatics and Mathematical Science, Graduate School of Engineering Science,

Osaka University, 1-3 Machikaneyama-cho, Toyonaka 560-8531, Japan

2The Institute of Statistical Mathematics, 4-6-7 Minami-Azabu, Minato-ku, Tokyo 106-8569, Japan

(Received March 27, 2000; revised April 13, 2001)

Abstract. By using a combinatorial method it is shown that for every finite pattern, the distribution of the waiting time for the reversed pattern coincides with that of the waiting time for the original pattern in a multi-state dependent sequence with a certain type of exchangeability. The number of the typical sequences until the occurrence of a given pattern and that of the typical sequences until the occurrence of the reversed pattern are shown to be equal. Further, the corresponding results for the waiting time for the r-th occurrence of the pattern, and for the number of occurrences of a specified pattern in n trials are also studied. Illustrative examples based on urn models are also given.

Key words and phrases: Discrete distribution, exchangeability, multi-state dependent sequence, reversed pattern, typical sequence, urn model, waiting time problem.