Bounds on absorption times of directionally biased random sequences

✍ Scribed by Bill Baritompa; Mike Steel

• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 810 KB
• Volume: 9
• Category: Article
• ISSN: 1042-9832
• DOI: 10.1002/(sici)1098-2418(199610)9:3<279::aid-rsa2>3.0.co;2-u

✦ Synopsis

A sequence of random variables X,, X , , . . . 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, E, := infk,o { j -E[Xk I X k -, = 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') steps. Simple upper bounds are described. In particular, t 5 E [bXO], where b, = C I S , 1/E, and E, = min,,, { E , } . If all E, 5 E,,, (so E, = E,) and < 1, this bound for t is the best possible.

For certain finite stochastic processes which we term conditionally independent of X , = i, b(i) bounds the expected time given X,, = 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.