D. Lichtenstein
ABSTRACT
We consider a simple model for a class of discrete control processes, motivated in part by recent work about the behavior of imperfect random sources in computer algorithms. The process produces a string of characters from {0, 1} of length n and is a “success” or “failure” depending on whether the string produced belongs to a prespecified set L. In an uninfluenced process each character is chosen by a fair coin toss, and hence the probability of success is |L|/2n. We are interested in the effect on the probability of success in the presence of a player (controller) who can intervene in the process by specifying the value of certain characters in the string. We answer the following questions in both worst and average case: (1) how much can the player increase the probability of success given a fixed number of interventions? (2) in terms of |L| what is the expected number of interventions needed to guarantee success? In particular our results imply that if |L|/2n = 1/w(n) where w(n) tends to infinity with n (so the probability of success with no interventions is o(1)) then with Ο(√nlogw(n)) interventions the probability of success is 1-o(1).
Our main results and the proof techniques are related to a well-known theorem of Kruskal, Katona, and Harper in extremal set theory.
- AR.N. Aton and M. O. Rabin, manuscript MiT 1985.Google Scholar
- BL.M. Ben-Or and N. Linial, Collective Coin Flipping, robust voting schemes and minimal of Banzhaf values, Proceedings of the 2$th Annual IEEE Symposium on Foundations of Computer Science, 1985, 408-416.Google Scholar
- CG.B. Chor and O. Goldreich, Unbiased bits from sources of weak randomness and probabilistie communication complexity, Proceedings of the 26th Annual {EEE Symposium on Foundations of Computer Science, 1985, 429-442.Google ScholarDigital Library
- D.D. E. Daykin, Ordered ranked posets, repre,~entations of integers and inequalities from extremal ranked posets, in Graphs and Order (I. Rival, ed.), D. Reidel Publishing, 1985, 395-412.Google Scholar
- GK.C. Greene and D. J. Kleitman, Proof techniques in the theory of finite sets, in Studies in Combinatorics (G.-C. Rota, ed.), .MAA Studies i:n Mathematics, Vol. 17, 1978, 22-79.Google Scholar
- H.L. Harper, Optimal numberings and isoperimetric problems on graphs, J. Comb. Th. 1 (1966), 385-393.Google ScholarCross Ref
- Ka.G. Katona, A theorem for finite sets, in Theory of Graphs (P. Erdos and G. Katona, eds.), Hungarian Academy of Science, Budapest, 1966, 187-207.Google Scholar
- Kr.J. B. Kruskal, The number of simplices in a complex, in Mathematical Optimization Techniques (R. Bellman, ed.), University of California Press, Berkeley, 1963, 251-278.Google Scholar
- S.M. Saks, A robust noncryptographic protocol for collective coin flipping, preprint.Google Scholar
- SV.M. Santha and U. V. Vazirani, Generating quasi random sequences from slightly random sources, Proceedings of the 25th Annual IEEE Symposium on the Foundations of Computer Science, 1984, 434-440.Google ScholarDigital Library
- V.U.V. Vazirani, Towards a strong communication complexity theory or generating quasirandom sequences from two communicating; slightly-random sources, Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985, 366-378. Google ScholarDigital Library
Index Terms
- Imperfect random sources and discrete controlled processes
Recommendations
Recognizing Sources of Random Strings
The identification of a source given a sequence of random strings is discussed. Two modes of random string generation are analyzed. In the first mode, arbitrary strings are generated in which the individual symbols occur exactly once in each random ...
General weak random sources
SFCS '90: Proceedings of the 31st Annual Symposium on Foundations of Computer ScienceThe following model for a weak random source is considered. The source is asked only once for R bits, and the source outputs an R-bit string such that no string has probability more than 2/sup - delta R/ of being output. for some fixed delta >0. A ...
Comments