Lesson 2

Let's start with a simple example. The process of selecting a random binary string (uniformly) can be imagined as follows: we start with an empty string and flip a coin \(n\) times. Thus, we simply traverse the binary tree shown below.

In general, we assume that the sum of the probabilities on the outgoing (downward) edges from a node equals one. (In all subsequent pictures, we will not label edges if the probabilities are equal for each node.) The possible outcomes are written in the leaves, and the probability of each outcome is the product of the labels on the edges.