Locating the maximum of a simple random sequence by sequential search (Q3769815)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4028680
Language Label Description Also known as
default for all languages
No label defined
    English
    Locating the maximum of a simple random sequence by sequential search
    scientific article; zbMATH DE number 4028680

      Statements

      Locating the maximum of a simple random sequence by sequential search (English)
      0 references
      0 references
      1987
      0 references
      sequential search
      0 references
      maximum of AR(1) processes
      0 references
      stationary Gaussian process
      0 references
      two-phase strategy
      0 references
      success probabilities
      0 references
      Let \(\{X_ i\}\) be a stationary Gaussian process with \(EX_ i=0\), \(cov(X_ i,X_ j)=a^{| i-j|}\), where \(a\in [0,1)\). Define \(X^*=\max (X_ 1,...,X_ N)\) and let \(X_{i^*}=X^*\). The problem is to find sequentially indices \(U_ 1,...,U_ M\) such that \(U^ 0=\{U_ 1,...,U_ M\}\subset \{1,...,N\}\) and that the event \(S=\{i^*\in U^ 0\}\) has its probability as large as possible. It is clear that for \(a=0\), \(P(S)=M/N\) holds for every set \(U^ 0\). For \(a\in (0,1)\) the author proves the following assertion: Let \(r\in (0,1)\) and let \(\epsilon_ N=(-\log a)/(\log \log N)\). Let \(U_{N,r}\) denote the set of strategies for finding \(i^*\) using \(m=\lfloor Nr \epsilon_ N\rfloor\) observations. Then \(\lim_{N\to \infty}\max_{U\in U_{N,r}}P(S)=r.\) It is shown in the proof that there exists a simple two-phase strategy which yields success probabilities as close to r as one likes, for N sufficiently large.
      0 references

      Identifiers