Answer: —
Corollary 6 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateSuppose Ba is obtained from an anonymous aggregation model with aggregation functions A1, . . . , An. If s ∈T a is the size of the initial coalition, then we get for the absorption probabilities: P(τ k s < ∞) = ga s,f Ca k, for k = 1, . . . , l. The initial coalition S ∈T (or its size s) in the results above can as well be seen as a coalition (or its size) at some stage of the influence process before entering a terminal class. This finishes our analysis of the speed of convergence and absorption probabilities.23 To illustrate the results, we continue the example on mass psychology.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \((\mu_t)_{t\in T}\) summing to \(1\), rational piecewise-linear nondecreasing update rules \(F_t:[0,1]\to[0,1]\) with \(F_t(0)=0\) and \(F_t(1)=1\), and a rational initial yes fraction \(q_0\), consider each population size \(N\) for which all \(N\mu_t\) and \(Nq_0\) are integers. Start with \(Nq_0\) yes opinions; when the current yes count is \(k\), each type-\(t\) agent independently says yes at the next step with probability \(F_t(k/N)\). Let \(\alpha_N\) be the probability of eventually reaching unanimous yes. Does \(\lim_{N\to\infty}\alpha_N\) exist along these population sizes, and, if so, what is its exact value?
A society is given by its support: \(T\) lists the \(\tau\) types with positive binary-rational masses \(\mu_t\), with \(\sum_{t\in T}\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
Each type has a continuous, nondecreasing piecewise-linear rule \(F_t:[0,1]\to[0,1]\), specified by rational breakpoints and values, with \(F_t(0)=0\) and \(F_t(1)=1\). The initial fraction is rational \(q_0\in[0,1]\).
For each integer \(N\ge2\) with \(N\mu_t\in\mathbb Z\) for every type and \(Nq_0\in\mathbb Z\), there are \(N\mu_t\) agents of fixed type \(t\). Initially \(Nq_0\) agents say yes.
At each synchronous step, conditional on the current yes count \(k\), all agents draw fresh independent opinions; a type-\(t\) agent says yes with probability \(F_t(k/N)\), including her own opinion in the count.
Let \(\alpha_N\) be the probability of ever reaching \(N\) yes opinions. Other closed classes are allowed; reaching one that excludes unanimous yes contributes zero.
Let \(m\) be the total number of linear pieces and \(L\) the total binary input length, including a comparison threshold \(r\in[0,1]\cap\mathbb Q\). State running times in \(m,\tau,L\).
Does \(\alpha=\lim_{N\to\infty}\alpha_N\) always exist along admissible population sizes, and, whenever it exists, what is its exact value?
Is deciding whether this limit exists and satisfies \(\alpha\ge r\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For finite anonymous societies, absorption probabilities are computable using a count chain with \(N+1\) states, yielding polynomial-time computation in explicitly represented population size and rational input length ([finite result](https://ageconsearch.umn.edu/record/151381/files/NDL2013-051.pdf)).
A related frequency-dependent Wright–Fisher model has exact large-population fixation limits for a fixed initial number of advantageous individuals under strict dominance; it does not cover arbitrary fixed heterogeneous piecewise-linear rules ([related result](https://people.tamu.edu/~roiterst/papers/JMB_2017r.pdf)). No result settling the stated general limit or its decision complexity was located.
I do not settle universal existence of the limit or the complexity of the general decision problem.
I establish two additional classes beyond the verified results in NOTES:
All ingredients taken from NOTES are proved below. The unresolved points are stated at the end.
Let $K_n$ be the number of yes opinions after step $n$, and write $X_n=K_n/N$. Define
$$
G(x)=\sum_{t\in T}\mu_tF_t(x),
\qquad
V(x)=\sum_{t\in T}\mu_tF_t(x)\bigl(1-F_t(x)\bigr).
$$
Both functions are continuous. The function $G$ is nondecreasing and piecewise linear.
Conditional on $X_n=x$, the next count is
$$
K_{n+1}=\sum_{t\in T}B_t,
\qquad
B_t\sim\operatorname{Bin}\bigl(N\mu_t,F_t(x)\bigr),
$$
with independent summands. Hence
$$
\mathbb E[X_{n+1}\mid X_n=x]=G(x),
\qquad
\operatorname{Var}(X_{n+1}\mid X_n=x)=\frac{V(x)}{N}.
$$
Let $h_N(x)$ denote the probability of ever reaching $1$, starting from a lattice state $x\in\{0,1/N,\ldots,1\}$. Thus $\alpha_N=h_N(q_0)$.
The endpoints are absorbing, so
$$
h_N(0)=0,\qquad h_N(1)=1.
$$
In particular, the initial conditions $q_0=0$ and $q_0=1$ are completely resolved. Below, the interesting initial fractions are interior.
Admissible population sizes are infinite in number: multiples of a common denominator of the masses and $q_0$ are admissible.
For every admissible $N$, the function $h_N$ is nondecreasing on the lattice.
To prove this, couple two chains starting at $x\le y$. For each agent at each step, use the same independent uniform random variable in both chains. Because every $F_t$ is nondecreasing, an agent who says yes in the lower chain also says yes in the upper chain. Thus the ordering of the counts persists at every step.
If the lower chain reaches $1$, the upper chain is also at $1$ at that step. Therefore
$$
x\le y\quad\Longrightarrow\quad h_N(x)\le h_N(y).
$$
The Markov property also gives
$$
h_N(x)=\mathbb E_x[h_N(X_1)].
$$
Consequently, $h_N(X_n)$ is a bounded martingale. For every almost surely finite stopping time $S$, bounded convergence applied to $S\wedge n$ gives
$$
h_N(x)=\mathbb E_x[h_N(X_S)].
$$
This identity does not require endpoint absorption to occur almost surely.
For a Bernoulli random variable $B$, the logarithm of its centered moment-generating function has second derivative at most $1/4$: that derivative is a Bernoulli variance under exponential tilting. Its value and first derivative at zero are both zero. Integrating this bound twice gives
$$
\mathbb E[e^{s(B-\mathbb EB)}]\le e^{s^2/8}
\qquad(s\in\mathbb R).
$$
Independence of the $N$ opinions therefore yields
$$
\mathbb E\!\left[e^{s(X_{n+1}-G(x))}\mid X_n=x\right]
\le e^{s^2/(8N)}.
$$
Applying Markov's inequality with $s=4N\eta$, and then with $s=-4N\eta$, proves
$$
\mathbb P\!\left(X_{n+1}-G(x)\ge\eta\mid X_n=x\right)
\le e^{-2N\eta^2},
$$
$$
\mathbb P\!\left(X_{n+1}-G(x)\le-\eta\mid X_n=x\right)
\le e^{-2N\eta^2}.
$$
Because every mass is positive,
$$
V(c)=0
\quad\Longleftrightarrow\quad
F_t(c)\in\{0,1\}\text{ for every }t.
$$
If also $G(c)=c$, then
$$
c=\sum_{\{t:F_t(c)=1\}}\mu_t.
$$
Thus $Nc$ is integral for every admissible population size, and the next fraction from $c$ is deterministically $c$.
Such a point is also a barrier. If $x\le c$, the types with $F_t(c)=0$ necessarily say no at $x$, so the next fraction is at most $c$. If $x\ge c$, the types with $F_t(c)=1$ necessarily say yes at $x$, so the next fraction is at least $c$.
In particular, an interior deterministic fixed point excludes fixation at $1$ from every initial fraction at or below it.
The following lemma will connect the local calculations to eventual fixation.
Lemma 1. Let $c\in[0,1]$.
$$ h_N(x_N)\longrightarrow1. $$
$$ h_N(x_N)\longrightarrow0. $$
All limits are along admissible population sizes.
Proof. Consider positive drift. Choose
$$
c<a<q<b<1.
$$
On the compact interval $[a,b]$, there are constants $\delta,\varepsilon>0$ such that
$$
G(x)-x\ge\delta,
\qquad
G(x)\ge(1+\varepsilon)x.
$$
Choose $\theta>0$ sufficiently small that
$$
(1-e^{-\theta})(1+\varepsilon)\ge\theta.
$$
This is possible because $(1-e^{-\theta})/\theta\to1$ as $\theta\downarrow0$.
Independence and $1-u\le e^{-u}$ imply
$$
\begin{aligned}
\mathbb E[e^{-\theta K_{n+1}}\mid X_n=x]
&=\prod_t\left[1-F_t(x)(1-e^{-\theta})\right]^{N\mu_t}\\
&\le e^{-N(1-e^{-\theta})G(x)}
\le e^{-\theta Nx}
\end{aligned}
$$
for $x\in[a,b]$.
For sufficiently large $N$, start at $x_N\in(a,b)$ and let $T$ be the first exit from $(a,b)$. The stopped exponential process is a supermartingale. Moreover,
$$
\mathbb E[X_{n\wedge T}]
\ge x_N+\delta\,\mathbb E[n\wedge T].
$$
The left side is at most $1$, so $T$ has finite expectation. Since the stopped exponential process is bounded for fixed $N$, stopping gives
$$
\mathbb P_{x_N}(X_T\le a)
\le e^{-\theta N(x_N-a)}.
$$
Next start from any lattice state $y\ge b$, and stop at the first state at most $a$, or at $1$. Every intervening lattice state has strictly positive drift. Its finite minimum proves, by the same stopped-expectation argument, that this stopping time has finite expectation.
If $p$ is the probability of reaching $1$ at this stopping time, the stopped submartingale gives
$$
y\le \mathbb E[X_{\mathrm{stop}}]\le a(1-p)+p.
$$
Therefore
$$
h_N(y)\ge p\ge\frac{b-a}{1-a}.
$$
Combining the two stopping arguments,
$$
h_N(x_N)\ge
\left(1-e^{-\theta N(x_N-a)}\right)\frac{b-a}{1-a}.
$$
For each fixed $b$, take the lower limit in $N$. Then let $b\uparrow1$, keeping $a$ fixed. This proves convergence to $1$.
For negative drift, replace each rule by
$$
\widetilde F_t(x)=1-F_t(1-x).
$$
The complemented process has aggregate mean
$$
\widetilde G(x)=1-G(1-x)>x
\qquad(1-c<x<1).
$$
The positive-drift result shows that the original process reaches $0$ with probability tending to $1$. The absorbing endpoint events are mutually exclusive, so its probability of reaching $1$ tends to zero. $\square$
Theorem 2. Suppose there are rational numbers $0<a<b<1$ such that
$$
G(x)<x\quad(0<x<a),
$$
$$
G(x)=x\quad(a\le x\le b),
$$
$$
G(x)>x\quad(b<x<1),
$$
and
$$
V(x)>0\quad(a\le x\le b).
$$
Then the limit exists for every rational initial fraction and equals
$$
\alpha=
\begin{cases}
0,&0\le q_0\le a,\\[2mm]
\dfrac{q_0-a}{b-a},&a<q_0<b,\\[3mm]
1,&b\le q_0\le1.
\end{cases}
$$
The positive-variance assumption excludes deterministic barriers within the fixed interval.
Fix $q=q_0\in[a,b)$. Choose $\ell\in(0,a)$ sufficiently close to $a$ that $G(\ell)>0$. Let $T$ be the first exit from $(\ell,b)$.
For $x\in[\ell,b]$, we have $G(x)\le x$. With $f(x)=(b-x)^2$,
$$
\begin{aligned}
\mathbb E[f(X_{n+1})-f(x)\mid X_n=x]
&=2(b-x)(x-G(x))+(x-G(x))^2+\frac{V(x)}N\\
&\ge \frac{(x-G(x))^2+V(x)}N.
\end{aligned}
$$
The continuous function
$$
H(x)=(x-G(x))^2+V(x)
$$
is strictly positive throughout $[\ell,b]$: below $a$ the first term is positive, and on $[a,b]$ the second term is positive. Hence
$$
h_*=\min_{x\in[\ell,b]}H(x)>0.
$$
Stopping the displayed increment inequality and using $0\le f\le1$ gives
$$
\mathbb E[T]\le \frac N{h_*}.
$$
Fix $0<\eta<G(\ell)$. Before exit, monotonicity gives $G(X_n)\ge G(\ell)$. The concentration bound and a union bound over the expected number of steps imply
$$
\mathbb P\bigl(X_T<G(\ell)-\eta\bigr)
\le \mathbb E[T]e^{-2N\eta^2}
\le \frac N{h_*}e^{-2N\eta^2}.
$$
Write the last bound as $\varepsilon_N$, so $\varepsilon_N\to0$.
Let
$$
p_N=\mathbb P(X_T\ge b).
$$
The stopped fraction process is a supermartingale, so $\mathbb E[X_T]\le q$. On upper exit, $X_T\ge b$. Except on an event of probability at most $\varepsilon_N$, a lower exit satisfies $X_T\ge G(\ell)-\eta$. Consequently,
$$
q\ge p_Nb+(1-p_N)(G(\ell)-\eta)-\varepsilon_N,
$$
and therefore
$$
p_N\le
\frac{q-G(\ell)+\eta+\varepsilon_N}{b-G(\ell)+\eta}.
$$
On lower exit, monotonicity of $h_N$ bounds the remaining fixation probability by
$$
h_N\!\left(\frac{\lfloor N\ell\rfloor}{N}\right),
$$
which tends to zero by Lemma 1. On upper exit it is at most $1$. Thus
$$
\limsup_N h_N(q)
\le
\frac{q-G(\ell)+\eta}{b-G(\ell)+\eta}.
$$
First let $\eta\downarrow0$, and then let $\ell\uparrow a$. Continuity gives $G(\ell)\to a$, proving
$$
\limsup_N h_N(q)\le\frac{q-a}{b-a}.
$$
This includes the boundary conclusion $h_N(a)\to0$.
Fix $q\in(a,b]$, choose $u\in(b,1)$, and stop at the first exit $S$ from $(a,u)$.
Here $G(x)\ge x$. For $f(x)=(x-a)^2$,
$$
\mathbb E[f(X_{n+1})-f(x)\mid X_n=x]
=
2(x-a)(G(x)-x)+(G(x)-x)^2+\frac{V(x)}N.
$$
As before, $(G(x)-x)^2+V(x)$ is strictly positive on $[a,u]$. Hence $\mathbb E[S]\le C_uN$ for a constant independent of $N$.
Because $G(X_n)\le G(u)$ before exit, concentration implies
$$
\mathbb P(X_S>G(u)+\eta)\le C_uN e^{-2N\eta^2}=o(1)
$$
for each fixed $\eta>0$.
Let $p_N=\mathbb P(X_S\ge u)$. The stopped fraction process is a submartingale. The lower exit is at most $a$, while the upper exit is at most $G(u)+\eta$ except on the exceptional event. Therefore
$$
q\le \mathbb E[X_S]
\le a(1-p_N)+(G(u)+\eta)p_N+o(1),
$$
so
$$
\liminf_Np_N\ge\frac{q-a}{G(u)+\eta-a}.
$$
On upper exit, the remaining fixation probability is at least
$$
h_N\!\left(\frac{\lceil Nu\rceil}{N}\right)\longrightarrow1
$$
by Lemma 1. Hence, letting $\eta\downarrow0$ and then $u\downarrow b$,
$$
\liminf_Nh_N(q)\ge\frac{q-a}{b-a}.
$$
This includes $h_N(b)\to1$.
Together with the upper bound and Lemma 1 outside $[a,b]$, this proves Theorem 2.
Suppose $c\in(0,1)$ satisfies
$$
G(c)=c,
$$
$$
G(x)<x\quad(0<x<c),
\qquad
G(x)>x\quad(c<x<1).
$$
Because $G$ is piecewise linear, it has one-sided affine representations near $c$:
$$
G(c+z)=
\begin{cases}
c+\lambda_-z,&-\delta\le z\le0,\\
c+\lambda_+z,&0\le z\le\delta
\end{cases}
$$
for some $\delta>0$.
Both slopes satisfy
$$
\lambda_->1,\qquad \lambda_+>1.
$$
Indeed, on the left the difference $G(c+z)-(c+z)=(\lambda_--1)z$ must be negative, while on the right the analogous difference must be positive.
Theorem 3. Under these hypotheses:
$$
\alpha=p(\lambda_-,\lambda_+),
$$
where $p$ is defined by the Gaussian recursion below.
Moreover,
$$
0<p(\lambda_-,\lambda_+)<1,
$$
and
$$
p(\lambda_-,\lambda_+)=
\begin{cases}
\dfrac12,&\lambda_-=\lambda_+,\\[2mm]
>\dfrac12,&\lambda_+>\lambda_-,\\[2mm]
<\dfrac12,&\lambda_+<\lambda_-.
\end{cases}
$$
The first two conclusions follow from Lemma 1, including the absorbing endpoint initial conditions. The third follows from Section 1.3. The rest of this section proves the fourth conclusion and the assertions about $p$.
Define
$$
H(y)=
\begin{cases}
\lambda_-y,&y\le0,\\
\lambda_+y,&y\ge0.
\end{cases}
$$
Let $Z_1,Z_2,\ldots$ be independent standard normal variables, and define
$$
Y_0=y,\qquad Y_{n+1}=H(Y_n)+Z_{n+1}.
$$
Write
$$
d=\min(\lambda_--1,\lambda_+-1)>0.
$$
We first prove that, from every initial $y$, this recursion almost surely tends either to $+\infty$ or to $-\infty$.
Fix $M>0$. At a state $y>M$, set $\theta=dM$. Since the active slope is $\lambda_+$,
$$
\begin{aligned}
\mathbb E[e^{-\theta Y_{n+1}}\mid Y_n=y]
&=e^{-\theta\lambda_+y+\theta^2/2}\\
&\le e^{-\theta y}.
\end{aligned}
$$
The last inequality follows from
$$
\frac{\theta^2}{2}\le\theta(\lambda_+-1)y.
$$
Stopping at the first state at most $M$, and first stopping also at a deterministic time $n$, gives
$$
\mathbb P_y(\text{ever reach a state at most }M)
\le e^{-dM(y-M)}
\qquad(y>M).
$$
Only finite-time supermartingale inequalities are needed; letting $n\to\infty$ uses monotonicity of the hitting events. Reflection gives
$$
\mathbb P_y(\text{ever reach a state at least }-M)
\le e^{-dM(|y|-M)}
\qquad(y<-M).
$$
For any $R>|y|$, let $\tau_R$ be the first time $|Y_n|\ge R$. This time is almost surely finite. In fact, while $|Y_n|<R$, the probability of leaving $[-R,R]$ on the next step is at least
$$
\mathbb P\!\left(Z_1\ge R+\max(\lambda_-,\lambda_+)R\right)>0.
$$
Thus the probability of remaining inside for $n$ steps decreases geometrically.
For $R>M$, apply the preceding return bounds at $\tau_R$. With probability at least
$$
1-e^{-dM(R-M)},
$$
all subsequent states remain on the exit side and have magnitude greater than $M$. Therefore
$$
\mathbb P_y\bigl(\text{not eventually confined to one side beyond }M\bigr)
\le e^{-dM(R-M)}.
$$
Letting $R\to\infty$ makes this probability zero. Applying the conclusion for all positive integers $M$, and observing that their eventual sides must agree, proves
$$
Y_n\longrightarrow+\infty
\quad\text{or}\quad
Y_n\longrightarrow-\infty
\qquad\text{almost surely}.
$$
Define
$$
w(y)=\mathbb P_y(Y_n\to+\infty),
\qquad
p(\lambda_-,\lambda_+)=w(0).
$$
The return bounds show that
$$
\lim_{y\to-\infty}w(y)=0,
\qquad
\lim_{y\to+\infty}w(y)=1.
$$
This gives a population-independent exact characterization. With
$$
\varphi(z)=\frac{e^{-z^2/2}}{\sqrt{2\pi}},
$$
the function $w$ satisfies
$$
w(y)=\int_{\mathbb R}w(H(y)+z)\varphi(z)\,dz.
$$
It is the unique bounded measurable function satisfying this equation and the two boundary limits. Indeed, if $u$ is another such function, iteration gives
$$
u(y)=\mathbb E_y[u(Y_n)].
$$
The almost sure escape result and bounded convergence imply $u(y)=w(y)$.
Thus the characterization is not merely another population-size limit: it is a fixed one-dimensional Gaussian integral equation depending only on two slopes.
Assume now $V(c)>0$, and set
$$
\sigma=\sqrt{V(c)}.
$$
For the society started at $c$, define the scaled fractions
$$
Y_n^{(N)}=\frac{\sqrt N}{\sigma}(X_n-c).
$$
For every fixed $n$,
$$
Y_n^{(N)}\ \Longrightarrow\ Y_n,
$$
where the limiting Gaussian recursion starts at $Y_0=0$.
Here are the details of the transition limit. For lattice states $x_N$ satisfying
$$
\frac{\sqrt N}{\sigma}(x_N-c)\longrightarrow y,
$$
the local affine formulas give
$$
\frac{\sqrt N}{\sigma}(G(x_N)-c)\longrightarrow H(y).
$$
For the centered innovation
$$
W_N=\frac{\sqrt N}{\sigma}(X_{n+1}-G(x_N)),
$$
Taylor expansion of the logarithms of the independent centered Bernoulli characteristic functions gives, for fixed real $t$,
$$
\log\mathbb E[e^{itW_N}\mid X_n=x_N]
=
-\frac{t^2V(x_N)}{2\sigma^2}+O(N^{-1/2}).
$$
The remainder is uniform in $x_N$: each centered Bernoulli contribution is bounded in absolute value by $1/(\sigma\sqrt N)$, so the sum of the third-order remainder bounds is $O(N^{-1/2})$.
Continuity gives $V(x_N)\to\sigma^2$. Thus the characteristic functions tend to $e^{-t^2/2}$, the characteristic function of a standard normal variable. The continuity theorem for characteristic functions applies because this limiting characteristic function is continuous at zero.
The same argument is uniform when the scaled starting state ranges over a compact set. Since $H$ is continuous, the resulting convergence of transition kernels, together with tightness, proves the fixed-time assertion by induction. More explicitly, for any bounded continuous test function, conditional expectations converge uniformly on compact sets of scaled starting states; outside such sets, tightness bounds the remaining contribution. This supplies the induction step from time $n$ to time $n+1$.
Finite-time convergence alone is insufficient for fixation. The next estimate supplies the missing infinite-horizon control.
Write
$$
d_+=\lambda_+-1,\qquad d_-=\lambda_--1.
$$
Fix $R>0$. Consider a lattice state with scaled coordinate
$$
y=\frac{\sqrt N}{\sigma}(x-c)\ge R
$$
and $x<c+\delta$. For sufficiently large $N$, stop when either
$$
\frac{\sqrt N}{\sigma}(X_n-c)\le\frac R2
\quad\text{or}\quad
X_n\ge c+\delta.
$$
At every state before stopping, the mean of the next scaled state is $\lambda_+y$. The centered moment-generating estimate from Section 1.2 gives
$$
\mathbb E\!\left[
e^{-\theta(Y_{n+1}^{(N)}-\lambda_+y)}
\mid Y_n^{(N)}=y
\right]
\le e^{\theta^2/(8\sigma^2)}.
$$
Choose
$$
\theta=4\sigma^2d_+R.
$$
For $y>R/2$,
$$
\frac{\theta^2}{8\sigma^2}\le\theta d_+y.
$$
Therefore $e^{-\theta Y_n^{(N)}}$, stopped as specified, is a supermartingale.
The stopping time has finite expectation. Before stopping,
$$
G(X_n)-X_n
=d_+(X_n-c)>
\frac{d_+\sigma R}{2\sqrt N},
$$
so the stopped first-moment argument used in Lemma 1 applies.
At a lower exit, the stopped exponential is at least $e^{-\theta R/2}$. Its initial value is at most $e^{-\theta R}$. Hence
$$
\mathbb P_x\!\left(\text{lower exit before reaching }c+\delta\right)
\le e^{-2\sigma^2d_+R^2}.
$$
On upper exit, monotonicity bounds the remaining fixation probability below by
$$
b_N=h_N\!\left(\frac{\lceil N(c+\delta)\rceil}{N}\right)\longrightarrow1,
$$
where the limit follows from Lemma 1. States already at least $c+\delta$ satisfy the same lower bound directly.
Reflection supplies the corresponding left-side bound, with
$$
a_N=h_N\!\left(\frac{\lfloor N(c-\delta)\rfloor}{N}\right)\longrightarrow0.
$$
Consequently, for
$$
\kappa=2\sigma^2\min(d_+,d_-)>0,
$$
we have, for all sufficiently large $N$,
$$
h_N(x)\ge(1-e^{-\kappa R^2})b_N
\quad\text{if}\quad
\frac{\sqrt N}{\sigma}(x-c)\ge R,
$$
and
$$
h_N(x)\le a_N+(1-a_N)e^{-\kappa R^2}
\quad\text{if}\quad
\frac{\sqrt N}{\sigma}(x-c)\le-R.
$$
For each fixed $n\ge1$,
$$
h_N(c)=\mathbb E_c[h_N(X_n)].
$$
Use the escape estimates on the events $Y_n^{(N)}\ge R$ and $Y_n^{(N)}\le-R$.
The limiting variable $Y_n$ has no atoms, because its last innovation is an independent Gaussian. Fixed-time convergence therefore gives
$$
\liminf_Nh_N(c)
\ge(1-e^{-\kappa R^2})\mathbb P(Y_n\ge R),
$$
$$
\limsup_Nh_N(c)
\le1-(1-e^{-\kappa R^2})\mathbb P(Y_n\le-R).
$$
The Gaussian escape result implies
$$
\mathbb P(Y_n\ge R)\longrightarrow p,
\qquad
\mathbb P(Y_n\le-R)\longrightarrow1-p
$$
as $n\to\infty$. Hence
$$
(1-e^{-\kappa R^2})p
\le\liminf_Nh_N(c)
\le\limsup_Nh_N(c)
\le p+e^{-\kappa R^2}(1-p).
$$
Letting $R\to\infty$ proves
$$
h_N(c)\longrightarrow p(\lambda_-,\lambda_+).
$$
First, $0<p<1$. A sufficiently large positive first Gaussian innovation has positive probability, and the return estimate gives a positive conditional probability of never returning below $1$. Almost sure escape then forces positive escape. A sufficiently negative first innovation similarly gives negative escape with positive probability.
If $\lambda_-=\lambda_+=\lambda>1$, the recursion is linear:
$$
\frac{Y_n}{\lambda^n}
=\sum_{j=1}^n\lambda^{-j}Z_j.
$$
The series converges almost surely: its independent centered terms have summable variances. Its limit is a centered Gaussian variable with variance
$$
\sum_{j=1}^{\infty}\lambda^{-2j}
=\frac1{\lambda^2-1}.
$$
It is nonzero almost surely, and its sign determines the escape direction. Therefore
$$
p(\lambda,\lambda)=\frac12.
$$
Now suppose $\lambda_+>\lambda_-=\lambda$. Couple $Y_n$ to
$$
S_0=0,\qquad S_{n+1}=\lambda S_n+Z_{n+1}
$$
using the same innovations. Since $H(y)\ge\lambda y$ for every $y$, induction gives $Y_n\ge S_n$. Thus $p\ge1/2$.
For strictness, write
$$
W_n=\sum_{j=1}^n\lambda^{-j}Z_j,
\qquad
W=\lim_nW_n.
$$
Expanding the nonlinear recursion gives
$$
\frac{Y_n}{\lambda^n}
=
W_n+
\sum_{j=1}^n
\frac{(\lambda_+-\lambda)(Y_{j-1})_+}{\lambda^j}.
$$
For $n\ge2$, this is at least $W_n+D$, where
$$
D=\frac{(\lambda_+-\lambda)(Z_1)_+}{\lambda^2}.
$$
Conditional on $Z_1=z>0$, the variable $W$ is Gaussian with positive variance and full support on $\mathbb R$. Therefore
$$
\mathbb P(Z_1>0,\ -D<W<0)>0.
$$
On this event, $S_n\to-\infty$, but $W+D>0$ forces $Y_n\to+\infty$. This supplies positive probability of positive escape in addition to the event $W>0$, proving
$$
p(\lambda_-,\lambda_+)>\frac12.
$$
Reflection swaps the two slopes and the two escape directions. It proves the strict reverse inequality when $\lambda_+<\lambda_-$.
This completes Theorem 3.
Take one type of mass $1$ and let its rule interpolate
$$
(0,0),\quad
\left(\frac14,\frac18\right),\quad
\left(\frac12,\frac12\right),\quad
\left(\frac34,\frac{15}{16}\right),\quad
(1,1).
$$
The four slopes are
$$
\frac12,\quad\frac32,\quad\frac74,\quad\frac14.
$$
Direct evaluation on the four pieces gives
$$
F(x)<x\quad(0<x<1/2),
\qquad
F(x)>x\quad(1/2<x<1).
$$
At $c=1/2$,
$$
V(c)=\frac14,\qquad
\lambda_-=\frac32,\qquad
\lambda_+=\frac74.
$$
Therefore, from $q_0=1/2$,
$$
\alpha=p\!\left(\frac32,\frac74\right),
\qquad
\frac12<\alpha<1.
$$
Thus a nonabsorbing repelling fixed initial fraction need not have limiting fixation probability $1/2$.
The variance hypothesis also matters. Keep this aggregate $G=F$, but use two types of mass $1/2$ with rules
$$
F_1(x)=\min(2F(x),1),
\qquad
F_2(x)=\max(2F(x)-1,0).
$$
These are admissible continuous nondecreasing rational piecewise-linear rules, and
$$
\frac{F_1(x)+F_2(x)}2=F(x).
$$
At $x=1/2$, their probabilities are respectively $1$ and $0$. The fraction $1/2$ is therefore absorbing, and
$$
\alpha_N=0
$$
for every admissible $N$. The same aggregate mean and initial fraction can consequently give different limits.
These results provide polynomial-time decision procedures for additional restricted classes, not for the full problem.
Form the common partition of all supplied breakpoints. It has $O(m)$ intervals, and $G(x)-x$ is affine on each interval. Exact rational calculations determine its zeros, signs, and identity intervals.
For Theorem 2, positivity of $V$ on the fixed interval can also be checked finitely. If $V(c)=0$ at an interior point of a common affine piece, every affine rule takes the value $0$ or $1$ there. An affine function bounded in $[0,1]$ cannot attain either endpoint at an interior point unless it is constant. Thus all rules would be locally constant, contradicting $G(x)=x$. Therefore any zero of $V$ in $[a,b]$ must be at a common breakpoint or at $a$ or $b$. Checking those candidates suffices.
For Theorem 3, the one-sided slopes and $V(c)$ are exactly computable. In particular:
A conservative implementation uses
$$
O\bigl(m\tau+m\log(m+1)\bigr)
$$
rational operations. Sorting the common breakpoints and evaluating each active affine rule achieves this bound.
Computing each aggregate independently keeps intermediate rational numerators and denominators to $O(L^2)$ bits: each evaluation uses input rationals and a rational partition point or affine root, and a sum involves at most $\tau\le L$ terms. With elementary arithmetic and fraction reduction, a conservative bit-time bound is
$$
O\!\left(\bigl(m\tau+m\log(m+1)\bigr)L^6\right).
$$
This bound covers recognition and the rational comparisons just listed.
The Gaussian integral characterization does not establish polynomial-time comparison of $p(\lambda_-,\lambda_+)$ with an arbitrary rational threshold.
The arguments above do not cover arbitrary nonsymmetric attracting fixed points, multiple attracting regions, or all configurations of fixed intervals and deterministic barriers. They therefore do not establish universal convergence.
They also provide neither a general polynomial-time algorithm nor an $\mathrm{NP}$-hardness reduction. In particular, a complete complexity classification must address eventual escape from attracting regions and exact threshold comparisons that are not resolved by rational formulas or symmetry.
⟨structured verdict parsed — rendered above⟩
The output establishes correct partial results, but does not resolve the general task. I found no mathematical error or substantive gap in the proofs of the stated restricted cases. Universal existence, general exact values, and the general decision complexity remain unresolved, as the prover acknowledges.
The conditional distribution correctly accounts for fixed heterogeneous types and fresh independent opinions. The formulas
$$
\mathbb E[X_{n+1}\mid X_n=x]=G(x),
\qquad
\operatorname{Var}(X_{n+1}\mid X_n=x)=\frac{V(x)}N
$$
have the correct normalization.
The uniform-variable coupling preserves the ordering of both agents’ opinions and total counts, establishing monotonicity of $h_N$. The harmonic identity for $h_N$ follows from the Markov property even when additional closed classes exist.
The stopping identity is justified: $h_N(X_{S\wedge n})$ is bounded, and an almost surely finite $S$ permits bounded convergence. No unjustified assumption of eventual endpoint absorption enters this argument.
Admissible population sizes are indeed unbounded, because common-denominator multiples satisfy all integrality requirements.
The centered Bernoulli moment-generating bound has the correct constant. For the fraction of $N$ independent opinions, it becomes
$$
\mathbb E[e^{s(X_{n+1}-G(x))}\mid X_n=x]
\le e^{s^2/(8N)}.
$$
Optimizing with $s=4N\eta$ gives the stated exponent $-2N\eta^2$.
Because every support mass is positive, $V(c)=0$ forces every $F_t(c)$ to be either $0$ or $1$. When additionally $G(c)=c$, the identity expressing $c$ as a sum of type masses ensures that $Nc$ is integral for every admissible population size.
Both barrier assertions follow from monotonicity of the individual rules. In particular, a chain started at or below an interior deterministic fixed point cannot reach $1$. This correctly handles a class of additional closed states allowed by the task.
On the compact interval $[a,b]$, strict positive drift supplies both a positive additive drift minimum and the required multiplicative bound. The choice of $\theta$ is valid for sufficiently small positive $\theta$.
The stopped first-moment inequality establishes finite expected exit time before optional stopping is used. The resulting lower-exit bound
$$
\mathbb P_{x_N}(X_T\le a)
\le e^{-\theta N(x_N-a)}
$$
follows with the stated exponent.
For the second stopping argument, every intervening state has strictly positive drift. For each fixed population size, the finite state space therefore supplies a positive drift minimum, making that stopping time integrable. The estimate
$$
h_N(y)\ge\frac{b-a}{1-a}
$$
is correctly derived from the stopped submartingale.
Taking the population-size limit before sending $b$ to $1$ is legitimate. The reflected argument proves convergence of the probability of reaching $0$ to $1$, which suffices for the negative-drift conclusion without assuming that endpoint absorption is otherwise certain.
Both quadratic increment identities are correct. Their signs depend on the respective stopping intervals, where $G(x)\le x$ or $G(x)\ge x$ holds as required.
The function
$$
(x-G(x))^2+V(x)
$$
is strictly positive on each relevant compact interval. Below or above the identity interval, the drift term is positive; within it, the variance hypothesis supplies positivity. This justifies the expected exit-time bounds of order $N$.
The overshoot bounds correctly combine conditional concentration with the expected number of transitions before exit. They therefore remain valid despite the random stopping times.
The stopped first-moment estimates give the stated bounds on upper-exit probabilities. Monotonicity of $h_N$ and Lemma 1 correctly control fixation after the lower and upper exits, respectively. The floor and ceiling choices are in the correct directions.
The successive limits in the auxiliary parameters yield matching bounds. In particular, the proof covers $q_0=a$ and $q_0=b$, rather than silently treating only the interior:
$$
\alpha(a)=0,\qquad \alpha(b)=1.
$$
The endpoint initial conditions are separately handled. Thus the full piecewise formula is established under the theorem’s hypotheses.
The strict drift hypotheses and local affine representations imply $\lambda_->1$ and $\lambda_+>1$, with the signs handled correctly on both sides.
The Gaussian exponential estimates have valid constants. Finite-time stopping is sufficient for the return-probability bounds; the proof does not require an unproved integrability assertion for an infinite hitting time.
Exit from any bounded interval is almost surely finite because the next-step exit probability has a uniform positive lower bound there. Applying the return bounds after that exit establishes eventual confinement beyond each fixed magnitude. The countable argument over positive integer magnitudes correctly yields almost sure escape to one of the two infinities.
The boundary limits for $w$ follow from the return estimates. The integral equation follows from the Markov property, and uniqueness among bounded measurable solutions with those boundary limits follows by iteration and bounded convergence.
Consequently, this is an exact characterization of the restricted-case value. It does not, by itself, provide an algorithm for exact comparison with an arbitrary rational threshold.
The characteristic-function expansion has the correct variance term:
$$
-\frac{t^2V(x_N)}{2\sigma^2}.
$$
The sum of the third-order remainders is of order $N^{-1/2}$ for fixed $t$, because the individual centered contributions are uniformly bounded at scale $N^{-1/2}$. Continuity of $V$ gives the standard normal transition limit.
The compact-uniform transition convergence and induction justify convergence at every fixed time. The limiting map $H$ is continuous, including at its kink.
Crucially, the proof supplies additional control beyond this finite-time convergence. In Section 4.3, the choice
$$
\theta=4\sigma^2d_+R
$$
satisfies the required supermartingale inequality whenever the scaled state exceeds $R/2$. The resulting lower-exit probability bound has the correct exponent:
$$
e^{-2\sigma^2d_+R^2}.
$$
Finite expected stopping time is independently justified by positive drift. Reflection supplies the corresponding left-side estimate.
The order of limits in Section 4.4 is valid: first population size, then fixed-time horizon, then scaled distance. Gaussian innovations ensure that the fixed-time limiting distributions have no atoms at the comparison boundaries. These estimates establish the claimed fixation limit at $q_0=c$.
With equal slopes, the normalized Gaussian series has summable variances and converges almost surely. Its variance is correctly computed as
$$
\frac1{\lambda^2-1}.
$$
Its almost surely nonzero sign determines the escape direction, giving probability $1/2$.
For unequal slopes, the pathwise comparison with the linear recursion is valid because $H$ is nondecreasing and dominates the corresponding linear map. The nonlinear expansion has the correct indexing, and its second-step contribution is exactly
$$
D=\frac{(\lambda_+-\lambda)(Z_1)_+}{\lambda^2}.
$$
Conditional on a positive first innovation, the remaining Gaussian series has positive variance and full support. The event used to prove strict bias therefore has positive probability, and the normalized lower bound forces positive escape on that event. Reflection correctly gives the reverse inequality.
The four slopes in the concrete example are correct, as are the drift signs and variance at $c=1/2$. The two-type construction preserves the aggregate mean while making that initial fraction deterministic. It validly demonstrates that the aggregate mean alone does not determine fixation limits.
A common partition has order $m$ intervals. On each interval, affine rational calculations suffice to determine the signs, zeros, and identity portions of $G(x)-x$.
The proposed variance check is sufficient: a nonconstant affine rule bounded in $[0,1]$ cannot attain $0$ or $1$ at an interior point of an affine piece. Thus an interior variance zero within an identity portion would force all rules locally constant, contradicting $G(x)=x$.
The rational-operation bound
$$
O\bigl(m\tau+m\log(m+1)\bigr)
$$
is consistent with sorting and evaluating the active rules. The stated bit-time bound is conservative for reduced rational arithmetic with the claimed intermediate bit lengths.
These bounds cover recognition and the rational comparisons explicitly listed. They do not cover arbitrary-threshold comparison for the asymmetric Gaussian value; the output expressly acknowledges this limitation.
The output provides genuine exact-limit results for two globally specified configurations, together with valid restricted decision procedures. The repeller result requires the stated drift inequalities throughout both sides of $c$; an arbitrary locally repelling fixed point is outside its proved scope.
The general assignment remains open. No expositional clarification is needed to verify the established results. Completing the assignment requires additional mathematics addressing the omitted configurations and a general exact comparison procedure or hardness reduction. Those are substantive missing results, not repairs to the arguments already written.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.