On the expected time of the first occurrence of every k bit long patterns in the symmetric Bernoulli process (Q1086903)

In a symmetric Bernoulli process (i.e. an infinite sequence of independent coin tossings) let \(T_ k\) denote the first time when every k bit long pattern has already appeared. As the main result of the paper, an elementary proof is given to the following inequality: \[ 2^ k(\ln 2^ k-\ln k+O(k^{-1}))\leq E(T_ k)\leq 2^{k+2}(\ln 2^ k+C+O(2^{- k})), \] where C stands for the Euler constant.