Hostname: page-component-78c5997874-mlc7c Total loading time: 0 Render date: 2024-11-04T21:40:09.308Z Has data issue: false hasContentIssue false
  • English
  • Français

Monte Carlo Algorithms for Finding the Maximum of a Random Walk with Negative Drift

Part of: Stochastic processes Theory of computing

Published online by Cambridge University Press:  14 July 2016

Ludwig Baringhaus  and
Rudolf Grübel
Ludwig Baringhaus*
Affiliation:
Universität Hannover
Rudolf Grübel*
Affiliation:
Universität Hannover
*
∗ Postal address: Institut für Mathematische Stochastik, Universität Hannover, Postfach 60 09, D-30060 Hannover, Germany.
∗ Postal address: Institut für Mathematische Stochastik, Universität Hannover, Postfach 60 09, D-30060 Hannover, Germany.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We discuss two Monte Carlo algorithms for finding the global maximum of a simple random walk with negative drift. This problem can be used to connect the analysis of random input Monte Carlo algorithms with ideas and principles from mathematical statistics.

Keywords

Brownian motion with driftconditioningefficiencyfast Fourier transformladder variableMarkov chainrandomization

MSC classification

Primary: 60G50: Sums of independent random variables; random walks 68Q25: Analysis of algorithms and problem complexity
Type
Research Papers
Information
Journal of Applied Probability , Volume 43 , Issue 1 , March 2006 , pp. 74 - 86
Copyright
© Applied Probability Trust 2006 

References

Borodin, A. N. Salminen, P. (2002). Handbook of Brownian Motion—Facts and Formulae , 2nd edn. Birkhäuser, Basel.Google Scholar
Brémaud, P. (1999). Markov Chains. Gibbs Fields, Monte Carlo Simulation and Queues. Springer, New York. Chan, W.-S. Yang, H. Zhang, L. (2003). Some results on ruin probabilities in a two-dimensional risk model. Insurance Math. Econom. 32, 345–358.Google Scholar
Chassaing, P. (1999). How many probes are needed to compute the maximum of a random walk? Stoch. Process. Appl. 81, 129–153.Google Scholar
Chassaing, P. Marckert, J. F. Yor, M. (2003). A stochastically quasi-optimal search algorithm for the maximum of the simple random walk. Ann. Appl. Prob. 13, 1264–1295.Google Scholar
Cox, D. R. Hinkley, D. V. (1974). Theoretical Statistics. Chapman and Hall, London.Google Scholar
Feller, W. (1968). An Introduction to Probability Theory and Its Applications, Vol. I, 3rd edn. John Wiley, New York. Feller, W. (1971). An Introduction to Probability Theory and Its Applications, Vol. II, 2nd edn. John Wiley, New York.Google Scholar
Gradstein, I. S. Ryshik, I. M. (1981). Tables of Series, Products and Integrals, Vol. 2. Deutsch, Frankfurt.Google Scholar
Grübel, R. (1989). The fast Fourier transform algorithm in applied probability theory. Nieuw Arch. Wisk. 7, 289–300.Google Scholar
Grübel, R. Hermesmeier, R. (1999). Computation of compound distributions. I. Aliasing errors and exponential tilting. Astin Bull. 29, 197–214.Google Scholar
Kallenberg, W. C. M. Koning, A. J. (1995). On Wieand's theorem. Statist. Prob. Lett. 25, 121–132.Google Scholar
Knuth, D. E. (2000). Selected Papers on Analysis of Algorithms. CSLI Publications, Stanford, CA.Google Scholar
Korf, I. Yandell, M. Bedell, J. (2003). BLAST. An Essential Guide to the Basic Local Alignment Search Tool. O'Reilly, Sebastopol.Google Scholar
Motwani, R. Raghavan, P. (1995). Randomized Algorithms. Cambridge University Press.Google Scholar
Odlyzko, A. M. (1995). Search for the maximum of a random walk. Random Structures Algorithms 6, 275–295.Google Scholar
Stuart, A. Ord, K. (1987). Kendall's Advanced Theory of Statistics, Vol. 1, Distribution Theory, 5th edn. Griffin, London.Google Scholar
Van der Vaart, A. W. (1998). Asymptotic Statistics. Cambridge University Press.Google Scholar
Williams, D. (1991). Probability with Martingales. Cambridge University Press.CrossRefGoogle Scholar