- Boxes
- definitions
- Ellipses
- theorems and lemmas
- Blue border
- the statement of this result is ready to be formalized; all prerequisites are done
- Orange border
- the statement of this result is not ready to be formalized; the blueprint needs more work
- Blue background
- the proof of this result is ready to be formalized; all prerequisites are done
- Green border
- the statement of this result is formalized
- Green background
- the proof of this result is formalized
- Dark green background
- the proof of this result and all its ancestors are formalized
- Dark green border
- this is in Mathlib
A distribution consists of nonnegative real weights \(p_a\) with \(\sum _a p_a=1\). Its expectation is \(\sum _a p_a f(a)\), and an event probability is the expectation of its indicator. Such a distribution cannot exist on an empty type.
Kernels \(K\) on \(\alpha \) and \(L\) on \(\beta \) are dual with respect to \(H:\alpha \times \beta \to \mathbb R\) if \(\mathbb {E}_x[H(X_1,y)]=\mathbb {E}_y[H(x,Y_1)]\) for all \(x\) and \(y\).
A family of kernels \((K_t)_{t\ge 0}\) moves the chain from time \(t\) to time \(t+1\) with \(K_t\); \(\mathrm{iterateSeq}(K,n,f)(a)\) is the expectation of \(f\) at time \(n\) from \(a\). A constant family gives the iterates of a single kernel.
The jump chain \(J\) of \(K\) is the step conditioned on moving: \(J(x,y)=K(x,y)/(1-K(x,x))\) for \(y\ne x\) and \(J(x,x)=0\), except that a state with \(K(x,x)=1\) stays absorbing. Two kernels have the same jump chain if their jump chains are equal.
A finite kernel assigns a distribution to every state. Its operator iterates compute expectations at finite times; trajectory functionals additionally record the history.
A kernel \(K\) on \(\alpha \) lumps to a kernel \(L\) on \(\beta \) along \(f:\alpha \to \beta \) if \(K(x)\circ f^{-1}=L(f(x))\) for every \(x\), equivalently \(\mathbb {E}_x[g(f(X_1))]=\mathbb {E}_{f(x)}[g(Y_1)]\) for every observable \(g\).
The majority map is \(m(p)=3p^2-2p^3\). Conformist transmission (Boyd and Richerson, Eq. 7.1) is the recursion \(p'=p+Dp(1-p)(2p-1)\): a naive individual whose three models include \(j\) holders of a variant acquires it with probability \(0\), \(\frac13-\frac D3\), \(\frac23+\frac D3\), \(1\) for \(j=0,1,2,3\). Galam’s majority rule with groups of three is the recursion \(P'=P^3+3P^2(1-P)\).
The observables \(\varphi _i\) of \(K\) have mean-field map \(F\) if \(\mathbb {E}_x[\varphi (X_1)]=F(\varphi (x))\) for every \(x\). A lumping transfers a mean-field map, and with \(F\) the identity every \(\varphi _i\) keeps its expectation at all times.
A deterministic update \(\mathrm{step}\colon S\times R\to S\) driven by a uniform round \(r\in R\) defines the kernel \(K(s)=\mathrm{law}(\mathrm{step}(s,r))\). Its \(T\)-step expectations are expectations over \(T\) i.i.d. uniform rounds.
The lazy version of a kernel \(K\) is \((I+K)/2\): it puts weight at least \(1/2\) on every self-loop, charges everything \(K\) charges, and has the same stationary distributions as \(K\). On a graph without isolated vertices the simple random walk \(D^{-1}A\) moves to a uniform neighbour, so its expectations are neighbour averages, and the lazy random walk is \((I+D^{-1}A)/2\).
- Dynamics.Kernel.lazy
- Dynamics.Kernel.lazy_weight
- Dynamics.Kernel.lazy_expect
- Dynamics.Kernel.lazy_stationary_iff
- Dynamics.Kernel.lazy_weight_self_ge_half
- Dynamics.Kernel.lazy_selfLoop_pos
- Dynamics.Kernel.lazy_weight_pos
- Dynamics.Kernel.uniformNeighbor
- Dynamics.Kernel.uniformNeighbor_support
- Dynamics.Kernel.uniformNeighbor_expect
- Dynamics.Kernel.uniformNeighbor_expect_eq_avg
- Dynamics.Kernel.lazyNeighbor
- Dynamics.Kernel.lazyNeighbor_weight
- Dynamics.Kernel.lazyNeighbor_expect
Iterated uniform averages over two finite sets commute; in particular an outer average commutes with the trajectory expectation \(\mathrm{expList}\), which also commutes with finite sums and vanishes on the zero functional.
The binomial law on \(\{ 0,\dots ,n\} \) has weights \(\binom nk p^k(1-p)^{n-k}\), those of Mathlib’s binomial distribution. The number of heads of independent Bernoulli(\(p\)) coins indexed by a set of size \(n\) has this law, so its mean is \(np\). The indicator of an event is a Bernoulli coin with the probability of the event, and an independent product transported coordinatewise is the product of the transported coordinates.
- Dynamics.countFin
- Dynamics.Distribution.binomial
- Dynamics.Distribution.binomial_weight_eq
- Dynamics.Distribution.map_decide_eq_bernoulli
- Dynamics.Distribution.independent_map_pi
- Dynamics.Distribution.card_countFin_eq
- Dynamics.Distribution.independent_bernoulli_map_countFin
- Dynamics.Distribution.independent_bernoulli_map_card
- Dynamics.Distribution.binomial_expect_val
The finite average is Mathlib’s finite expectation, \(\operatorname {avg}(f)=\mathbb {E}_{a\in A}f(a)\) (Finset.expect); both vanish on an empty type. On a nonempty type the independent product of uniform distributions on \(A\), indexed by a finite set \(I\), is the uniform distribution on \(A^I\). Hence \(\mathrm{expList}\) over \(T\) rounds is the expectation of \(F\) over \(T\) i.i.d. uniform draws, both as Mathlib’s \(\mathbb {E}_{\omega \colon \{ 0,\ldots ,T-1\} \to A}\) and under the product distribution.
A distribution \(p\) on a finite type is a probability mass function (Mathlib’s PMF); the uniform distribution, point masses and pushforward are PMF.uniformOfFintype, PMF.pure and PMF.map. Equip the type with a \(\sigma \)-algebra containing the singletons (hence every set). Under the induced measure \(\mu _p\), the expectation of \(f\) is \(\int f\, d\mu _p\) and the probability of an event \(S\) is \(\mu _p(S)\). The measure of an independent product is the product measure \(\bigotimes _i\mu _{p_i}\), so the coordinates \(x\mapsto Y_i(x_i)\) are independent random variables in Mathlib’s sense (iIndepFun).
A sum over the darts of \(G\) is the sum over the adjacent ordered pairs; along a walk from \(u\) to \(v\) the differences \(\psi (d_1)-\psi (d_2)\) telescope to \(\psi (u)-\psi (v)\); and over any set of distinct darts \(\sum _d(\psi (d_1)-\psi (d_2))^2\le \sum _{i\sim j}(\psi (i)-\psi (j))^2\).
If \(K\) and \(L\) are dual with respect to \(H\), then \(\mathbb {E}_x[H(X_t,y)]=\mathbb {E}_y[H(x,Y_t)]\) for every \(t\).
For a uniform dart \(d\) of \(G\), \(\mathbb {E}F(d_1,d_2)=\sum _v\sum _{u\in N(v)}F(v,u)/(2|E|)\); reversing \(d\) preserves the law, its underlying edge is a uniform edge, and its tail is \(v\) with probability \(\deg v/(2|E|)\).
On the complete graph the darts are the ordered pairs of distinct vertices, \(n(n-1)\) of them, and a sum over them is the sum over all ordered pairs minus the diagonal. A one-way protocol step on the dart \((u,v)\) updates the state of the responder \(v\) against the initiator \(u\).
The expectation over \(T\) draws only evaluates its functional on lists of length \(T\). For \(k\le T\), a functional of the first \(k\) draws has the same expectation over \(T\) draws as over \(k\) draws; for \(k{\lt}T\), the draw after them is a fresh uniform sample.
Let \(K\) be a kernel on configurations \(V\to \{ 0,1\} \) for which the all-one configuration \(\mathbf1\) is absorbing and the non-consensus probability tends to zero from \(s\). If \(K\varphi =\varphi \) and \(\varphi (\mathbf1)\ne \varphi (\mathbf0)\), the probability of fixation in \(\mathbf1\) from \(s\) is \((\varphi (s)-\varphi (\mathbf0))/(\varphi (\mathbf1)-\varphi (\mathbf0))\). For instance, a harmonic \(q^{k}\), with \(k\) the number of ones out of \(n\), gives \((1-q^k)/(1-q^n)\). Affine images \(u\varphi +v\) of harmonic observables are harmonic.
Let \(V\ge 0\) vanish on \(B\) and be at least \(V_{\min }{\gt}0\) off \(B\), with \(\mathbb {E}[V(X_{t+1})\mid X_t=x]\le \rho V(x)\) for \(x\notin B\). Then \(\Pr _a(T_B{\gt}t)\le \rho ^tV(a)/V_{\min }\).
Under an independent product, resampling one coordinate does not change the law, so the expectation can be conditioned on the value of one coordinate. Two distinct coordinates are independent, and so are functions of disjoint sets of coordinates; centred coordinate functions have additive second and third moments. If \(x\) and \(y\) are independent families, the family \((\varphi _i(x_i,y_i))_i\) is independent, with the coordinatewise laws.
- Dynamics.Distribution.independent_expect_update
- Dynamics.Distribution.independent_expect_eq_sum_update
- Dynamics.Distribution.independent_expect_fin_succ
- Dynamics.Distribution.independent_prob_fin_succ
- Dynamics.Distribution.independent_expect_mul_of_update
- Dynamics.Distribution.independent_expect_pair
- Dynamics.Distribution.independent_expect_sum_sq
- Dynamics.Distribution.independent_expect_sum_cube
- Dynamics.Distribution.expect_expect_coord
- Dynamics.Distribution.expect_mul_of_dep
\(Kg(x)=K(x,x)g(x)+(1-K(x,x))Jg(x)\), so \(g\) is harmonic at \(x\) for \(K\) iff it is for \(J\). If the rows of \(K\) and \(L\) are proportional off the diagonal with positive factors, they have the same jump chain; a lazy kernel \((I+K)/2\) has the jump chain of \(K\), and \(J\) is its own jump chain.
- Dynamics.Kernel.sum_erase_weight
- Dynamics.Kernel.weight_eq_zero_of_weight_self
- Dynamics.Kernel.eq_point_of_weight_self
- Dynamics.Kernel.jump_of_weight_self
- Dynamics.Kernel.jump_weight_self
- Dynamics.Kernel.weight_eq_mul_jump
- Dynamics.Kernel.apply_eq_jump
- Dynamics.Kernel.apply_eq_self_iff_jump
- Dynamics.Kernel.sameJumpChain_of_weight
- Dynamics.Kernel.jump_jump
- Dynamics.Kernel.jump_eq_self
- Dynamics.Kernel.lazy_sameJumpChain
- Dynamics.Kernel.SameJumpChain.symm
- Dynamics.Kernel.SameJumpChain.apply_eq_self_iff
The matrix \(P_{ab}=K(a)(b)\) of a kernel is row stochastic, the transition operator is \(f\mapsto Pf\) and the expectation after \(n\) steps is \(P^nf\).
Distributions with the same weights, or with the same expectations, are equal. The law \(pK^t\) at time \(t\) satisfies \(\mathbb {E}_{pK^t}[g]=\mathbb {E}_p[K^tg]\).
If \(K\) lumps to \(L\) along \(f\), then \((pK^t)\circ f^{-1}=(p\circ f^{-1})L^t\) for every initial law \(p\) and time \(t\), and the expectation of every functional of the trajectory \(f(X_0),\dots ,f(X_t)\) is that of \(Y_0,\dots ,Y_t\) from \(f(x)\). In particular the probabilities of events at time \(t\) and the hitting probabilities agree. Lumpings compose.
\(m(p)\) is the probability that at least two of three independent coins of bias \(p\) show heads. The conformist table adopts the majority of the three models with probability \(D\) and otherwise copies one of them, drawn uniformly; if the three models are independent and each holds the variant with probability \(p\), the variant is acquired with probability \(p+Dp(1-p)(2p-1) =(1-D)p+Dm(p)\), which is \(p\) for \(D=0\) and \(m(p)\) for \(D=1\). Galam’s map is \(m\).
- Dynamics.majorityMap_eq_prob
- Dynamics.majorityMap_nonneg
- Dynamics.majorityMap_le_one
- Dynamics.majorityMap_one_sub
- Dynamics.conformistTable_eq
- Dynamics.conformistMap_eq_expect
- Dynamics.conformistMap_eq_mix
- Dynamics.conformistMap_one
- Dynamics.conformistMap_zero
- Dynamics.conformistMap_nonneg
- Dynamics.conformistMap_le_one
- Dynamics.galamMap_eq
In a round \(r\in \prod _vN(v)\) every vertex picks a neighbour. Under the uniform distribution the picks are independent and uniform: \(\mathbb {E}\prod _vf_v(r_v)=\prod _v\mathbb {E}_{u\in N(v)}f_v(u)\), and, without isolated vertices, \(\mathbb {E}g(r_v)=\mathbb {E}_{u\in N(v)}g(u)\). A uniform vertex \(v\) with a uniform round gives the sequential step “uniform vertex, uniform neighbour \(r_v\)”.
Let \(f\le 1\). If \(t_0\) is reachable from \(s\) along transitions \(a\to b\) with \(K(a,b){\gt}0\) and \(f(t_0)=0\), then \((K^n f)(s){\lt}1\) for some \(n\).
For \(a,b\ge 0\): \(\lceil a\rceil +\lceil b\rceil \le \lceil c\rceil \) if \(a+b+2\le c\), and \(k\lceil a\rceil \le \lceil b\rceil \) if \(k(a+1)\le b\); \(\lceil ay\rceil \le \lceil by\rceil \) if \(0\le a\le b\). For \(w\ge 1\) and \(q{\gt}1\), \(w\le q^{\lceil \log w/\log q\rceil }\); growth by a factor \(q\) from \(\Delta {\gt}0\) passes \(N\ge \Delta \) within \(\log (N/\Delta )/\log q+2\) steps, and \(2^{2^T}\ge N\ge 2\) for some \(T\le 2\log \log N+3\). Moreover \(c^3\le x\) if \(3c\le \log x\); \((\log x)^3/6\le x\) and \((\log x)^4/24\le x\) if \(\log x\ge 0\); \(\varepsilon /2\le \log (1+\varepsilon )\) on \([0,1]\); and \(S/N^2\le C/N\) if \(S\le CN\), \(N{\gt}0\).
- Dynamics.ceil_add_ceil_le
- Dynamics.mul_ceil_le_ceil
- Dynamics.nat_ceil_mul_le_of_le
- Dynamics.le_pow_ceil_real
- Dynamics.le_pow_ceil
- Dynamics.exists_lt_pow_mul
- Dynamics.exists_le_two_pow_two_pow
- Dynamics.pow_three_le_of_log
- Dynamics.log_cube_le
- Dynamics.log_pow_four_div_le
- Dynamics.half_le_log_one_add
- Dynamics.mul_one_div_sq_le
Probability is monotone in the event. An observable \(f\le 1\) with \(f(b){\lt}1\) at a point of positive weight has expectation \({\lt}1\). Markov’s inequality \(\Pr (X\ge c)\le \mathbb {E}X/c\) for \(X\ge 0\), \(c{\gt}0\); in particular \(\Pr (\sum _iY_i(\omega _i)\ge 1)\le \sum _i\mathbb {E}Y_i\) for nonnegative coordinates. One round of \(\mathrm{step}\) lands in an event with probability at least \(1-\mathbb {E}[\mathrm{bad}]\) when \(\mathrm{bad}\ge 0\) is at least \(1\) on every miss. If \(f\le Kf\), then \(n\mapsto K^nf(a)\) is nondecreasing; in particular the occupation probability of an absorbing event is nondecreasing in time. Finally \(e^{-2\log n}=1/n^2\) for \(n\ge 1\), \(e^{-3\log n}=1/n^3\) for \(n{\gt}0\), and \(\log n{\gt}0\) forces \(n\ge 1\).
- Dynamics.Distribution.prob_mono
- Dynamics.Distribution.expect_lt_one
- Dynamics.avg_lt_one
- Dynamics.avg_markov
- Dynamics.avg_markov_one
- Dynamics.Kernel.one_sub_avg_le_prob_ofStep
- Dynamics.Kernel.iterate_monotone
- Dynamics.Kernel.event_monotone
- Dynamics.exp_neg_two_log
- Dynamics.exp_neg_three_log
- Dynamics.one_le_of_log_pos
Uniform averages over a finite (dependent) product factor over its coordinates, each coordinate is uniform on its factor, disjoint blocks of coordinates are independent, and averages are invariant under bijections of the sample space.
The recursively defined expectation over \(T\) independent draws equals the uniform average over functions \(\{ 0,\ldots ,T-1\} \to A\).
Independent coordinates have product weights. Expectations of product observables factor, and transporting weights along a function commutes with expectation.
Under these hypotheses, \(K^{nm}f\le q^n f\), and \(K^t f(a)\to 0\) for every state \(a\).
Let \(X=\sum _iX_i\) be a sum of independent \(\{ 0,1\} \)-valued trials with \(\Pr (X_i=1)=p_i\), and let \(\mu _L\le \mu =\sum _ip_i\le \mu _H\). For \(\delta {\gt}0\),
and for \(0{\lt}\delta {\lt}1\),
The trials are \(\{ 0,1\} \)-valued observables of the coordinates of an independent product of distributions, independent biased coins (counting the heads in any subset), or the coordinates of one uniform round (Mitzenmacher–Upfal, Probability and Computing, Theorems 4.4 and 4.5 with Exercise 4.7). For identical Bernoulli\((p)\) coins, conditioning on one coin gives \(\Pr (E)=p\, \Pr (E\mid \text{heads})+(1-p)\Pr (E\mid \text{tails})\), and the binomial tail \(T(m,k)=\Pr (\)
- Dynamics.Distribution.bernoulli
- Dynamics.Distribution.chernoff_upper_ratio
- Dynamics.Distribution.chernoff_upper
- Dynamics.Distribution.chernoff_lower_ratio
- Dynamics.Distribution.chernoff_lower
- Dynamics.Distribution.bernoulli_chernoff_upper_ratio
- Dynamics.Distribution.bernoulli_chernoff_upper
- Dynamics.Distribution.bernoulli_chernoff_lower_ratio
- Dynamics.Distribution.bernoulli_chernoff_lower
- Dynamics.Distribution.independent_bernoulli_prob_split
- Dynamics.Distribution.binTail
- Dynamics.Distribution.binTail_succ_succ
- Dynamics.avg_chernoff_upper_ratio
- Dynamics.avg_chernoff_upper
- Dynamics.avg_chernoff_lower_ratio
- Dynamics.avg_chernoff_lower
Let \(X=\sum _{i{\lt}n}Y_i(\omega _i)\) with independent uniform \(\{ 0,1\} \)-valued coordinates and \(\mu =\mathbb {E}X\). Then \(\Pr (X\le \mathbb {E}X-\lambda )\le e^{-2\lambda ^2/n}\), and a \(\{ 0,1\} \) coordinate has variance at most its mean. For every real \(t\), \(\mathbb {E}e^{tX}\le \exp (\mu (e^t-1))\); hence \(\Pr (X\ge k)\le \exp (\mu (e^t-1)-tk)\) for \(t\ge 0\) and \(\Pr (X\le k)\le \exp (\mu (e^t-1)-tk)\) for \(t\le 0\). If \(\mathbb {E}X\le \mu \le k\) with \(\mu {\gt}0\), then \(\Pr (X\ge k)\le \exp (k-\mu -k\log (k/\mu ))\); if \(0{\lt}k\le \mu \le \mathbb {E}X\), then \(\Pr (X\le k)\le \exp (k-\mu -k\log (k/\mu ))\). Finally \(\Pr (X\le (1-\delta )\mathbb {E}X)\le \exp (-\delta ^2\mathbb {E}X/2)\) for \(0\le \delta {\lt}1\). Bernstein’s bound also holds for the lower tail \(\Pr (X\le \mathbb {E}X-\lambda )\) (when \(\mathbb {E}Y_i-Y_i\le b\)); for \(\{ 0,1\} \)-valued coordinates and \(\ell {\gt}0\), each of \(\Pr (X\ge \mu +\sqrt{3\ell (\mu +2\ell )})\) and \(\Pr (X\le \mu -\sqrt{3\ell (\mu +2\ell )})\) is at most \(e^{-\ell }\). For independent (not necessarily uniform) \(\{ 0,1\} \) trials with \(\mathbb {E}X\le (1-\varepsilon )c\), \(0\le \varepsilon {\lt}1\) and \(c\ge 0\), \(\Pr (X\ge k)\le \exp (c(\varepsilon -\varepsilon ^2/2)-\varepsilon k)\) for every \(k\).
- Dynamics.avg_lower_tail_le_of_mgf
- Dynamics.avg_hoeffding_lower
- Dynamics.variance_le_avg_of_zero_one
- Dynamics.avg_chernoff_mgf
- Dynamics.avg_chernoff_upper_of_mgf
- Dynamics.avg_chernoff_lower_of_mgf
- Dynamics.avg_chernoff_upper_log
- Dynamics.avg_chernoff_lower_log
- Dynamics.avg_chernoff_lower_mul
- Dynamics.avg_bernstein_lower
- Dynamics.avg_bernstein_of_zero_one
- Dynamics.avg_bernstein_lower_of_zero_one
- Dynamics.Distribution.prob_ge_le_exp_tilt
Let \(X=\sum _{i{\lt}n}Y_i(\omega _i)\) with independent uniform coordinates. If each \(Y_i\) is \(\{ 0,1\} \)-valued, \(\Pr (X\ge \mathbb {E}X+\lambda )\le e^{-2\lambda ^2/n}\). If \(Y_i-\mathbb {E}Y_i\le b\) and \(\sum _i\mathrm{Var}\, Y_i\le \sigma ^2\), then \(\Pr (X\ge \mathbb {E}X+\lambda )\le \exp \bigl(-\lambda ^2/(2\sigma ^2(1+b\lambda /(3\sigma ^2)))\bigr)\).
Let \(\Psi \ge 0\), and for \(t{\lt}T\) let \(c_t\ge 0\), \(\mathbb {E}[\Psi (X_{t+1})\mid X_t=x]\le \Psi (x)-c_t/\Psi (x)\) when \(\Psi (x){\gt}0\), and \(\mathbb {E}[\Psi (X_{t+1})\mid X_t=x]=0\) when \(\Psi (x)=0\). If \(\sum _{t{\lt}T}c_t\ge 4\Psi (x_0)^2\), then \(\Pr _{x_0}(\Psi (X_T)=0)\ge 1/2\).
Let \(c_1{\gt}1\) and \(c_2,c_3,c_4,c_6{\gt}0\). There is \(c_5{\gt}0\) such that for every finite chain and observable \(X\in \{ 0,\dots ,q\} \) with \(c_4\log q\le q\): if from every state below the target \(\Pr [X_{t+1}\ge \min \{ c_1X_t,q\} ]\ge 1-e^{-c_2X_t}\), and \(\Pr [X_{t+1}\ge 1]\ge c_3\) when \(X_t=0\), then \(X\) reaches \(c_4\log q\) within \(c_5\log q+\log _{c_1}(c_4\log q)\) steps with probability at least \(1-q^{-c_6}\) (equivalently within \(C\log q\) steps).
Let \(X=\sum _{i\in I}Y_i(x_i)\) under the independent product of distributions \(p_i\), where \(Y_i\) takes values in \([a_i,b_i]\). Then \(\Pr (X\ge \sum _i\mathbb {E}_{p_i}Y_i+\lambda )\le \exp \bigl(-2\lambda ^2/\sum _i(b_i-a_i)^2\bigr)\) for \(\lambda \ge 0\). The case of uniform \(p_i\) and \(\{ 0,1\} \)-valued \(Y_i\) is the Hoeffding bound of Theorem 23.
If \(K\) and \(L\) have the same jump chain and \(A\) is absorbing for both, then \(\sup _t\Pr ^K_x(X_t\in A)=\sup _t\Pr ^L_x(Y_t\in A)\) for every \(x\).
Let \(S=\sum _{i{\lt}n}f_i(\omega _i)\) with independent uniform coordinates, each \(f_i\) centered and bounded by \(1\) in absolute value, and \(\sigma ^2=\sum _i\mathbb {E}f_i^2\). Then \(\mathbb {E}S^2=\sigma ^2\) and \(\mathbb {E}S^4\le \sigma ^2+3\sigma ^4\). If \(\mathbb {E}X\ge 0\) and \(0\le \theta \le 1\), then \((1-\theta )^2(\mathbb {E}X)^2\le \mathbb {E}X^2\, \Pr (X{\gt}\theta \, \mathbb {E}X)\) (one-sided Paley–Zygmund). If \(\mathbb {E}Z^2=s{\gt}0\) and \(\mathbb {E}Z^4\le 4s^2\), then \(\Pr (s\le 4Z^2)\ge 9/64\) (two-sided Paley–Zygmund); hence \(\Pr (\sigma ^2\le 4S^2)\ge 9/64\) whenever \(\sigma ^2\ge 1\), in particular for centered \(\{ 0,1\} \)-valued coordinates, whose variance is \(p(1-p)\). For \(\{ 0,1\} \)-valued coordinates and every real \(t\), \(\mathbb {E}e^{tS}\le \exp (t\, \mathbb {E}S+nt^2/8)\). Finally, a sum \(X\) of pairwise uncorrelated \(\{ 0,1\} \)-valued variables with mean \(\mu \) has \(\mathbb {E}X^2\le \mu +\mu ^2\).
Let \(\Psi \ge 0\) with every positive value at least \(\Psi _{\min }{\gt}0\), and \(\mathbb {E}[\Psi (X_{t+1})\mid X_t=x]\le (1-\delta _t)\Psi (x)\) for all \(x\) and \(t{\lt}T\). Then \(\Pr _{x_0}(\Psi (X_T){\gt}0)\le \prod _{t{\lt}T}(1-\delta _t)\, \Psi (x_0)/\Psi _{\min }\).
Let \(\varphi \) equal \(\varphi _A\) on an event \(A\) and \(\varphi _B\) on an event \(B\), and let \(S\) be the event of lying in neither. If \(\mathbb {E}_{x_0}\varphi (X_T)=\varphi (x_0)\) and \(m\le \varphi -\varphi _B\le M\) on \(S\), then \(\varphi (x_0)-\varphi _B-(\varphi _A-\varphi _B)\Pr _{x_0}(X_T\in A)\) lies between \(m\Pr _{x_0}(X_T\in S)\) and \(M\Pr _{x_0}(X_T\in S)\). Hence, if \(\varphi _A\ne \varphi _B\), the conservation law holds for every \(T\) and \(\Pr _{x_0}(X_T\in S)\to 0\), then \(\Pr _{x_0}(X_T\in A)\to (\varphi (x_0)-\varphi _B)/(\varphi _A-\varphi _B)\); if moreover \(A\) is absorbing, this is the supremum of the finite-time probabilities.
Let \(A_1\supseteq \cdots \supseteq A_T\) be sets of states such that from \(A_i\) the chain stays in \(A_i\) with probability at least \(1-\varepsilon \) and, for \(i{\lt}T\), enters \(A_{i+1}\) with probability at least \(1-\nu \). From \(A_1\), after \(\ell T\) steps the chain is in \(A_T\) with probability at least \(1-T(\ell \varepsilon +\nu ^\ell )\).
For every functional \(F\) of \(T\) i.i.d. uniform rounds, \(\mathbb {E}F(r_T,\dots ,r_1)=\mathbb {E}F(r_1,\dots ,r_T)\). In particular the \(T\)-step expectations of a round-based process are also obtained by applying the rounds last to first.