Proof. Conditionally on the RRT percolation history up to time \(n\), the parent of vertex \(n+1\) is uniform on \([n]\). Thus the new vertex receives cluster label \(j\) with probability \(p\lvert \Pi_j^{(n)} \rvert/n\), and receives the next unused label with probability \(1-p\). These are exactly the transitions in 1 , so induction on \(n\) gives the equality in law of the label processes. ◻

Proof. Given the history up to time \(s\ge T\), an already occupied aggregated block \(B_r\) is selected with probability \[p\,\frac{\sum_{\ell\in B_r}N_\ell^{(s)}}{s} =p\,\frac{M_r^{(s)}}{s},\] and a new singleton block is opened with probability \(1-p\). These are exactly the transition probabilities of the aggregated restaurant process.

Now condition also on the aggregated seating sequence. When the aggregated sequence visits a block \(B_r\subseteq[K_T]\) at time \(s\), the original table is \(\ell\in B_r\) with probability \(N_\ell^{(s)}/M_r^{(s)}\). This transition depends only on the current occupancies inside \(B_r\). Thus the conditional law factorizes over the blocks \(B_r\subseteq[K_T]\), and each factor is the law of the corresponding fixed-table restaurant. ◻

Proof. Condition on the directing variable \(\Theta\) from Fact [fact:beta-de-finetti]. Given \(\Theta=\theta\), the law is a product Bernoulli\((\theta)\) measure, which is positively associated; this follows first for cylinder functions from the finite Harris–FKG inequality and then for bounded increasing functions by monotone-class approximation. Hence \[\mathbb{E}[f(\xi)g(\xi)\mid\Theta] \ge \mathbb{E}[f(\xi)\mid\Theta]_{\vphantom{|}}\,\mathbb{E}[g(\xi)\mid\Theta].\] For an increasing \(f\), the function \(\theta\mapsto\mathbb{E}_\theta f\) is increasing by the standard coupling \(\mathbf{1}_{\{W_r\le\theta\}}\) with i.i.d. uniform random variables \((W_r)\). Therefore the two conditional expectations are increasing functions of the same real variable \(\Theta\), and Chebyshev’s association inequality for monotone functions on the line gives 2 . ◻

Proof of Theorem 4 assuming Propositions [prop:prob]–[prop:io]. Note that \[\label{eq:representation} \bigl\{N_1^{(n)}\ge N_j^{(n)} \text{ for all }j\ge1\text{ and all }n\ge1\bigr\} =\bigcap_{j=2}^\infty D_j .\tag{6}\] Fix \(\varepsilon\in(0,1)\) and put \(\alpha=(1-\varepsilon)p\). By Proposition [prop:io], \[G_N:=\bigcap_{k=N}^\infty\{L_{2^k}\ge2^{\alpha k}\}\] satisfies \(\mathbb{P}(G_N)>0\) for at least one deterministic \(N\). Fix such an \(N\).

For \(r\ge N\) and \(1\le\ell\le2^r-1\), set \[H_{\ell,r}:= \bigcap_{j=2}^{\ell}D_j\cap \bigcap_{k=N}^{r}\{L_{2^k}\ge2^{\alpha k}\}.\] We claim that there exists \(c_1>0\) such that, for every \(2\le\ell\le2^r-1\), \[\label{eq:one-step} \mathbb{P}(H_{\ell,r}) \ge \bigl(1-\exp(-c_1\ell^\alpha)\bigr)\mathbb{P}(H_{\ell-1,r}).\tag{7}\] Indeed, write \(q(\ell)=\lfloor\log_2\ell\rfloor\) and put \[A_\ell:=\bigcap_{k=N}^{q(\ell)}\{L_{2^k}\ge2^{\alpha k}\},\] with the convention that this is the whole space if \(q(\ell)<N\). By Proposition [prop:posicor], \[\begin{align} \mathbb{P}(H_{\ell,r}\mid\mathcal{F}_{T_\ell}) &=\mathbf{1}_{A_\ell}\, \mathbb{P}\Biggl( \bigcap_{j=2}^{\ell}D_j\cap \bigcap_{k=N\vee(q(\ell)+1)}^{r}\{L_{2^k}\ge2^{\alpha k}\} \,\Bigm|\,\mathcal{F}_{T_\ell}\Biggr)\\ &\ge \mathbf{1}_{A_\ell}\, \mathbb{P}\Biggl( \bigcap_{j=2}^{\ell-1}D_j\cap \bigcap_{k=N\vee(q(\ell)+1)}^{r}\{L_{2^k}\ge2^{\alpha k}\} \,\Bigm|\,\mathcal{F}_{T_\ell}\Biggr) \mathbb{P}(D_\ell\mid\mathcal{F}_{T_\ell}). \end{align}\] On \(A_\ell\), if \(\ell\ge2^N\), \[L_\ell\ge L_{2^{q(\ell)}}\ge 2^{\alpha q(\ell)} \ge2^{-\alpha}\ell^\alpha.\] For \(\ell<2^N\) we use only \(L_\ell\ge1\). Hence, by Proposition [prop:prob], there exists \(c_1>0\) such that, on \(A_\ell\), \[\begin{align} \mathbb{P}(D_\ell\mid\mathcal{F}_{T_\ell}) \ge1-\exp(-cL_\ell)\ge1-\exp(-c_1\ell^\alpha), \end{align}\] where \(c\) is the constant in Proposition [prop:prob]. Taking expectations yields 7 .

Iterating 7 for \(\ell=2,3,\ldots,2^r-1\) gives \[\label{eq:finite-lower} \mathbb{P}(H_{2^r-1,r}) \ge \mathbb{P}\Bigl(\bigcap_{k=N}^r\{L_{2^k}\ge2^{\alpha k}\}\Bigr) \prod_{\ell=2}^{2^r-1}\bigl(1-\exp(-c_1\ell^\alpha)\bigr).\tag{8}\] Letting \(r\to\infty\) in 8 yields \[\mathbb{P}\Bigl(\bigcap_{j=2}^\infty D_j\cap G_N\Bigr) \ge \mathbb{P}(G_N)\prod_{\ell=2}^\infty \bigl(1-\exp(-c_1\ell^\alpha)\bigr)>0,\] and the conclusion follows from 6 . ◻

Proof. By Fact [fact:beta-de-finetti], conditionally on \(\Theta\), the difference \(A_r-B_r\) is a nearest-neighbour random walk with increments \(+1\) with probability \(\Theta\) and \(-1\) with probability \(1-\Theta\), started from \(n-1\). If \(\Theta\ge2/3\), the probability that this walk ever makes table \(2\) strictly larger than table \(1\) is at most \(((1-\Theta)/\Theta)^n\le2^{-n}\). Since \(\Theta\sim\mathrm{Beta}(n,1)\), \[\mathbb{P}(\Theta<2/3)=(2/3)^n.\] For \(n=1\) we compute directly \[\mathbb{P}(\mathcal{D}_2^c) \le\int_0^{1/2}1\,\,\mathrm d\theta +\int_{1/2}^1\frac{1-\theta}{\theta}\,\,\mathrm d\theta =\log2<1.\] For \(n\ge2\), the preceding bound gives there exists a universal constant \(c>0\) such that \[\mathbb{P}\bigl(\mathcal{D}_2^c\bigr) \le2^{-n}+(2/3)^n\le\exp(-cn).\qedhere\] ◻

Proof of Proposition [prop:prob]. At time \(T_j\), table \(j\) has exactly one customer and table \(1\) has \(L_j\) customers. Before time \(T_j\), table \(j\) is absent, so \(D_j\) can fail only after \(T_j\). Apply Theorem 3 with the partition whose only non-singleton block is \(\{1,j\}\). Conditionally on \(\mathcal{F}_{T_j}\), the future comparison between tables \(1\) and \(j\), restricted to visits to these two tables, is a fixed two-table restaurant with initial occupancies \(L_j\) and \(1\). Lemma 1 gives 3 . ◻

Proof of Proposition [prop:posicor]. Let \(\mathbb{Q}\) be a regular conditional law given \(\mathcal{F}_{T_n}\). Apply Theorem 3 to the partition \[\mathcal{B}_n:=\bigl\{\{1,n\},\{2,3,\ldots,n-1\},\{n+1\},\{n+2\},\ldots\bigr\},\] with the empty middle block omitted when \(n=2\). Recall the notation \(C^{\mathcal{B}}\) and \(C_B^{(T)}\) from Definitions 1 and 2. Put \[\mathcal{G}:=\sigma\bigl((C_k^{\mathcal{B}_n}:k>T_n),\,C_{\{2,\ldots,n-1\}}^{(T_n)}\bigr), \qquad \xi:=\bigl(\mathbf{1}_{\{C_{\{1,n\}}^{(T_n)}(r)=1\}}:r\ge1\bigr).\] By Theorem 3, \(\xi\) is independent of \(\mathcal{G}\), and conditionally on \(\mathcal{G}\) its law is that of a fixed two-table restaurant started from \((L_n,1)\). Let \[E:=\bigcap_{j=2}^{n-1}D_j\cap\bigcap_{k=1}^m\{L_{j_k}\ge a_k\}, \qquad F:=D_n.\] Conditionally on \(\mathcal{G}\), there are bounded increasing functions \(f,g\) on \(\{0,1\}^{\mathbb{N}}\) such that \(\mathbf{1}_E=f(\xi)\) and \(\mathbf{1}_F=g(\xi)\). Hence Proposition [thm:correlation] gives \[\mathbb{Q}(E\cap F\mid\mathcal{G}) \ge \mathbb{Q}(E\mid\mathcal{G})\,\mathbb{Q}(F\mid\mathcal{G}) = \mathbb{Q}(E\mid\mathcal{G})\,\mathbb{Q}(F).\] Taking \(\mathbb{Q}\)-expectations yields \[\mathbb{Q}(E\cap F)\ge \mathbb{Q}(E)\,\mathbb{Q}(F),\] which is 4 . ◻

Proof. For completeness, we recall the short argument. Run the continuous-time version in which each customer gives births at rate \(1\). Each birth joins the parent’s table with probability \(p\) and opens a new table with probability \(1-p\), independently of everything else. Observed at birth times, this has the transition probabilities 1 . The total population is a Yule process \(Z^{(1)}\), while births that keep the first-table label occur from first-table customers at total rate \(p\) times the current first-table size. Hence the first table evolves as a Yule process \(Z^{(p)}\), observed at the stopping times \(\tau_n\). ◻

Proof. The first two bounds follow directly from 9 . The bounds for \(\tau_n\) follow by applying these estimates to \(Z^{(1)}((1-\varepsilon)\log n)\) and \(Z^{(1)}((1+\varepsilon)\log n)\). ◻

Proof. Choose \(\delta\in(0,\varepsilon)\). By the coupling ?? , \[\mathbb{P}\bigl(N_1^{(n)}<n^{(1-\varepsilon)p}\bigr) \le \mathbb{P}\bigl(\tau_n<(1-\delta)\log n\bigr) +\mathbb{P}\bigl(Z^{(p)}((1-\delta)\log n)<n^{(1-\varepsilon)p}\bigr).\] Both terms are \(O(n^{-c})\) by Lemma 3, since \((1-\delta)p>(1-\varepsilon)p\). ◻

Proof. After the first customer, the events that a new table is opened at subsequent arrivals are i.i.d. Bernoulli\((1-p)\). Put \(m_j:=\left\lfloor j/(2(1-p))\right\rfloor\). A Chernoff bound gives \[\mathbb{P}(T_j<m_j)\le \exp(-c_1j)\] for some \(c_1=c_1(p)>0\). On the event \(\{T_j\ge m_j\}\), monotonicity of the first table gives \(L_j=N_1^{(T_j)}\ge N_1^{(m_j)}\). Choose \(\delta\in(0,\varepsilon)\). For all sufficiently large \(j\), \(m_j^{(1-\delta)p}\ge j^{(1-\varepsilon)p}.\) Therefore, by Lemma 4, there exist \(C,c>0\) such that \[\mathbb{P}\bigl(L_j<j^{(1-\varepsilon)p}\bigr) \le \mathbb{P}(T_j<m_j)+\mathbb{P}\bigl(N_1^{(m_j)}<m_j^{(1-\delta)p}\bigr) \le Cj^{-c}.\qedhere\] ◻

Proof of Proposition [prop:io]. By Lemma 5, \[\sum_{k=1}^\infty \mathbb{P}\bigl(L_{2^k}<2^{(1-\varepsilon)pk}\bigr) \le C\sum_{k=1}^\infty 2^{-ck}<\infty.\] The Borel–Cantelli lemma proves 5 . ◻

Proof. The case \(a=1\) is trivial, so assume \(a<1\) and choose \(\alpha=a/2\). By the monotone coupling in \(p\) and Lemma 5 applied at \(p=a\), there are constants \(C,\eta>0\) such that \[\label{eq:regularity-uniform-L-lower} \sup_{p\in[a,1)}\mathbb{P}\bigl(L_{2^k}<2^{\alpha k}\bigr)\le C2^{-\eta k}.\tag{10}\] With \(I_k:=\{2^k,\ldots,2^{k+1}-1\}\), Proposition [prop:prob] and 10 give \[\begin{align} \sup_{p\in[a,1]}\mathbb{P}\bigl(\exists j\in I_k:D_j^c\bigr) &\le \sup_{p\in[a,1)} \biggl\{\mathbb{P}\bigl(L_{2^k}<2^{\alpha k}\bigr) +\sum_{j\in I_k} \mathbb{E}_p\bigl[ \mathbf{1}_{\{L_{2^k}\ge2^{\alpha k}\}} \mathbb{P}(D_j^c\mid\mathcal{F}_{T_j}) \bigr]\biggr\} \\ &\le C2^{-\eta k}+2^k\exp(-c2^{\alpha k}), \end{align}\] where \(\{L_{2^k}\ge2^{\alpha k}\}\in\mathcal{F}_{T_j}\) and, on this event, \(L_j\ge L_{2^k}\ge2^{\alpha k}\) for \(j\in I_k\). Summing over \(k\ge M\) proves the claim. ◻

Proof. Monotonicity. Fix \(0<p_1<p_2\le1\) and use the coupling above. Let \(A_i\) be the event that the first table is never overtaken, and let \(B_i\) be the event that the first table has the largest limiting weight in the \(\lambda_i\)-process. Then \[A_1\subseteq A_2, \qquad B_1\subseteq B_2.\] By definition, \(\mathbb{P}(A_i)=\rho(p_i)\), while Remark [rem:limit-pn] gives \(\mathbb{P}(B_i)=\theta(p_i)\). Thus \(\rho(p_1)\le\rho(p_2)\) and \(\theta(p_1)\le\theta(p_2)\).

Strictness. Condition on the \(\lambda_2\)-process, and let \(R(t)\) be the size of its first table. Then \[W_1:=\lim_{t\to\infty}\mathrm e^{-t}R(t)\] exists and belongs to \((0,\infty)\) a.s. by the standard martingale convergence theorem for Yule processes; see, for example, Durrett [11]. In this \(\lambda\)-parametrization, each table grows after its birth as a rate-one Yule process. Extra tables born from first-table members during \([0,1]\) form a Poisson process with intensity \(\delta R(s)\,\,\mathrm ds\). If such a table is born at time \(s\), its limiting weight relative to the common factor \(\mathrm e^t\) is \(\mathrm e^{-s}E_s\), with \(E_s\sim{\rm Exp}(1)\) independently. Hence the event \[H:=\{\exists s\in[0,1]\text{ an extra table with }\mathrm e^{-s}E_s>W_1\}\] has conditional probability \[q:=\mathbb{P}(H\mid\lambda_2\text{-process}) = 1-\exp\biggl\{ -\delta\int_0^1 R(s)\exp(-\mathrm e^sW_1)\,\,\mathrm ds \biggr\}>0 \quad\text{a.s.}\] Since \(\mathbb{P}(A_2)=\rho(p_2)>0\), \[\mathbb{P}(A_2\cap H) =\mathbb{E}\bigl[q\mathbf{1}_{A_2}\bigr]>0.\] On \(A_2\cap H\), persistence holds for \(\lambda_2\) but fails for \(\lambda_1\). Hence \[\rho(p_2)-\rho(p_1) \ge \mathbb{P}(A_2\cap H)>0.\] Similarly, since \(\mathbb{P}(B_2)=\theta(p_2)>0\), \[\theta(p_2)-\theta(p_1) \ge \mathbb{P}(B_2\cap H) =\mathbb{E}\bigl[q\mathbf{1}_{B_2}\bigr]>0.\qedhere\] ◻

Proof. First fix a compact interval \(K=[a,b]\subset(0,1)\). The random time \(T_m\) has an exponentially decaying tail uniformly for \(p\in K\): the successive new-table openings occur with probability \(1-p\ge1-b\), so \(T_m\) is dominated by the sum of \(m-1\) geometric random variables with parameter \(1-b\).

On each event \(\{T_m=r\}\) there are only finitely many seating histories \(h=(c_1,\ldots,c_r)\). Each such history has probability polynomial in \(p\), because every step contributes either a factor \(1-p\) for a new table or a factor \(p\) times a deterministic occupancy ratio for an old table choice. Given \(h\), discard all subsequent customers seated outside the first \(m\) tables. By Theorem 3, the relative seating process among tables \(1,\ldots,m\) is a fixed \(m\)-table restaurant whose law depends only on the occupancies at time \(T_m\), not on \(p\). Both events \(\cap_{j=2}^mD_j\) and \(\{X_1>\max_{2\le j\le m}X_j\}\) are determined by this relative process. Thus, conditional on \(h\), their probabilities are constants independent of \(p\).

If we truncate to histories with \(T_m\le R\), the resulting approximants are finite sums of polynomials in \(p\), hence continuous. The error is at most \(\mathbb{P}(T_m>R)\) for both \(\rho_m\) and \(\theta_m\), and this tends to zero uniformly on \(K\). Therefore \(\rho_m\) and \(\theta_m\) are continuous on \((0,1)\).

It remains to check continuity at \(p=1\). Fix \(R\ge1\). If the first \(R\) customers all sit at table \(1\), then \(L_j\ge R\) for every fixed \(j\ge2\), and this event has probability \(p^{R-1}\). By Proposition [prop:prob], \[\mathbb{P}(D_j^c)\le 1-p^{R-1}+\mathrm e^{-cR}, \qquad j\ge2.\] Hence \[1-\rho_m(p) \le \sum_{j=2}^m\mathbb{P}(D_j^c) \le (m-1)\bigl(1-p^{R-1}+\mathrm e^{-cR}\bigr).\] Letting first \(p\uparrow1\) and then \(R\to\infty\) gives \(\rho_m(p)\to1\). The finite analogue of \(\rho\le\theta\) gives \(\rho_m(p)\le\theta_m(p)\le1\), so also \(\theta_m(p)\to1\). ◻

Proof. Fix \(a\in(0,1]\) and put \(K=[a,1]\). Let \(\rho_m,\theta_m\) be the finite approximants from Lemma 7. By the lemma, both are continuous on \(K\).

Note that, for \(p\in K\), \[0\le \rho_m(p)-\rho(p) \le \mathbb{P}\bigl(\exists j>m:D_j^c\bigr), \qquad 0\le \theta_m(p)-\theta(p) \le \mathbb{P}\bigl(\exists j>m:D_j^c\bigr),\] since a later limiting winner must eventually overtake the first table. By ?? , \[\sup_{p\in K}\mathbb{P}\bigl(\exists j>m:D_j^c\bigr)\longrightarrow0.\] Thus \(\rho_m\to\rho\) and \(\theta_m\to\theta\) uniformly on \(K\), which proves the claim since \(a\) is arbitrary. ◻

Proof. Let \(B_M\) be the event that the first \(M\) customers occupy \(M\) distinct tables. Then \(\mathbb{P}(B_M)=(1-p)^{M-1}\). On \(B_M\), the first \(M\) tables are exchangeable thereafter, and limiting ties among them have probability zero; hence \[\theta(p) \le 1-(1-p)^{M-1}+\frac{(1-p)^{M-1}}{M}.\] Letting first \(p\downarrow0\) and then \(M\to\infty\) gives \(\theta(p)\to0\). Since \(0\le\rho(p)\le\theta(p)\), also \(\rho(p)\to0\). ◻