Loading...
Please wait, while we are loading the content...
Similar Documents
A stochastically quasi-optimal search algorithm for the maximum of the simple random walk.
| Content Provider | CiteSeerX |
|---|---|
| Author | Chassaing, P. Marckert, J. F. Yor, M. |
| Abstract | an asymptotically optimal algorithm, with respect to the average cost, among algorithms that find the maximum of a random walk by using only probes and comparisons. We extend Odlyzko’s techniques to prove that his algorithm is indeed asymptotically optimal in distribution (with respect to the stochastic order). We also characterize the limit law of its cost. Computing its moments in two ways allows us to recover a surprising identity concerning Euler sums. 1. Introduction. 1.1. The model. In a remarkable paper, Odlyzko [31] introduces a new model for the study of various searching strategies in an unknown environment. The model is as follows: consider a simple symmetric random walk ω = (Sk(ω))k=0,...,n [i.e., S0(ω) = 0, Sk+1(ω) = Sk(ω) ± 1 for 0 ≤ k ≤ n − 1 and the |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Stochastically Quasi-optimal Search Algorithm Simple Random Walk Simple Symmetric Random Walk Limit Law Optimal Algorithm Unknown Environment Surprising Identity Random Walk New Model Odlyzko Technique Average Cost Remarkable Paper Euler Sum Stochastic Order |
| Content Type | Text |
