Finite-horizon SMC error, CLTs, and degeneracy

Fix $x,x^{\mathrm{\prime }}\in S$ and write $p=k_x$, $q=k_{x^{\mathrm{\prime }}}$. The assumed ordered-pair bound gives $p\le Cq$ almost everywhere, so $q\ge p\mathrm{/}C$. Where $p\le q$, $\min (p,q)=p\ge p\mathrm{/}C$; where $p>q$, the same inequality $p\le Cq$ gives $\min (p,q)=q\ge p\mathrm{/}C$. Hence $\int \min (p,q)d\lambda \ge C^{-1}\int pd\lambda =C^{-1}$.

Let $A_{+}=\{z:p(z)\ge q(z)\}$. For every measurable $A$, $\mathrm{\mid }{\int }_A(p-q)d\lambda \mathrm{\mid }\le \int (p-q{)}^{+}d\lambda$. Since $\int (p-q)=0$, the positive and negative parts have equal integral, and $\int (p-q{)}^{+}d\lambda =1-\int \min (p,q)d\lambda$; equality is attained at $A_{+}$. Thus [F2] gives $\parallel K(x,\cdot )-K(x^{\mathrm{\prime }},\cdot ){\parallel }_{\mathrm{T}\mathrm{V}}=1-\int \min (p,q)d\lambda \le 1-C^{-1}$ by step 1.1.

The bound in step 2.1 holds for every pair $x,x^{\mathrm{\prime }}$, so taking their supremum in [F1] proves $\delta (K)\le 1-C^{-1}$.

For any bounded measurable $h$ and $s\ge 1$, [F1] gives ${\pi }_{s-1}(E_{s}h)={\pi }_{s-1}(k_s({\upsilon }_{s}h))={\tilde{\pi }}_s({\upsilon }_{s}h)={\pi }_s(h)\mathrm{.}$ Iterating this identity yields ${\pi }_k(E_{k+1:t}\bar{\varphi })={\pi }_t(\bar{\varphi })=0$ for every $k<t$; for $k=t$ the identity operator also gives mean zero.

Repeated application of the assumed oscillation contraction gives $\mathrm{osc}(E_{k+1:t}\bar{\varphi })\le {\beta }^{t-k}\mathrm{osc}(\bar{\varphi })={\beta }^{t-k}\mathrm{\Delta }\varphi$. By step 1.1 its ${\pi }_k$-mean is zero, so its infimum is at most zero and its supremum at least zero; hence its sup norm is at most its oscillation. For $k=t$ this is $\mathrm{\parallel }\bar{\varphi }{\mathrm{\parallel }}_{\mathrm{\infty }}\le \mathrm{\Delta }\varphi$.

At time $0$, [F2] and the finite particle law [F7] give IID proposal particles with law ${\tilde{\pi }}_0$. For $h\in L^1({\tilde{\pi }}_0)$, [F4] gives ${\eta }_0^N(h)\to {\tilde{\pi }}_0(h)$. If $\varphi \in L^1({\pi }_0)$, then ${\upsilon }_0\varphi$ is integrable under ${\tilde{\pi }}_0$ and its integral is ${\pi }_0(\varphi )$ by [F1]; also ${\tilde{\pi }}_0({\upsilon }_0)=1$. Applying [F4] to numerator and denominator and dividing on the event that the denominator is positive gives ${\omega }_0^N(\varphi )\to {\pi }_0(\varphi )$. That event has probability tending to one because the denominator average converges to $1$.

Fix $t\ge 1$ and suppose the three convergences hold at $t-1$. First let $h$ be bounded. By [F2] and [F7], conditional on the selected parents, the $X_t^i$ are independent with laws $k_t({\check{X}}_{t-1}^i,\cdot )$; measurability of $k_{t}h$ follows from [F8]. Thus ${\eta }_t^N(h)-{\check{\eta }}_{t-1}^N(k_{t}h)$ has conditional mean zero and conditional variance at most $\mathrm{\parallel }h{\mathrm{\parallel }}_{\mathrm{\infty }}^2\mathrm{/}N$. By [F5] this difference tends to zero in probability. Since $k_{t}h$ is bounded and ${\pi }_{t-1}(k_{t}h)={\tilde{\pi }}_t(h)$ by [F1], the induction hypothesis proves ${\eta }_t^N(h)\to {\tilde{\pi }}_t(h)$.

The selected-law base at time zero follows as well. For bounded $\varphi$, [F3] makes the conditional selected mean equal to ${\omega }_0^N(\varphi )$. Under multinomial selection its conditional variance is at most $\mathrm{\parallel }\varphi {\mathrm{\parallel }}_{\mathrm{\infty }}^2\mathrm{/}N$; under residual selection the deterministic floor counts have no variance and the at most $N$ remaining categorical draws give the same bound. By [F5] and step 1.1, ${\check{\eta }}_0^N(\varphi )\to {\pi }_0(\varphi )$ in probability. For integrable $\varphi$, truncate at $M$. The conditional expected selected average of $\mathrm{\mid }\varphi \mathrm{\mid }{\mathbf{1}}_{\{\mathrm{\mid }\varphi \mathrm{\mid }>M\}}$ is its weighted empirical average by [F3], which converges to the target tail integral by step 1.1. Conditional Markov [F6], using $P(\text{tail average}>ϵ)\le E[\min (1,{\omega }_0^N(\text{tail})\mathrm{/}ϵ)]$ and bounded continuity of $x\mapsto \min (1,x\mathrm{/}ϵ)$, makes the limiting tail probability vanish as $M\to \mathrm{\infty }$. Combining with the bounded truncations proves the selected convergence for all ${\pi }_0$-integrable tests.

For general $h\in L^1({\tilde{\pi }}_t)$, let $h_M=h{\mathbf{1}}_{\{\mathrm{\mid }h\mathrm{\mid }\le M\}}$. The conditional mean of ${\eta }_t^N(\mathrm{\mid }h-h_M\mathrm{\mid })$ is $Y_N={\check{\eta }}_{t-1}^N(k_t\mathrm{\mid }h-h_M\mathrm{\mid })$, measurable by [F8]. The function inside this last empirical average is integrable under ${\pi }_{t-1}$ and its integral is $a_M={\tilde{\pi }}_t(\mathrm{\mid }h-h_M\mathrm{\mid })$. The induction hypothesis gives $Y_N\to a_M$ in probability. Conditional Markov [F6] bounds $P({\eta }_t^N(\mathrm{\mid }h-h_M\mathrm{\mid })>ϵ)$ by $E[\min (1,Y_N\mathrm{/}ϵ)]$. For fixed $M$, bounded continuity of $y\mapsto \min (1,y\mathrm{/}ϵ)$ and convergence in probability to the constant $a_M$ imply that this expectation tends to $\min (1,a_M\mathrm{/}ϵ)$: for any $\eta >0$, split on $\mathrm{\mid }{Y}_N-a_M\mathrm{\mid }\le \eta$ and its complement, use continuity on the first event and convergence in probability on the second. Since $a_M\to 0$ by integrability, the limiting tail probability vanishes. Applying the same truncation to the target integral and combining with step 1.2 proves the proposal empirical convergence for every integrable $h$.

Apply step 2.2 to $h={\upsilon }_t$ and $h={\upsilon }_t\varphi$, where $\varphi \in L^1({\pi }_t)$. Their limiting integrals are $1$ and ${\pi }_t(\varphi )$ by [F1]. The ratio consequently converges to ${\pi }_t(\varphi )$ whenever its denominator is positive; the denominator-zero event has probability tending to zero because its normalized sum converges to $1$. The uniform fallback in [F2] on that event cannot change convergence in probability.

For bounded $\varphi$, the conditional expectation of ${\check{\eta }}_t^N(\varphi )$ is ${\omega }_t^N(\varphi )$ by [F3]. In multinomial resampling the conditional variance is at most $\mathrm{\parallel }\varphi {\mathrm{\parallel }}_{\mathrm{\infty }}^2\mathrm{/}N$. In residual resampling the deterministic floor counts contribute no variance, and the remaining $R\le N$ categorical draws give conditional variance at most $\mathrm{\parallel }\varphi {\mathrm{\parallel }}_{\mathrm{\infty }}^2\mathrm{/}N$ as well. Chebyshev [F5] and step 3.1 prove ${\check{\eta }}_t^N(\varphi )\to {\pi }_t(\varphi )$ for bounded $\varphi$.

For $\varphi \in L^1({\pi }_t)$, truncate to ${\varphi }_M=\varphi {\mathbf{1}}_{\{\mathrm{\mid }\varphi \mathrm{\mid }\le M\}}$. By [F3], the conditional expected selected average of $\mathrm{\mid }\varphi -{\varphi }_M\mathrm{\mid }$ is exactly ${\omega }_t^N(\mathrm{\mid }\varphi -{\varphi }_M\mathrm{\mid })$. Step 3.1 applied to this integrable tail and conditional Markov [F6] make the limiting probability of a tail deviation at most $\min (1,{\pi }_t(\mathrm{\mid }\varphi -{\varphi }_M\mathrm{\mid })\mathrm{/}ϵ)$, which tends to zero as $M\to \mathrm{\infty }$. Combining with step 4.1 proves the selected empirical convergence for all integrable $\varphi$.

Steps 1.2, 2.2, 3.1, 4.1, and 5.1 establish the induction step from $t-1$ to $t$. Steps 1.1 and 2.1 give the base case, so the assertions hold for every fixed finite time. No conclusion is uniform in $t$.

For every integrable $h$ on ${\mathrm{\Theta }}_s$, the Radon–Nikodym identity [F1] gives ${\pi }_{s-1}(E_{s}h)={\pi }_{s-1}(k_s({\upsilon }_{s}h))={\tilde{\pi }}_s({\upsilon }_{s}h)={\pi }_s(h)$. Hence if ${\pi }_s(h)=0$, then $E_{s}h$ has mean zero under ${\pi }_{s-1}$.

For a square-integrable vector function $u$ on ${\mathrm{\Theta }}_s$, expand $u-{\tilde{\pi }}_s(u)=(u-k_{s}u)+(k_{s}u-{\tilde{\pi }}_s(u))\mathrm{.}$ The cross-covariance terms vanish after integrating the first factor conditionally against $k_s$, because $k_s(u-k_{s}u)=0$. Therefore ${\mathrm{Cov}}_{{\tilde{\pi }}_s}(u)=\int {\mathrm{Cov}}_{k_s}(u)(x){\pi }_{s-1}(dx)+{\mathrm{Cov}}_{{\pi }_{s-1}}(k_{s}u)\mathrm{.}$ For $u={\upsilon }_{s}h$ with ${\pi }_s(h)=0$, its ${\tilde{\pi }}_s$ mean is zero by step 1.1. Substituting the multinomial recursion from [F1] thus yields $V_s(h)=V_{s-1}(E_{s}h)+{\tilde{\pi }}_s\text{\hspace{0.17em}⁣}\left[{\upsilon }_s^{2}h{h}^{\mathrm{\top }}\right]\mathrm{.}$

Starting with $h=\bar{\varphi }$ at time $t$, apply step 1.1 to see that each backward iterate $E_{k+1:t}\bar{\varphi }$ has ${\pi }_k$-mean zero. The recursive $\mathrm{\Psi }$ condition also gives its finite target second moment at each such time. Repeated substitution of the one-step identity in step 2.1 gives one new term ${\tilde{\pi }}_k[{\upsilon }_k^2(E_{k+1:t}\bar{\varphi })(E_{k+1:t}\bar{\varphi }{)}^{\mathrm{\top }}]$ at each $k=t,t-1,\dots ,1$, and the remaining initial term is $V_0(E_{1:t}\bar{\varphi })={\mathrm{Cov}}_{{\tilde{\pi }}_0}({\upsilon }_0{E}_{1:t}\bar{\varphi })$. Its mean is zero by step 1.1, so it equals the $k=0$ summand. The same base calculation gives the formula when $t=0$. Each summand is finite: for $k\ge 1$, the recursive $\mathrm{\Phi }$ condition gives a $2+\delta$ proposal moment of ${\upsilon }_k{E}_{k+1:t}\bar{\varphi }$; for $k=0$, the initial ${\mathrm{\Psi }}_0$ moment gives square integrability of ${\upsilon }_0{E}_{1:t}\bar{\varphi }$.

Fix $k<t$. Define $Q_{j,t}h(x)$ by iterating the kernels $g_{j+1},\dots ,g_t$, multiplying by $f_{j+1},\dots ,f_t$, and evaluating $h$ at the final state. Put $H_{j,t}=Q_{j,t}1$ and $H_{t,t}=1$. Measurability follows from [F1], while probability normalization and the bounds on $f_s$ give $a^{t-j}\le H_{j,t}\le b^{t-j}$. Comparing the first transition row gives $H_{j,t}(x)\le C{H}_{j,t}(x^{\mathrm{\prime }})$ for $j<t$. Consequently $r_{k,t}:=H_{k,t}\mathrm{/}{\eta }_k(H_{k,t})$ is positive, at most $C$, and has ${\eta }_k$-mean one.

For $j=k+1,\dots ,t$, set $L_{j,t}(x,dz)=g_j(z\mid x)f_j(z)H_{j,t}(z)\lambda (dz)\mathrm{/}{H}_{j-1,t}(x)$. The recursion for $H$ shows that these are probability kernels, with strictly positive finite denominators. The ratio of two of their density rows is $[g_j(z\mid x)\mathrm{/}{g}_j(z\mid x^{\mathrm{\prime }})][H_{j-1,t}(x^{\mathrm{\prime }})\mathrm{/}{H}_{j-1,t}(x)]\le C^2$ by step 1.1. Thus [F3] gives $\delta (L_{j,t})\le 1-C^{-2}=\rho$. Telescoping the $H$ factors in the product kernel $P_{k,t}=L_{k+1,t}\cdots L_{t,t}$ gives $P_{k,t}h=Q_{k,t}h\mathrm{/}{H}_{k,t}$.

For any probability kernel $K$ and bounded real $h$ of positive oscillation, put $u=(h-\inf h)\mathrm{/}\mathrm{osc}(h)$. Then $0\le u\le 1$, and [F5] under each output law gives $Ku(x)-Ku(x^{\mathrm{\prime }})={\int }_0^1[K(x,\{u>r\})-K(x^{\mathrm{\prime }},\{u>r\})]dr$. By [F4], its absolute value is at most $\delta (K)$. If the oscillation is zero, $K$ preserves the constant and the same oscillation bound is immediate. Hence $\mathrm{osc}(Kh)\le \delta (K)\mathrm{osc}(h)$. Iterating this inequality along the kernels in step 2.1 gives $\mathrm{osc}(P_{k,t}h)\le {\rho }^{t-k}\mathrm{osc}(h)$.

The filtering recursion and iterated integration [F2] yield ${\eta }_{t}h={\eta }_k(Q_{k,t}h)\mathrm{/}{\eta }_k(H_{k,t})$ and ${\prod }_{j=k+1}^t{c}_j={\eta }_k(H_{k,t})$. Thus $E_{k+1:t}h=r_{k,t}{P}_{k,t}h$. Take $h=\psi -{\eta }_t\psi$. Then ${\eta }_k(r_{k,t}{P}_{k,t}h)=0$, and $r_{k,t}{\eta }_k$ is a probability by step 1.1. Therefore the global infimum of $P_{k,t}h$ is at most zero and its supremum is at least zero, so its sup norm is at most its oscillation. Step 3.1 bounds this by ${\rho }^{t-k}\mathrm{osc}(\psi )$; multiplying by $r_{k,t}\le C$ proves the claim. For $k=t$, the mean ${\eta }_t\psi$ lies between $\inf \psi$ and $\sup \psi$, giving the identity-case bound.

Let ${\mathcal{F}}_N$ contain the corrected particles and their weights. By [F2], conditionally on ${\mathcal{F}}_N$ the selected values $Y_1^N,\dots ,Y_N^N$ are IID with law ${\omega }_t^N$. Their centered conditional variance is $s_N^2={\omega }_t^N({\varphi }^2)-{\omega }_t^N(\varphi {)}^2$, which converges in probability to $s^2={\mathrm{Var}}_{{\pi }_t}(\varphi )$ by [F1] and [F3].

Put $m_N={\omega }_t^N(\varphi )$ and ${\xi }_i^N=\varphi (Y_i^N)-m_N$. By [F3], $m_N\to {\pi }_t\varphi$ in probability, hence $m_N=O_P(1)$. For a fixed threshold $a>0$, choose fixed $K$ and then $R\ge K$. On $\{\mathrm{\mid }{m}_N\mathrm{\mid }\le K\}$ and for all sufficiently large $N$ with $a\sqrt{N}>R+K$, the event $\mathrm{\mid }\varphi (Y_i^N)-m_N\mathrm{\mid }>a\sqrt{N}$ implies $\mathrm{\mid }\varphi (Y_i^N)\mathrm{\mid }>R$, and $\mathrm{\mid }\varphi (Y_i^N)-m_N{\mathrm{\mid }}^2\le 4\varphi (Y_i^N{)}^2$ there. Thus the conditional Lindeberg sum is at most $4{\omega }_t^N({\varphi }^2{\mathbf{1}}_{\{\mathrm{\mid }\varphi \mathrm{\mid }>R\}})$ on that event. For fixed $R$, [F3] makes this upper bound converge to $4{\pi }_t({\varphi }^2{\mathbf{1}}_{\{\mathrm{\mid }\varphi \mathrm{\mid }>R\}})$, which tends to zero as $R\to \mathrm{\infty }$ by the finite target second moment. Given any error probability, first choose $K$ so that the probability of $\mathrm{\mid }{m}_N\mathrm{\mid }>K$ is small, then choose $R\ge K$ with this tail integral small, and finally let $N\to \mathrm{\infty }$. This proves that the conditional Lindeberg sum tends to zero in probability using only target $L^2$.

Along any subsequence, choose a further subsequence on which $s_N\to s$ almost surely. If $s>0$, then eventually $s_N>s\mathrm{/}2$; the normalized Lindeberg sum for draws divided by $s_N\sqrt{N}$ is bounded by step 2.1 at threshold $as\mathrm{/}2$, divided by $s_N^2$. It therefore tends to zero in probability, and a further subsequence makes that convergence almost sure. Apply [F4] to obtain a standard-normal limit for the normalized row. Slutsky [F6] with $s_N\to s$ gives convergence of the conditional characteristic function of $N^{-1\mathrm{/}2}{\sum }_i{\xi }_i^N$ to $e^{-u^2{s}^2\mathrm{/}2}$. If $s=0$, conditional [F5] gives $P(\mathrm{\mid }{N}^{-1\mathrm{/}2}{\sum }_i{\xi }_i^N\mathrm{\mid }>a\mid {\mathcal{F}}_N)\le \min (1,s_N^2\mathrm{/}{a}^2)\to 0$, giving the degenerate characteristic-function limit. The subsequence criterion therefore gives convergence in probability of these conditional characteristic functions along the full sequence.

The conditional characteristic functions are bounded by one, so their differences from $e^{-u^2{s}^2\mathrm{/}2}$ converge to zero in $L^1$. For arbitrary real $v,u$, multiply the conditional resampling characteristic function at $u$ by the bounded factor $e^{iv\sqrt{N}({\omega }_t^N(\varphi )-{\pi }_t(\varphi ))}$ and take expectations. The resulting joint characteristic function tends to $e^{-v^{2}V\mathrm{/}2}{e}^{-u^2{s}^2\mathrm{/}2}$. Thus the resampling fluctuation is asymptotically independent of the weighted fluctuation, and their sum has variance $V+s^2$.