A note on occurrence of gapped patterns in i.i.d. Sequences (Q2462355)

A gapped pattern is defined as an item composed of two fixed patterns separated by a variable gap. The author develops a technique to find formulas for the expected value and generating function of the waiting time until a given gapped pattern occurs in an i.i.d. sequence of random letters from a finite alphabet. The author's approach leans heavily on a martingale technique introduced by \textit{S-Y. R. Li} [Ann. Probab. 8, 1171--1176 (1980; Zbl 0447.60006)] to treat occurrence of patterns in i.i.d. sequences of random letters. It is shown that the approach proposed presents a significant computational advantage over any method based on the occurrence of compound patterns.