= Random path in a binary tree
In a <full binary tree>[rooted full binary tree], suppose each internal vertex selects either child with <Conditional probability> $1/2$. A specified leaf at depth $d$ is reached with <probability> $2^{-d}$: reaching it requires its particular sequence of $d$ choices, and the <chain rule for probabilities>[chain rule] multiplies their <conditional probability>[conditional probabilities].
The resulting leaves need not be uniformly distributed. A <tree> whose root has a leaf on one side and a two-leaf subtree on the other gives leaf <probability>[probabilities] $1/2,1/4,1/4$. For a <full binary tree>[finite full binary tree] these <probability>[probabilities] sum to one, giving $\sum_{\ell}2^{-d(\ell)}=1$. For an infinite <tree> the sum over finite leaves can be smaller than one, because a path can continue forever. If a vertex has only one available child, the fair-two-child formula needs an explicit convention; a forced transition contributes <probability> one instead of one half.
Back to article page