Biased random walks

ABSTRACT

How much can an imperfect source of randomness affect an algorithm? We examine several simple questions of this type concerning the long-term behavior of a random walk on a finite graph. In our setup, each step of the random walk a “controller” can, with a certain small probability, fix the next step, thus introducing a bias. We analyze the extent to which the bias can affect the limit behavior of the walk. The controller is assumed to associate a real, nonnegative, “benefit” with each state, and to strive to maximize the long-term expected benefit. We derive tight bounds on the maximum of this objective function over all controller's strategies, and present polynomial time algorithms for computing the optimal controller strategy.

REFERENCES

• 1: M. Ajtai , J. Komlos , E. Szemeredi, Deterministic simulation in LOGSPACE, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.132-140, January 1987, New York, New York, United States [doi>10.1145/28395.28410]
• 2: M. Ajtai and N. Linial, "The influence of large coalitions," Combinatorica, accepted for publication.
• 3: N. Alon and M. Naor, "Coin-flipping Games Immune Against Linear-sized Coalitions," 31st Annual IEEE FOCS 1990, pp. 46-54.
• 4: N. Alon and M. O. Rabin, "Biased Coins and Kandomized Algorithms," in Randomness and Computation (S. Micali ed.) Advances in Computing Research, Vol. 5, pp. 499-507.
• 5: M. Ben-Or and N. Linial, "Collective coin flipping," in Randomness and Computation (S. Micah ed.) Academic Press, New York, 1990, pp. 91-115.
• 6: M. Ben-Or, N. Linial and M. Saks, "Collective coin flipping and other models of imperfect randomness," in Colloq. Math $oc. Janos Bolyai no. 52, Combinatorics Eger 1987, pp. 75-112.
• 7: A. Cohen and A. Wigderson, "Dispersers, Deterministic Amplification, and Weak Random Sources," 30th Annual IEEE FOCS 1989, pp. 14-19.
• 8: Oded Goldreich , Shafi Goldwasser , Nathan Linial, Fault-tolerant computation in the full information model (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.447-457, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185405]
• 9: 1%. impagliazzo and D. Zuckerman, "How to Recycle Random Bits," 30th Annum IEEE FOCS, 1989, pp. 248-253.
• 10: D. Lichtenstein, N.Linial and M. Saks, "Some extremal problems arising from discrete control processes," Combinatorica, 9 (1989), pp. 269-287.
• 11: M. Metropolis, A. Kosenbluth, M. Kosenbluth, A. Teller, and M. Teller, "Equation of state calculations by fast computing machines," Journal of Chemica/ Physics 21 (1953), pp. 1087-1092.
• 12: M. Santha and U. Vazirani, "Generating Quasi-Random Sequences from Semi-random #ourees," 25f:}a Annual IEEE FOCS, 1984, pp. 434-440.
• 13: U. Vazirani, Efficiency considerations in using semi-random sources, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.160-168, January 1987, New York, New York, United States [doi>10.1145/28395.28413]
• 14: Umesh Virkumar Vazirani, Randomness, adversaries and computation (random polynomial time), 1986

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Performance, Theory