Covering with blocks in the non-symmetric case (Q1345083): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q206674 |
||
Property / reviewed by | |||
Property / reviewed by: Rene L. Schilling / rank | |||
Revision as of 22:17, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Covering with blocks in the non-symmetric case |
scientific article |
Statements
Covering with blocks in the non-symmetric case (English)
0 references
26 February 1995
0 references
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.
0 references
random walks on graphs
0 references
cover time
0 references
Poisson process
0 references
Gumbel distribution
0 references
approximate independence
0 references