Dirichlet-process priors and finite-partition updates

Define $d(s,t)=0$ when $s=t$ and $d(s,t)=1$ when $s\mathrm{\ne }t$. These values are nonnegative, the definition is symmetric, and $d(s,t)=0$ exactly when $s=t$. If $s\mathrm{\ne }u$, then at least one of $s\mathrm{\ne }t$ or $t\mathrm{\ne }u$ holds, so $d(s,u)=1\le d(s,t)+d(t,u)$; if $s=u$, the triangle inequality follows from nonnegativity. Thus [F3] makes $d$ a metric. For every $s\in S$, [F4] gives $B(s,1\mathrm{/}2)=\{s\}$, so [F5] shows that every subset of $S$ is open.

If $(s_n)$ is Cauchy, [F6] with the rational $ϵ=1\mathrm{/}2$ gives an index $N$ such that $d(s_m,s_n)<1\mathrm{/}2$ for all $m,n\ge N$. Hence all $s_n$ for $n\ge N$ are equal, so the sequence converges in $S$; by [F7], $d$ is complete. Since $S$ is at-most-countable and dense in itself, [F8] makes $(S,d)$ separable.

The power set is closed under relative complements and countable unions, so it is a sigma-algebra by [F2]. By [F10] and step 1.1, every subset of $S$ belongs to the Borel sigma-algebra. Conversely, every Borel set is a subset of $S$, so this sigma-algebra is exactly $\mathcal{P}(S)$. Therefore $(S,d)$ is Polish by [F9], and the identity map from $(S,\mathcal{P}(S))$ to $(S,\mathcal{B}(S,d))$ is a measurable bijection with measurable inverse.

The identity map in step 3.1 is a measurable isomorphism to a Polish space, so [F11] gives that $(S,\mathcal{P}(S))$ is standard Borel.

Put $\rho (dt)=t^{-1}{e}^{-t}dt$ on $(0,\mathrm{\infty })$; [A2] and [F22] make this a measure on the Borel sigma-algebra with a nonnegative density relative to Lebesgue measure, and partition the mark axis into $I_0=[1,\mathrm{\infty })$ and $I_m=[1\mathrm{/}(m+1),1\mathrm{/}m)$ for $m\ge 1$. These disjoint strips cover $(0,\mathrm{\infty })$. For $m\ge 1$, $\rho (I_m)\le 1\mathrm{/}m$ because $t^{-1}\le m+1$ and $e^{-t}\le 1$ there, while $\rho (I_m)\ge 1\mathrm{/}(e(m+1))>0$ because $t^{-1}\ge m$, $e^{-t}\ge e^{-1}$, and the interval length is $1\mathrm{/}(m(m+1))$. Also $\rho (I_0)\le {\int }_1^{\mathrm{\infty }}{e}^{-t}dt<\mathrm{\infty }$ and $\rho (I_0)\ge e^{-2}\mathrm{/}2>0$ by restricting to $[1,2]$. Thus every strip has finite positive mass. By [F3] and [F14], $\mu =\alpha \otimes \rho$ is sigma-finite and ${\mu }_m:=\mu {\mathrm{\mid }}_{\mathsf{X}\times I_m}$ has finite positive total ${\lambda }_m=\alpha (\mathsf{X})\rho (I_m)$. Let $Q_m={\mu }_m\mathrm{/}{\lambda }_m$.

Index count coordinates by $m\ge 0$ and mark coordinates by $(m,\mathrm{\ell })$ with $m\ge 0,\mathrm{\ell }\ge 1$. Their spaces are ${\mathbb{N}}_0$ and $\mathsf{X}\times (0,\mathrm{\infty })$, respectively, hence standard Borel by [F1], [F21], and [F23]. Assign every finite set of coordinates the product of the laws $\mathrm{Pois}({\lambda }_m)$ and $Q_m$. These finite-dimensional laws are consistent because coordinate projections of a finite product recover the corresponding marginal products. By [F1] and [A1] they extend to one probability law. The product rectangle formula gives mutual independence of each finite coordinate family by [F20], and [F13] identifies its joint law with the product. Thus it supports mutually independent $N_m\sim \mathrm{Pois}({\lambda }_m)$ and $Z_{m\mathrm{\ell }}=(X_{m\mathrm{\ell }},T_{m\mathrm{\ell }})\sim Q_m$.

Define $N={\sum }_{m\ge 0}{\sum }_{\mathrm{\ell }\ge 1}{\mathbf{1}}_{\{\mathrm{\ell }\le N_m\}}{\delta }_{Z_{m\mathrm{\ell }}}$. Each $N_m$ is finite, so this is a countable sum of Dirac measures and is a counting measure by [F8]. For every measurable $B$, its evaluation is the increasing limit of finite sums of measurable functions of the coordinates; hence $N(B)$ is measurable. Thus $N$ is a random counting measure.

Fix pairwise-disjoint measurable sets $B_1,\dots ,B_r$ with $\mu (B_j)<\mathrm{\infty }$. Within strip $m$, put $q_{jm}=Q_m(B_j)$ and $q_{0m}=1-{\sum }_{j=1}^r{q}_{jm}$. Conditional on $N_m=n$, independent marks assign counts $(k_0,k_1,\dots ,k_r)$ with $n=k_0+\cdots +k_r$. There are $n!\mathrm{/}{\prod }_{j=0}^r{k}_j!$ assignments of the $n$ mark indices to these cells, and each assignment has probability ${\prod }_{j=0}^r{q}_{jm}^{k_j}$, so the count vector has mass $n!{\prod }_{j=0}^r{q}_{jm}^{k_j}\mathrm{/}{\prod }_{j=0}^r{k}_j!$ (with $0^0=1$). Summing over $k_0$ and using the Poisson mass in [F2] gives $\mathrm{Pr}\{N_m(B_j)=k_j,1\le j\le r\}=e^{-{\lambda }_m}({\prod }_{j=1}^r({\lambda }_m{q}_{jm}{)}^{k_j}\mathrm{/}{k}_j!)e^{{\lambda }_m{q}_{0m}}={\prod }_{j=1}^r{e}^{-{\mu }_m(B_j)}{\mu }_m(B_j{)}^{k_j}\mathrm{/}{k}_j!$; here ${\lambda }_m{q}_{jm}={\mu }_m(B_j)$ and ${\lambda }_m(1-q_{0m})={\sum }_j{\mu }_m(B_j)$. Thus the strip counts are independent Poisson variables with means ${\mu }_m(B_j)$. The series over $k_0$ is the exponential series [F17].

Define $\mathrm{\Gamma }(A)={\sum }_{m\ge 0}{\sum }_{\mathrm{\ell }\ge 1}{\mathbf{1}}_{\{\mathrm{\ell }\le N_m\}}{T}_{m\mathrm{\ell }}{\mathbf{1}}_{\{X_{m\mathrm{\ell }}\in A\}}$ for $A\in \mathcal{A}$. This is a measurable nonnegative weighted sum of Dirac measures, hence a measure by [F8]. For each strip, independence of $N_m$ and its marks [F13], expectation against their law [F11], and $\mathbb{E}{N}_m={\lambda }_m$ from [F2] give $\mathbb{E}{\sum }_{\mathrm{\ell }=1}^{N_m}{T}_{m\mathrm{\ell }}{\mathbf{1}}_{\{X_{m\mathrm{\ell }}\in A\}}={\lambda }_m\int t{\mathbf{1}}_A(x)Q_m(dx,dt)={\int }_{A\times I_m}t\mu (dx,dt)$. Monotone convergence [F16] then gives $\mathbb{E}\mathrm{\Gamma }(A)={\sum }_m{\int }_{A\times I_m}t\mu (dx,dt)=\alpha (A){\int }_0^{\mathrm{\infty }}{e}^{-t}dt=\alpha (A)$ by [F3] and [F6].

Let $A_1,\dots ,A_r$ be pairwise disjoint and choose $\mathrm{\mid }{u}_j\mathrm{\mid }<\delta <1$. On strip $m$, define $g_m(x,t)={\sum }_{j=1}^r{e}^{u_{j}t}{\mathbf{1}}_{A_j}(x)+{\mathbf{1}}_{\mathsf{X}\setminus {\cup }_j{A}_j}(x)$. Conditional on $N_m=n$, the independent marks give the exponential factor $(\int g_{m}d{Q}_m{)}^n$. Summing its Poisson series yields $\mathbb{E}\exp ({\sum }_j{u}_j{\mathrm{\Gamma }}_M(A_j))=\exp ({\sum }_j\alpha (A_j){\int }_{{\cup }_{m\le M}{I}_m}(e^{u_{j}t}-1)\rho (dt))$, where ${\mathrm{\Gamma }}_M$ sums the first $M+1$ strips. The mark integral is finite on each strip because the strips are bounded away from zero and $u_j<1$; the Poisson series is [F17].

For each finite $M$, the sums over $m\le M$ are independent Poisson counts: convolution and [F18] give ${\sum }_{h=0}^k{e}^{-a}{a}^h\mathrm{/}h!e^{-b}{b}^{k-h}\mathrm{/}(k-h)!=e^{-(a+b)}(a+b{)}^k\mathrm{/}k!$, and iteration handles $M$. By [F16], their increasing total counts have $\mathbb{E}N(B_j)={\lim }_{M\to \mathrm{\infty }}{\sum }_{m\le M}{\mu }_m(B_j)=\mu (B_j)<\mathrm{\infty }$. Thus the full counts are finite almost surely and the truncated integer counts eventually stabilize. Their joint point probabilities converge both to the point probabilities of the full count vector (by eventual stabilization) and to the product Poisson masses with means $\mu (B_j)$ (by continuity of the Poisson mass formula in its mean). Hence the full counts are independent Poisson variables with means $\mu (B_j)$. Therefore $N$ satisfies Poisson random measure on a standard Borel space.

Since $\mathbb{E}\mathrm{\Gamma }(\mathsf{X})=\alpha (\mathsf{X})<\mathrm{\infty }$, $\mathrm{\Gamma }(\mathsf{X})<\mathrm{\infty }$ almost surely: if it were infinite on a set of positive probability, its expectation would exceed every finite bound. Also, $\mathrm{\Gamma }(A)$ is measurable for every $A$ as a monotone limit of finite coordinate sums.

For $u<1$, ${\int }_0^{\mathrm{\infty }}(e^{ut}-1)t^{-1}{e}^{-t}dt={\int }_0^u(1-v{)}^{-1}dv=-\log (1-u)$: use $(e^{ut}-1)\mathrm{/}t={\int }_0^u{e}^{vt}dv$, Tonelli on the positive or negative part, and [F6]. In particular $\mathbb{E}{e}^{\delta \mathrm{\Gamma }(\mathsf{X})}=(1-\delta {)}^{-\alpha (\mathsf{X})}<\mathrm{\infty }$, by monotone convergence [F16] on the nonnegative truncations. For general $\mathrm{\mid }{u}_j\mathrm{\mid }<\delta$, the truncated exponentials are dominated by $e^{\delta \mathrm{\Gamma }(\mathsf{X})}$; [F16] therefore gives $\mathbb{E}{e}^{{\sum }_j{u}_j\mathrm{\Gamma }(A_j)}={\prod }_j(1-u_j{)}^{-\alpha (A_j)}$.

Let $J_{+}=\{j:\alpha (A_j)>0\}$. For $j\in J_{+}$, [F4], [F5], and the Euler integral [F19], with $t=(1-u)y$, give $\mathbb{E}{e}^{uY}=\mathrm{\Gamma }(a{)}^{-1}{\int }_0^{\mathrm{\infty }}{y}^{a-1}{e}^{-(1-u)y}dy=(1-u{)}^{-a}$ for $Y\sim \mathrm{Gamma}(a,1)$ and $u<1$. Thus the vector $(\mathrm{\Gamma }(A_j){)}_{j\in J_{+}}$ and the product of the corresponding Gamma laws have the same moment-generating transform near zero by step 4.3; [F3] supplies that finite product law, and [F7] identifies the distributions when $J_{+}$ is nonempty; if $J_{+}$ is empty this clause is vacuous. For each $j\mathrm{\notin }{J}_{+}$, step 3.3 gives $\mathbb{E}\mathrm{\Gamma }(A_j)=0$. If $\mathrm{\Gamma }(A_j)>0$ with positive probability, some event $\{\mathrm{\Gamma }(A_j)\ge 1\mathrm{/}q\}$ has positive probability, forcing its nonnegative expectation to be positive; hence $\mathrm{\Gamma }(A_j)=0$ almost surely. Since there are finitely many cells, these zero coordinates are simultaneously zero almost surely. Their events in any measurable rectangle have probability zero or one, so adjoining these constants preserves the product law and independence.

For a partition with $r\ge 2$ positive cells and parameters $a_1,\dots ,a_r$, the independent Gamma increments have product density ${\prod }_j{z}_j^{a_j-1}{e}^{-z_j}\mathrm{/}\mathrm{\Gamma }(a_j)$. Change variables to $s={\sum }_j{z}_j$ and $p_j=z_j\mathrm{/}s$ for $j<r$, with $p_r=1-{\sum }_{j<r}{p}_j$. Its Jacobian has absolute value $s^{r-1}$: factor $s$ from each of the $r-1$ proportion columns, then add the first $r-1$ rows of the remaining matrix to its last row, whose first entry becomes ${\sum }_j{p}_j=1$ and whose other entries become zero. The inverse map is $s={\sum }_j{z}_j$, $p_j=z_j\mathrm{/}s$, so this is a $C^1$ diffeomorphism on the positive orthant and open simplex. The joint density factors as the Gamma$({\sum }_j{a}_j,1)$ density in $s$ times $\mathrm{\Gamma }({\sum }_j{a}_j){\prod }_j{p}_j^{a_j-1}\mathrm{/}{\prod }_j\mathrm{\Gamma }(a_j)$ on the simplex. Integrating the normalized Gamma factor in $s$, which has total mass one by [F4], leaves the second factor as the marginal density of $p$. By [F9] this is the Dirichlet law. With one positive cell the normalized mass is one, and zero-base cells have zero mass by step 5.1.

The total $\mathrm{\Gamma }(\mathsf{X})$ is Gamma$(\alpha (\mathsf{X}),1)$ by step 5.1, so it is strictly positive almost surely; step 4.2 gives finiteness. Since $\alpha (\mathsf{X})>0$, the space $\mathsf{X}$ is nonempty; choose $x_0\in \mathsf{X}$ and set $G(A)=\mathrm{\Gamma }(A)\mathrm{/}\mathrm{\Gamma }(\mathsf{X})$ on that probability-one event, assigning ${\delta }_{x_0}$ on its null complement. The event is measurable and each evaluation $G(A)$ is measurable, so [F12] makes $G$ a random probability measure with the partition laws from step 6.1.

Finite evaluation cylinders form a generating pi-system for the evaluation sigma-algebra. For any $A_1,\dots ,A_s\in \mathcal{A}$, the nonempty intersections of $A_i$ and $A_i^c$ form a finite partition, and each $G(A_i)$ is the sum of the corresponding cell masses. Hence its joint law is fixed by step 6.1. Two probability laws with those partition laws therefore agree on the generating pi-system; [F10] gives equality on the entire evaluation sigma-algebra. By [F15], this is uniqueness of $DP(\alpha )$.

The nonempty finite discrete space $S=\{1,\dots ,k\}$ is standard Borel by [F7]. Define $\alpha (B)={\sum }_{j\in B}{a}_j$ for $B\subseteq S$, equivalently $\alpha ={\sum }_{j=1}^k{a}_j{\delta }_j$. By [F7] this is a measure, with finite positive total ${\sum }_{j=1}^k{a}_j$, so [F1] applies to $(S,\mathcal{P}(S),\alpha )$. Thus the law of $P$ is that of $Z_j\mathrm{/}{\sum }_{h=1}^k{Z}_h$, where the $Z_j$ are independent $\mathrm{Gamma}(a_j,1)$ variables, and it is the Dirichlet law [F6].

For $u<1$, [F2] and the change of variables $t=(1-u)z$ in [F3] give $\mathbb{E}{e}^{u{Z}_j}=\mathrm{\Gamma }(a_j{)}^{-1}{\int }_0^{\mathrm{\infty }}{z}^{a_j-1}{e}^{-(1-u)z}dz=(1-u{)}^{-a_j}$. For $W_{\mathrm{\ell }}={\sum }_{j\in I_{\mathrm{\ell }}}{Z}_j$, independence therefore gives the joint moment-generating function ${\prod }_{\mathrm{\ell }=1}^r(1-u_{\mathrm{\ell }}{)}^{-b_{\mathrm{\ell }}}$ for $\mathrm{\mid }{u}_{\mathrm{\ell }}\mathrm{\mid }<\delta <1$, since the groups use disjoint coordinates in the finite product law [F5].

By [F5], the product law of independent $\mathrm{Gamma}(b_{\mathrm{\ell }},1)$ variables exists and has the same joint transform. Both laws have finite exponential moment at every $0<\delta <1$, since the transform at $(\delta ,\dots ,\delta )$ is finite. Applying [F4] to the difference of these two finite measures shows that $(W_1,\dots ,W_r)$ has that product Gamma law.

Normalize the grouped variables by their common positive total. The resulting vector is Dirichlet with parameters $(b_1,\dots ,b_r)$ by [F1], while $W_{\mathrm{\ell }}\mathrm{/}{\sum }_h{W}_h={\sum }_{j\in I_{\mathrm{\ell }}}{P}_j$ by step 1.1. This proves the claim for $r\ge 2$. For $r=1$ the only coordinate sum is ${\sum }_{j=1}^k{P}_j=1$, which is the stated one-category law.

For $x=(x_1,\dots ,x_n)$ put ${\beta }_x=\alpha +{\sum }_{i=1}^n{\delta }_{x_i}$. This is a finite nonzero measure because its total mass is $\alpha (\mathsf{X})+n$ by [F8]. The existence theorem [F1] therefore defines $DP({\beta }_x)$ for every $x$.

Fix a finite evaluation cylinder $C=\{G:(G(A_1),\dots ,G(A_s))\in H\}$ with Borel $H$, and form the finite Boolean partition generated by $A_1,\dots ,A_s$. On each cell $P_j$, the updated parameter is ${\beta }_x(P_j)=\alpha (P_j)+{\sum }_i{\mathbf{1}}_{P_j}(x_i)$. Each count is a measurable finite-valued function of $x$ by [F9], so $x\mapsto DP({\beta }_x)(C)$ is measurable: it is constant on each of finitely many count-pattern preimages.

For each $G\in \mathcal{P}(\mathsf{X})$, the map $A\mapsto G(A)$ is a probability kernel from the evaluation-measurable space $\mathcal{P}(\mathsf{X})$ to $(\mathsf{X},\mathcal{A})$. Its finite product $G^{\otimes n}$ is a probability kernel by [F2]; on rectangles $D_1\times \cdots \times D_n$ it has value ${\prod }_{i}G(D_i)$, which is evaluation-measurable. The proper model in [F3] therefore gives a joint probability $J$ for $(G,X_{1:n})$ and its data marginal $M$.

Fix a finite-partition cylinder $C$ and a data rectangle $D=D_1\times \cdots \times D_n$. Refine the partition defining $C$ by all $D_i$ to obtain a finite measurable partition $P_1,\dots ,P_m$ of $\mathsf{X}$. The data rectangle is a disjoint union of ordered cell-pattern blocks $P_{j_1}\times \cdots \times P_{j_n}$. For one such block let $y_j=\mathrm{\#}\{i:j_i=j\}$. If $y_j>0$ for a cell with $\alpha (P_j)=0$, then $G(P_j)=0$ almost surely by [F1], so the block has prior-predictive mass zero.

The finite evaluation cylinders form a generating pi-system. The class of sets $C$ for which $x\mapsto DP({\beta }_x)(C)$ is measurable contains this pi-system, contains the whole space, is closed under complements, and is closed under countable disjoint unions by pointwise limits of partial sums. Dynkin's theorem [F7] gives measurability on the full evaluation sigma-algebra. Each section is a probability measure by [F1], so $K$ is a probability kernel.

Otherwise omit cells with $\alpha (P_j)=0$ (their counts are zero). On the remaining cells the prior vector is Dirichlet with positive parameters $a_j=\alpha (P_j)$. Given that vector, the likelihood of this particular ordered pattern is ${\prod }_{j}G(P_j{)}^{y_j}$, a constant multiple ${\prod }_j{y}_j!\mathrm{/}n!$ of the multinomial count likelihood. By [A2] and [F5], its posterior vector is Dirichlet$(a_1+y_1,\dots ,a_m+y_m)$ with positive finite evidence. Coarsening to the cells defining $C$ gives the same cylinder probability as $DP({\beta }_x)$ by [F6]. This probability is constant over the ordered block because its cell counts are fixed.

Summing step 2.2 over the ordered blocks contained in $D$ gives $J(C\times D)={\int }_{D}K(x,C)M(dx)$ for every finite-partition cylinder $C$ and data rectangle $D$. For fixed such $C$, the two sides define finite measures of $D$; their total masses agree by taking $D={\mathsf{X}}^n$. Finite-measure uniqueness [F7] extends the identity to every $D\in {\mathcal{A}}^{\otimes n}$.

Now fix any $D\in {\mathcal{A}}^{\otimes n}$. The set functions $C\mapsto J(C\times D)$ and $C\mapsto {\int }_{D}K(x,C)M(dx)$ are finite measures on the evaluation sigma-algebra; the second is a measure because $K$ is a probability kernel. They have common total mass $M(D)$ and agree on every finite-partition cylinder by step 3.1. These cylinders form a generating pi-system, so [F7] extends equality to every measurable $C$. By [F4], $K(x;\cdot )$ is the claimed posterior version. Null data blocks contribute zero to both sides, so the proof imposes no pointwise uniqueness there.

Put ${\beta }_x=\alpha +{\sum }_{i=1}^n{\delta }_{x_i}$. For $n\ge 1$, [F1] makes the posterior law $DP({\beta }_x)$; for $n=0$ it is the prior $DP(\alpha )$. In either case, ${\beta }_x(\mathsf{X})=\alpha (\mathsf{X})+n>0$.

Let $b={\beta }_x(A)$ and $c={\beta }_x(A^c)$. If $b=0$, [F3] gives $G(A)=0$ almost surely under $DP({\beta }_x)$; if $c=0$, it gives $G(A)=1$ almost surely. If both are positive, apply [F4] to one Bernoulli draw on the partition $(A,A^c)$: its probability of the first cell is the Dirichlet-multinomial evidence $b\mathrm{/}(b+c)$, which equals ${\mathbb{E}}_{DP({\beta }_x)}G(A)$ by the sampling kernel [F2]. Thus in all cases the predictive probability is $b\mathrm{/}(b+c)=(\alpha (A)+{\sum }_i{\mathbf{1}}_A(x_i))\mathrm{/}(\alpha (\mathsf{X})+n)$.