Pólya trees construct random probability measures through recursive random splits. They make the relation between partitions, histograms, and nonparametric priors explicit.
Recursive beta splits
A Pólya tree assigns random masses down a binary partition tree.
Definition. Let \(\mathcal X\) be recursively partitioned into sets \(A_\epsilon\), \(\epsilon\in\{0,1\}^m\). At each node, draw \[ V_\epsilon\sim\operatorname{Beta}(a_{\epsilon0},a_{\epsilon1}) \] and assign conditional masses \(P(A_{\epsilon0}\mid A_\epsilon)=V_\epsilon\), \(P(A_{\epsilon1}\mid A_\epsilon)=1-V_\epsilon\).
Proposition. The mass of a cell is the product of the split probabilities along its path.
Proof. Use the chain rule \(P(A_{\epsilon_1\cdots\epsilon_m})=\prod_{r=1}^m P(A_{\epsilon_1\cdots\epsilon_r}\mid A_{\epsilon_1\cdots\epsilon_{r-1}})\).
Posterior conjugacy
Observed counts update beta splits node by node.
Proposition. If \(n_{\epsilon0}\) and \(n_{\epsilon1}\) are the numbers of observations going left and right from node \(\epsilon\), then \[ V_\epsilon\mid X_{1:n}\sim\operatorname{Beta}(a_{\epsilon0}+n_{\epsilon0},a_{\epsilon1}+n_{\epsilon1}). \]
Proof. Conditional on reaching a node, the split likelihood is binomial in \(V_\epsilon\). Beta-binomial conjugacy gives the update, independently across nodes conditional on the tree counts.
Absolute continuity
The smoothness of a Pólya tree draw depends on how quickly split variances decrease down the tree.
Remark. If split parameters grow sufficiently fast with depth, random measures are often absolutely continuous with respect to the centering measure. If not, draws can be singular or too rough.
Histograms and tail-free priors
Finite truncations of Pólya trees are random histograms on a partition.
Example. Stopping the tree at depth \(M\) gives a random probability vector over \(2^M\) cells. Conditional on that vector, the density is piecewise constant relative to the base partition measure.
Binary recursive construction
Definition. Let \(\{B_\epsilon:\epsilon\in\{0,1\}^{m},m\ge0\}\) be a recursive binary partition, where \[ B_\epsilon=B_{\epsilon0}\cup B_{\epsilon1}. \] Assign independent \[ V_\epsilon\sim \operatorname{Beta} (\alpha_{\epsilon0},\alpha_{\epsilon1}), \] and define \[ P(B_{\epsilon0}\mid B_\epsilon)=V_\epsilon, \qquad P(B_{\epsilon1}\mid B_\epsilon)=1-V_\epsilon. \] For a depth-\(m\) cell \(B_{\epsilon_1\cdots\epsilon_m}\), its probability is the product of branch probabilities along its path.
Proposition. The construction defines a unique random probability measure on the \(\sigma\)-field generated by the partition, provided the nested cells separate points and the finite-level probabilities are consistent.
Proof. At each finite depth, products of branch probabilities form a probability vector because child masses sum to the parent mass. These finite distributions are projectively consistent across depth. The extension theorem gives a measure on the generated \(\sigma\)-field, and separating partitions give uniqueness.
Centering on a base distribution
Proposition. If the partition is chosen so that \[ G_0(B_{\epsilon0}\mid B_\epsilon) =\frac{\alpha_{\epsilon0}} {\alpha_{\epsilon0}+\alpha_{\epsilon1}}, \] then \[ E\{P(B_\epsilon)\}=G_0(B_\epsilon) \] for every tree cell.
Proof. Independent branch probabilities make the expectation of a path product equal the product of branch expectations. Each branch expectation matches the corresponding \(G_0\) conditional probability, whose product is \(G_0(B_\epsilon)\).
Conjugate branch updates
Theorem. If \(X_1,\ldots,X_n\mid P\stackrel{\mathrm{iid}}{\sim}P\), then independently over tree nodes, \[ V_\epsilon\mid X_{1:n} \sim\operatorname{Beta} \left( \alpha_{\epsilon0}+N_{\epsilon0}, \alpha_{\epsilon1}+N_{\epsilon1} \right), \] where \(N_{\epsilon j}\) is the number of observations entering child \(B_{\epsilon j}\).
Proof. Conditional on reaching node \(\epsilon\), observations choose its two children according to a binomial likelihood \[ V_\epsilon^{N_{\epsilon0}} (1-V_\epsilon)^{N_{\epsilon1}}. \] Beta-binomial conjugacy gives the update. The likelihood factors over branch decisions, preserving posterior independence.
Absolute continuity
Theorem (sufficient condition). For a balanced tree with \[ V_\epsilon\sim\operatorname{Beta}(a_m,a_m) \quad\text{at depth }m, \] if \[ \sum_{m=1}^\infty a_m^{-1}<\infty, \] then a Pólya-tree draw is absolutely continuous with respect to the centering measure under standard regular partitions.
Proof outline. The log density martingale along a nested path is a sum of centered log branch ratios. Its variance at level \(m\) is of order \(a_m^{-1}\). Summability makes the martingale \(L^2\)-bounded and hence convergent. Uniform integrability preserves total integral one, producing a Radon-Nikodym density. If branch variances fail to decay, multiplicative fluctuations can persist across infinitely many scales and yield singular draws.
A common choice \(a_m\asymp m^2\) satisfies the condition. Constant \(a_m\) generally produces rough, singular random measures despite a smooth centering distribution.
Finite Pólya trees and random histograms
Example. Stop at depth \(M\), with terminal cells \(B_1,\ldots,B_{2^M}\) of lengths \(|B_j|\). The induced density is \[ f_M(x) =\sum_{j=1}^{2^M} \frac{P(B_j)}{|B_j|}1_{B_j}(x). \] The posterior mean cell probability is obtained by multiplying posterior mean branch probabilities along the path. Increasing \(M\) decreases approximation bias but creates many sparsely informed branches.
Optional Pólya trees
An optional Pólya tree assigns a stopping probability at each node. A stopped node uses a simple base density inside that cell; an unstopped node splits recursively. This randomizes local resolution, allowing smooth regions to stop early and complex regions to refine. Posterior computation combines stop/split probabilities with beta-binomial branch factors.
Partition dependence
Remark. A fixed dyadic partition privileges its boundaries: a feature lying across a boundary can be represented less efficiently than one aligned with it. Centering partitions on quantiles of \(G_0\), mixing over shifts, or using optional/random partitions reduces this artifact. Tail-free priors generalize the recursive conditional-probability idea beyond one fixed binary tree.
Density support
Proposition. If every branch beta density is positive on \((0,1)\) and the partition generates the Borel \(\sigma\)-field, then every finite collection of target cell probabilities with positive entries receives positive prior neighborhood mass.
Proof. Target cell probabilities determine finitely many target branch ratios in \((0,1)\). Independent beta variables assign positive probability to arbitrary neighborhoods of these ratios. Continuity of finite products transfers this to terminal cell masses.
As with all support arguments, positive mass at each fixed resolution is only the first step. Contraction rates require controlling how branch precisions and stopping depth allocate mass near increasingly fine approximations of the truth.