  Whereas deterministic protocols are typically guaranteed to obtain particular
goals of interest, probabilistic protocols typically provide only probabilistic
guarantees. This paper initiates an investigation of the interdependence
between actions and subjective beliefs of agents in a probabilistic setting. In
particular, we study what probabilistic beliefs an agent should have when
performing actions, in a protocol that satisfies a probabilistic constraint of
the form: 'Condition C should hold with probability at least p when action a is
performed'. Our main result is that the expected degree of an agent's belief in
C when it performs a equals the probability that C holds when a is performed.
Indeed, if the threshold of the probabilistic constraint should hold with
probaility p=1-x^2 for some small value of x then, with probability 1-x, when
the agent acts it will assign a probabilistic belief no smaller than 1-x to the
possibility that C holds. In other words, viewing strong belief as,
intuitively, approximate knowledge, the agent must probably approximately know
(PAK-know) that C is true when it acts.
