Martingale Methods for Patterns and Scan Statistics
V. A. Pozdnyakov, J. Michael Steele · Birkhäuser Boston eBooks · 2009
We show how martingale techniques (both old and new) can be used to obtain otherwise hard-to-get information for the moments and distributions of waiting times for patterns in independent or Markov sequences. In particular, we show how these methods provide moments and distribution approximations for certain scan statistics, including variable length scan statistics. Each general problem that is considered is also illustrated with a concrete example confirming the computational tractability of the method.