Moment conditions for a sequence with negative drift to be uniformly bounded in Lr

被引:46
作者
Pemantle, R
Rosenthal, JS
机构
[1] Univ Wisconsin, Dept Math, Madison, WI 53706 USA
[2] Univ Toronto, Dept Stat, Toronto, ON M5S 3G3, Canada
关键词
L-p; pth moments; supermartingale; martingale; linear boundary; Lyapunov function; stochastic adversary; queueing networks;
D O I
10.1016/S0304-4149(99)00012-5
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
Suppose a sequence of random variables {X-n} has negative drift when above a certain threshold and has increments bounded in L-P. When p > 2 this implies that EXn is bounded above by a constant independent of n and the particular sequence {X-n}. When p less than or equal to 2 there are counterexamples showing this does not hold. In general, increments bounded in L-P lead to a uniform L-r bound on X-n(+) for any r < p- 1, but not for r greater than or equal to p -1. These results are motivated by questions about stability of queueing networks. (C) 1999 Elsevier Science B.V. All rights reserved.
引用
收藏
页码:143 / 155
页数:13
相关论文
共 13 条
[1]   Universal stability results for greedy contention-resolution protocols [J].
Andrews, M ;
Awerbuch, B ;
Fernandez, A ;
Kleinberg, J ;
Leighton, T ;
Liu, ZY .
37TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1996, :380-389
[2]  
[Anonymous], 1992, Stochastic Stability of Markov chains
[3]  
Borodin A., 1996, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, P376, DOI 10.1145/237814.237984
[4]  
BORODIN A, 1998, UNPUB ADVERSARIAL QU
[5]  
BURKHOLDER D, 1966, ANN MATH STAT, V37, P1497
[6]  
BURKHOLDER DL, 1988, ASTERISQUE, P75
[7]  
CHOW YS, 1988, PROBABILITY THEORY I
[8]  
Durrett R, 1996, PROBABILITY THEORY E
[10]   Analysis of backoff protocols for multiple access channels [J].
Hastad, J ;
Leighton, T ;
Rogoff, B .
SIAM JOURNAL ON COMPUTING, 1996, 25 (04) :740-774