Premium
Bounds on absorption times of directionally biased random sequences
Author(s) -
Baritompa Bill,
Steel Mike
Publication year - 1996
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199610)9:3<279::aid-rsa2>3.0.co;2-u
Subject(s) - combinatorics , mathematics , upper and lower bounds , sequence (biology) , random variable , convergence (economics) , expected value , state (computer science) , stochastic process , finite set , discrete mathematics , algorithm , statistics , mathematical analysis , chemistry , economics , economic growth , biochemistry
A sequence of random variables X 0 , X 1 , … with values in {0, 1, …, n } representing a general finite‐state stochastic process with absorbing state 0 is said to be directionally biased towards 0, if, for all j > 0, ϵ j : = inf k >0 { j − E[ X k | X k −1 = j ]} > 0. For such sequences, let t be the expected value of the time to absorption at 0. For a fixed set of biases, the least upper bound for this time can be computed with an algorithm requiring O ( n 2 ) steps. Simple upper bounds are described. In particular, t ≤ E[ b x 0 ], where b i = Σ j≤i 1/¯ϵ j and ¯ϵ j = min l≥j {ϵ l }. If all ϵ j ≤ ϵ j + 1 (so ¯ϵ j = ϵ j ) and ϵ n < 1, this bound for t is the best possible. For certain finite stochastic processes which we term conditionally independent of X 0 = i , b ( i ) bounds the expected time given X 0 = i . Similar results are given for lower bounds. The results of this paper were designed to be a useful tool for determining rates of convergence of stochastic optimization algorithms. © 1996 John Wiley & Sons, Inc.