Large deviations and rare events in the study of stochastic algorithms
- 1 September 1983
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 28 (9), 907-920
- https://doi.org/10.1109/tac.1983.1103345
Abstract
New asymptotics formulas for the mean exit time from an almost stable domain of a discrete-time Markov process are obtained. An original fast simulation method is also proposed. The mathematical background involves the large deviation theorems and approximations by a diffusion process. We are chiefly concerned with the classical Robbins-Monroe algorithm. The validity of the results are tested on examples from the ALOHA system (a satellite type communication algorithm).Keywords
This publication has 8 references indexed in Scilit:
- Analysis of stochastic approximation schemes with discontinuous and dependent forcing terms with applications to data communication algorithmsIEEE Transactions on Automatic Control, 1980
- Stability and Optimal Control of the Packet Switching Broadcast ChannelJournal of the ACM, 1977
- Rough Limit Theorems on Large Deviations for Markov Stochastic Processes, IITheory of Probability and Its Applications, 1977
- The Throughput of Packet Broadcasting ChannelsIEEE Transactions on Communications, 1977
- Mélanges d'équations différentielles et grands écarts à la loi des grands nombresProbability Theory and Related Fields, 1977
- Persistence of Dynamical Systems under Random PerturbationsSIAM Review, 1975
- Packet Switching in a Multiaccess Broadcast Channel: Dynamic Control ProceduresIEEE Transactions on Communications, 1975
- Stochastic Differential EquationsPublished by Springer Nature ,1972