Random path in a binary tree
ID: random-path-in-a-binary-tree
In a rooted full binary tree, suppose each internal vertex selects either child with Conditional probability . A specified leaf at depth is reached with probability : reaching it requires its particular sequence of choices, and the chain rule multiplies their 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 probabilities . For a finite full binary tree these probabilities sum to one, giving . 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.
New to topics? Read the docs here!