Show that Chinese restaurant process is exchangeable

Question

Chinese restaurant process(CRP) is a process such that $X_1 \sim v(\cdot)$, $v$ is some distribution. Afterwards, $$\mathbb{P}_{\theta}\left[X_{n+1} \in \cdot | {X}_{1},...,X_n\right]=\frac{\theta}{n+\theta} \nu(\cdot)+\sum_{j=1}^{K_{n}} \frac{n_{j, n}}{n+\theta} \delta_{X_{j}^{*}}(\cdot) \quad$$ where $\theta>0$, $K_n$ is number of unique value of ${X_1,...,X_n}$ , $X_j^*$ is $j$th unique value, $n_{j,n}$ is number of $X_i$ such that $X_i = X_j^*$.
Generally, we would say new customer will select a new table with propability $\frac{\theta}{n+\theta}$, under this case, this customer may still choose a value from $v(\cdot)$ such that $X_{n+1}$ is equal to one of ${X_1,...,X_n}$, am I right?
How can I show that ${X_1,...,X_n}$ is exchangeable $\forall n$? Any hint?

Answer 1

CRP can be defined in a little more concise way, i.e.

$$X_{n+1}|X_1, \dots, X_n\sim \frac\theta{n+\theta}\nu + \frac1{n+\theta}\sum_{j=1}^n \delta_{X_j} $$

I can show exchangeability for discrete $\mu$ by induction. Let's assume $\forall_{k\leq n}(X_1, \dots X_k)$ is exchangeable. Then \begin{align} p(a_{1:n+1}) &= p(a_{1:n-1})p(a_n, a_{n+1}|a_{1:n-1}) \\ & = p(a_{1:n-1}) \frac1{n-1+\theta} \left(\theta\nu(a_n)+\sum_{j=1}^{n-1}1_{a_j=a_n}\right) \frac1{n+\theta} \left(\theta\nu(a_{n+1})+\sum_{j=1}^{n-1}1_{a_j=a_{n+1}}+1_{a_n=a_{n+1}}\right) \\ &= p(a_{1:n-1})\beta(\text{ expr} + (\theta\nu(a_n)+\sum_{j=1}^{n-1}1_{a_j=a_n})1_{a_n=a_{n+1}}) \end{align} $\beta$ being constant and expr as well as what comes after the expr being expressions that are invariant to exchanging $a_n \leftrightarrow a_{n+1}$ (easily checked). So now you have $$ p(a_{1:n-1}, a_n, a_{n+1}) = p(a_{1:n-1}, a_{n+1}, a_n) \\ p(a_{1:n}, a_{n+1}) = p(\sigma(a_{1:n}), a_{n+1}) $$

Hence $(X_1, \dots, X_{n+1})$ are exchangeable. Exchangeability of $(X_1)$ is trivial and exhangeability of $(X_1, X_2)$ follows from the calculation above, QED. I tried a similar approach for nondiscrete $\nu$ but I failed :( . Hope this helps!