Theory of Probability and Mathematical Statistics
A simple proof of the formula of Solov’ev–Nielsen–Blom for the expected waiting time
Yuuya Yoshida
Link
Abstract: Solov’ev (1966), Nielsen (1973), and Blom (1982) independently showed a formula for the expected waiting time until a given finite pattern first occurs in random data. In this paper, we give a simple and combinatorial proof of the formula.
Keywords: Expected waiting time, random data, combinatorics on words
Bibliography: Gunnar Blom, On the mean number of random digits until a given sequence occurs, J. Appl. Probab. 19 (1982), no. 1, 136–143. MR 644426, DOI 10.2307/3213923
P. Tolstrup Nielsen, On the expected duration of a search for a fixed pattern in random data, IEEE Trans. Inform. Theory IT-19 (1973), 702–704. MR 381817, DOI 10.1109/tit.1973.1055064
A. D. Solov’ev, A combinatorial identity and its application to the problem concerning the first occurrence of a rare event, Theory Prob. Appl. 11 (1966), 276–282.
