On the expected time of the first occurrence of every k bit long patterns in the symmetric Bernoulli process (Q1086903)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the expected time of the first occurrence of every k bit long patterns in the symmetric Bernoulli process |
scientific article |
Statements
On the expected time of the first occurrence of every k bit long patterns in the symmetric Bernoulli process (English)
0 references
1986
0 references
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.
0 references
stopping time
0 references
symmetric Bernoulli process
0 references
Euler constant
0 references