Words in Random Binary Sequences I

Abstract

When flipping a fair coin, let $W=L_1{L}_2...L_N$ with $L_i\in \{H,T\}$ be a binary word of length $N=2$ or $N=3$. In this paper, we establish second- and third-order linear recurrence relations and their generating functions to discuss the probabilities $p_W(n)$ that binary words $W$ appear for the first time after $n$ coin tosses.