Y. Azar, A. Z. Broder, A. R. Karlin, N. Linial, and S. Phillips, Biased random walks, Proc. 24th Ann. ACM Symp. on Theory of Computing, pp.1-9, 1992.

E. G. Cooman, C. Jr, M. R. Courcoubetis, D. S. Garey, L. A. Johnson et al., Fundamental discrepancies between average-case analyses under discrete and continuous distributions: A bin-packing case study. I n Proc. 23rd A nn, ACM Symp. on Theory of Computing, pp.230-240, 1991.

E. G. Cooman, D. S. Johnson, P. W. Shor, and R. R. Weber, Markov chains, computer proofs, and average-case analysis of Best Fit bin packing, Proc. 25th Ann. ACM Symp. on Theory of Computing, pp.412-421, 1993.

G. Fayolle, V. A. Malyshev, and M. V. Menshikov, Constructive Theory of Countable Markov Chains (Part I), 1992.

W. Feller, An I n t r oduction to Probability Theory and its Applications, vol.I, 1968.

F. G. Foster, On stochastic matrices associated with certain queueing processes, Ann. Math. Stat, vol.24, pp.355-360, 1953.

B. Hajek, Hitting-time and occupation-time bounds implied by drift analysis with applications, Adv. Appl. Prob, vol.14, pp.502-525, 1982.

D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey, and R. L. Graham, Worst case performance bounds for simple one-dimensional packing algorithms, SIAM J. Comput, vol.3, pp.299-325, 1974.

F. T. Leighton, Average case analysis of greedy routing algorithms on arrays, Proc. 2nd Ann. ACM Symp. on Parallel Algorithms and Architectures, pp.2-10, 1990.

V. A. Malyshev and M. V. Menshikov, Ergodicity, c o n tinuity, and analyticity of countable Markov c hains, Trans. Moscow Math. Soc, vol.39, pp.3-48, 1979.

P. W. Shor, The average case analysis of some on-line algorithms for binpacking, Combinatorica, vol.6, pp.179-200, 1986.