Fairness, Computable Fairness and Randomness
Manfred Jaeger
Motivated by the observation that executions of a probabilistic system
almost surely are fair,
we interpret concepts of fairness for nondeterministic processes as
partial descriptions of probabilistic
behavior. We propose computable fairness as a very strong concept of
fairness, attempting to capture
all the qualitative properties of probabilistic behavior that we might
reasonably expect to see in the behavior
of a nondeterministic system. It is shown that computable fairness
does describe probabilistic
behavior by proving that runs of a probabilistic system almost surely
are computable fair. We then turn to
the question of how sharp an approximation of randomness is obtainedby
computable fairness by discussing
completeness of computable fairness for certain classes of path properties.
Get the Full paper