Stochastics

For many things in the world, the behavior is not the same every time. An example is a coin toss, where the result can be either heads or tails. Tossing a coin exhibits randomness. It is possible to model the different variants in a CIF model without specifying the likelihood of each of the outcomes. This approach was used in the lesson on non-determinism.

It is however also possible to explicitly specify the likelihood of each of the outcomes in the CIF model, using a stochastic distribution (also called probability distribution). A stochastic distribution describes how likely the different outcomes are. There are many different stochastic distributions. The Bernoulli distribution for instance, can be used to model things with two potential outcomes, such as a coin toss.

Consider the following CIF specification:

automaton coin_toss:
  disc dist bool d = bernoulli(0.5);
  disc bool outcome;

  location toss:
    initial;
    edge do (outcome, d) := sample d goto result;

  location result:
    edge when     outcome goto heads;
    edge when not outcome goto tails;

  location heads:
    edge tau goto toss;

  location tails:
    edge tau goto toss;
end

Variable d holds a stochastic distribution that produces boolean values (true or false), as indicated by its dist bool type. In this case it holds a Bernoulli distribution, with a probability of 0.5 (or chance of 50%) for true, and thus also the same probability/chance for false (the only other possible outcome).

The bernoulli function is used to create a Bernoulli distribution with the proper parameter (probability of 0.5 for true). Different distributions have different parameters. See the language reference documentation for further details. Distribution functions, such as the bernoulli function can be used to create distributions with specific parameters, and may only be used to initialize discrete variables.

Initially, the automaton is in its toss location, where the coin can be tossed. The edge uses the sample operator to get a sample from the bernoulli distribution. Each time the distribution is sampled, the outcome is either a true value or a false value. As we used a probability of 0.5 for both outcomes, half of the times true will be the outcome, and the other half of the times false will be the outcome, if we were to sample infinitely many times.

Sampling does not only result in the outcome, but also the distribution itself. This is further explained in one of the next lessons, which explains pseudo-randomness.

The result of sampling is stored in the outcome variable. In the result location, the sampling result is used to make a decision to go to either the heads location (true outcome) or the tails location (false outcome). From there, it is possible to go back to the toss location, to proceed with the next coin toss.