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
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
0.783957302570343
0 references
0.7742883563041687
0 references
0.7645726203918457
0 references
0.7557709813117981
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