Separate the first coordinate using the finite-function/product equivalence, then induct on \(T\). The empty sample space is handled separately.

Exchange the order of finite summation; for \(\mathrm{expList}\), induct on \(T\).

Distribute products over finite sums; for pushforward interchange the two sums and evaluate each fiber indicator.

Mathlib’s finite expectation is a sum divided by a cardinality. Every point of \(A^I\) has product weight \(|A|^{-|I|}=|A^I|^{-1}\). Combine both with Lemma 3.

Average the first \(n+1\) evolved distributions. The stationarity defect of this Cesàro average is \((p_{n+1}-p_0)/(n+1)\), which tends to zero coordinatewise. Compactness of the finite probability simplex gives a convergent subsequence; continuity of finite sums implies that its limit is stationary.

Take one plus the maximum of the finitely many access times. Antitonicity of survival probabilities puts every state below one at that time. Their finite maximum supplies \(q\). At states with \(f=0\), absorption keeps the expectation zero.

Induct over blocks using positivity and linearity. The geometric bound tends to zero. For arbitrary \(t\), compare with \(m\lfloor t/m\rfloor \) by antitonicity.

Pointwise, \(\varphi -\varphi _B=(\varphi _A-\varphi _B)1_A+(\varphi -\varphi _B)1_S\) (on \(A\cap B\) both sides vanish). Take expectations at time \(T\) and bound the last term by monotonicity. For the limit, take \(M=-m=\sum _a|\varphi (a)-\varphi _B|\) and squeeze. If \(A\) is absorbing, the finite-time probabilities increase, so their limit is their supremum.

Induction on \(T\), unfolding one round of \(\mathrm{expList}\).

Write both sides as uniform averages over \(\mathrm{Fin}\, T\to R\) and reindex by the involution \(i\mapsto T-1-i\).

Markov’s inequality applied to \(e^{tX}\), which factors over the coordinates. Hoeffding’s lemma bounds each Bernoulli factor; for Bernstein, \(e^y\le 1+y+y^2/(2(1-u/3))\) for \(y\le u{\lt}3\) bounds each factor, and \(t\) is chosen as \(\lambda /(\sigma ^2+b\lambda /3)\).

Markov’s inequality applied to \(e^{tX}\), which factors over the coordinates; each factor is \(1+p_i(e^t-1)\le e^{p_i(e^t-1)}\), so \(\mathbb {E}e^{tX}\le e^{\mu _H(e^t-1)}\) for \(t\ge 0\) and \(\mathbb {E}e^{tX}\le e^{\mu _L(e^t-1)}\) for \(t\le 0\). Take \(t=\log (1+\delta )\), respectively \(t=\log (1-\delta )\). The closed forms follow from \(\log (1+\delta )\ge 2\delta /(2+\delta )\) (the first term of the series of \(\log \frac{1+x}{1-x}\) at \(x=\delta /(2+\delta )\)) and \((1-\delta )\log (1-\delta )\ge -\delta +\delta ^2/2\).

Track the indicator of lying outside a set. In \(\ell \) steps the chain leaves \(A_i\) with probability at most \(\ell \varepsilon \), and misses \(A_{i+1}\) in all \(\ell \) steps with probability at most \(\nu ^\ell \). Sum over the \(T\) phases.

Induction on \(n\).

Let \(q=\Pr (\Psi (X_T){\gt}0)\); survival is nonincreasing, so it is at least \(q\) before \(T\). With \(\lambda =q/\Psi (x_0)\), the bound \(1/y\ge 2\lambda -\lambda ^2y\) linearizes the drift: \(\mathbb {E}\Psi (X_{t+1})\le (1+c_t\lambda ^2)\mathbb {E}\Psi (X_t) -2c_t\lambda \Pr (\Psi (X_t){\gt}0)\le \mathbb {E}\Psi (X_t)-c_t\lambda q\). (The paper uses Jensen’s inequality here; this is its optimal-\(\lambda \) form.) Summing, \(0{\lt}m q\le \mathbb {E}\Psi (X_T)\le \Psi (x_0)(1-4q^2)\) if \(q{\gt}0\), where \(m{\gt}0\) is the least positive value of \(\Psi \); hence \(q\le 1/2\).

By induction \(\mathbb {E}\Psi (X_T)\le \prod _{t{\lt}T}(1-\delta _t)\Psi (x_0)\) (the factors are nonnegative unless \(\Psi \equiv 0\)); then Markov’s inequality \(\mathbf1_{\Psi {\gt}0}\le \Psi /\Psi _{\min }\).

\(\sum _r\prod _vf_v(r_v)=\prod _v\sum _{u\in N(v)}f_v(u)\) and \(|\prod _vN(v)|=\prod _v\deg v\); the marginals take \(f_w=1\) for \(w\ne v\).

Group the darts by tail (the darts with tail \(v\) are the neighbours of \(v\)) or by edge (each edge carries two darts).

In the chain stopped on entering \(B\), being outside \(B\) at time \(t\) is the event \(T_B{\gt}t\); apply Theorem 22 to the stopped chain with \(\delta =1-\rho \).

The paper omits the proof. Let \(p=\min \{ c_3,1-e^{-c_2}\} \), \(\theta =1/p\) and \(\beta =c_2/2\). For a large threshold \(x_0\) take \(g(x)=1-\eta (\theta ^x-1)\) for \(x\le x_0\), with \(\eta \) chosen so that \(g(x_0)=1/2\), and \(g(x)=\tfrac 12e^{-\beta (x-x_0)}\) for \(x\ge x_0\); let \(V=g(X)\) below the target and \(V=0\) on it. Below \(x_0\) a step goes up by at least one with probability at least \(p\), and \(pg(x+1)+1-p\le \rho g(x)\) with \(\rho =1-(1-p)\eta /2\); above \(x_0\) growth by \(c_1\) fails with probability at most \(e^{-c_2x}\), and the expected potential is at most \(\tfrac 38e^{-\beta (x-x_0)}\le \rho g(x)\). Since \(V\le 1\) and \(V\ge \tfrac 12q^{-\beta c_4}\) below the target, Lemma 26 gives \(\Pr (T{\gt}t)\le 2\rho ^tq^{\beta c_4}\le q^{-c_6}\) for \(t\ge (1+\beta c_4+c_6)\log q/\log (1/\rho )\).