Covering with blocks in the non-symmetric case (Q1345083): Difference between revisions

Let \(T(a)\) be the first occurrence time of the run \(a \in X^ n\) in an infinite sequence of letters drawn from the alphabet \(X\) whose letters have probabilities \(0<p_ 1\leq p_ 2 \leq \cdots \leq p_ d\). The covering time \(W_ n\) is the first time at which all runs of length \(n\) have appeared at least once. In the uniform case \((p_ 1 = p_ d)\) the limit distribution of \(W_ n\) as \(n \to \infty\) is known to be a renormalized Gumbel distribution \(F(t) = \exp (-e^{-t})\). The author shows that also in the nonuniform case \(\lim_{n \to \infty} P(\Phi_ n (W_ n) \leq t) = F(t)\) holds and computes the normalization \(\Phi_ n\) explicitly. If \(p_ 1 < p_ 2\), then \(\Phi_ n\) depends on the ratio \(p_ 2/p_ 1\), otherwise \(\Phi_ n\) depends only on \(p_ 1\) and its multiplicity. This result is a consequence of a more general weak convergence result for the associated point processes to certain homogeneous Poisson processes. The proofs do not use techniques for random walks on graphs, but rely on `classical' estimates for the (tail) probabilities of overlapping long runs and their approximate independence.