Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-25T12:24:14.811Z Has data issue: false hasContentIssue false
  • English
  • Français

Extremal large deviations in controlled i.i.d. processes with applications to hypothesis testing

Part of: Limit theorems

Published online by Cambridge University Press:  01 July 2016

Nahum Shimkin
Nahum Shimkin*
Affiliation:
University of Minnesota
*
* Postal address: Institute for Mathematics and its Applications, University of Minnesota, Minneapolis, MN 55455, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a controlled i.i.d. process, where several i.i.d. sources are sampled sequentially. At each time instant, a controller determines from which source to obtain the next sample. Any causal sampling policy, possibly history-dependent, may be employed. The purpose is to characterize the extremal large deviations of the sample mean, namely to obtain asymptotic rate bounds (similar to and extending Cramér's theorem) which hold uniformly over all sampling policies. Lower and upper bounds are obtained, and it is shown that in many (but not all) cases stationary sampling policies are sufficient to obtain the extremal large deviations rates. These results are applied to a hypothesis testing problem, where data samples may be sequentially chosen from several i.i.d. sources (representing different types of experiments). The analysis provides asymptotic estimates for the error probabilities, corresponding both to optimal and to worst-case sampling policies.

Keywords

LARGE DEVIATIONS OF THE SAMPLE MEANEXTREMAL RATESSTATIONARY POLICIESSEQUENTIAL DESIGN

MSC classification

Primary: 60F10: Large deviations
Secondary: 90C40: Markov and semi-Markov decision processes
Type
Research Article
Information
Advances in Applied Probability , Volume 25 , Issue 4 , December 1993 , pp. 875 - 894
Copyright
Copyright © Applied Probability Trust 1993 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Bertsekas, D. P. (1976) Dynamic Programming and Stochastic Control. Academic Press, New York.Google Scholar
[2] Bucklew, J. A. (1990) Large Deviations Techniques in Decision, Simulation and Estimation. Wiley, New York.Google Scholar
[3] Chernoff, H. (1952) A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statist. 23, 493–507.Google Scholar
[4] Chernoff, H. (1972) Sequential Analysis and Optimal Design. Regional Conference Series in Applied Mathematics 8, SIAM, Philadelphia.Google Scholar
[5] De Acosta, A. (1985) Upper bounds for large deviations of dependent random vectors. Z. Wahrscheinlichkeitsth. 69, 551–565.Google Scholar
[6] Dembo, A. and Zeitouni, O. (1992) Large Deviations and Applications. Jones and Bartlett, Boston, MA.Google Scholar
[7] Deuschel, J.-D. and Stroock, D. W. (1989) Large Deviations. Academic Press, San Diego.Google Scholar
[8] Ellis, R. S. (1984) Large deviations for a general class of random vectors. Ann. Prob. 12, 1–12.Google Scholar
[9] Rockafellar, R. T. (1970) Convex Analysis. Princeton University Press, Princeton, NJ.CrossRefGoogle Scholar
[10] Ross, S. M. (1983) Introduction to Stochastic Dynamic Programming. Academic Press, New York.Google Scholar
[11] Shwartz, A. and Weiss, A. (1993) Large deviations and their applications to computer and communications systems. To appear.Google Scholar