TY - JOUR
T1 - On fairness and randomness
AU - Jaeger, Manfred
PY - 2009
Y1 - 2009
N2 - We investigate the relation between the behavior of non-deterministic systems under fairness constraints, and the behavior of probabilistic systems. To this end, first a framework based on computable stopping strategies is developed that provides a common foundation for describing both fair and probabilistic behavior. On the basis of stopping strategies it is then shown that fair behavior corresponds in a precise sense to random behavior in the sense of Martin-Löf's definition of randomness.We view probabilistic systems as concrete implementations of more abstract non-deterministic systems. Under this perspective the question is investigated what probabilistic properties are needed in such an implementation to guarantee (with probability one) certain required fairness properties in the behavior of the probabilistic system. Generalizing earlier concepts of ε-bounded transition probabilities, we introduce the notion of divergent probabilistic systems, which enables an exact characterization of the fairness properties of a probabilistic implementation. Looking beyond pure fairness properties, we also investigate what other qualitative system properties are guaranteed by probabilistic implementations of fair non-deterministic behavior. This leads to a completeness result which generalizes a well-known theorem by Pnueli and Zuck.
AB - We investigate the relation between the behavior of non-deterministic systems under fairness constraints, and the behavior of probabilistic systems. To this end, first a framework based on computable stopping strategies is developed that provides a common foundation for describing both fair and probabilistic behavior. On the basis of stopping strategies it is then shown that fair behavior corresponds in a precise sense to random behavior in the sense of Martin-Löf's definition of randomness.We view probabilistic systems as concrete implementations of more abstract non-deterministic systems. Under this perspective the question is investigated what probabilistic properties are needed in such an implementation to guarantee (with probability one) certain required fairness properties in the behavior of the probabilistic system. Generalizing earlier concepts of ε-bounded transition probabilities, we introduce the notion of divergent probabilistic systems, which enables an exact characterization of the fairness properties of a probabilistic implementation. Looking beyond pure fairness properties, we also investigate what other qualitative system properties are guaranteed by probabilistic implementations of fair non-deterministic behavior. This leads to a completeness result which generalizes a well-known theorem by Pnueli and Zuck.
U2 - 10.1016/j.ic.2009.01.005
DO - 10.1016/j.ic.2009.01.005
M3 - Journal article
SN - 0890-5401
VL - 207
SP - 909
EP - 922
JO - Information and Computation
JF - Information and Computation
IS - 9
ER -