Extension of Goulden-Jackson cluster method on pattern occurrences in random sequences and comparison with Regnier-Szpankowski method

摘要

The Goulden-Jackson cluster method is a powerful method to find generating functions of pattern occurrences in random sequences [1]. The method is clearly explained, extended and implemented by Noonan and Zeilberger [2]. In this paper, we elaborate on one of the several extensions in [2], namely the extension from symmetrical Bernoulli sequences where the occurrences of each symbol have equal probability, to asymmetrical Bernoulli sequences with different probabilities of symbol generations. An explicit formula is derived for the extension, which is implicitly embedded in the treatment of [2]. The extended result is then compared with the method of Regnier-Szpankowski [3], a method which was developed independently to tackle the same problem. By manipulating some matrix inversions, we show that the Regnier-Szpankowski method can be simplified to the extended Goulden-Jackson method.