Multi-step concentration of the configuration (Lem. 10, Gast et al. 2023)

Fix a finite type $S$ of states with decidable equality (nothing forces $S$ to be nonempty). Given

• two real $S\times S$ matrices $P_0,P_1$, each assumed to be a transition matrix, meaning every entry satisfies $P_a(x,y)\ge 0$ and every row satisfies $\sum_{y\in S}P_a(x,y)=1$;
• a priority function $\nu:S\to\mathbb R$ assumed injective (distinct states get distinct priority values);
• a real number $\alpha$ with $0<\alpha<1$;

the statement asserts the existence of a real constant $K$ with $K\ge 0$, depending only on the data just listed ($S$, $P_0$, $P_1$, $\nu$, $\alpha$) and on nothing quantified later, such that for every natural number $N$ with $N>0$, for every function $\pi:(\mathrm{Fin}\,N\to S)\to(\mathrm{Fin}\,N\to\mathrm{Bool})\to\mathbb R$ that is an index policy with budget $M_N:=\lfloor\alpha N\rfloor_{\mathbb N}$ (the natural-number floor of $\alpha N$; since $0<\alpha<1$ this is an integer with $0\le M_N\le N-1$, and $M_N=0$ when $N=1$), for every initial joint state $s_0:\mathrm{Fin}\,N\to S$, for every $t\in\mathbb N$ and for every real $\delta>0$, the inequality

$$\sum_{s\in B}\;\mathcal L_t(s)\;\le\;2\,t\,|S|\,e^{-N\delta^2/2}$$

holds, where the ingredients are the following, all spelled out from their definitions.

"$\pi$ is an index policy with budget $M$" means the conjunction of three conditions: (i) $\pi(s,a)\ge 0$ for all joint states $s$ and all action profiles $a:\mathrm{Fin}\,N\to\mathrm{Bool}$, and $\sum_{a}\pi(s,a)=1$ for every $s$ (the sum ranging over all $2^N$ profiles); (ii) for all $s,a$, if $\pi(s,a)\neq 0$ then $a$ activates exactly $M$ agents, i.e. $\#\{i:a_i=\text{true}\}=M$; (iii) for every joint state $s$ and every agent index $i$, the marginal activation probability

$$\sum_{a}\big[\,a_i=\text{true}\,\big]\,\pi(s,a)$$

equals $q_\nu^M(s,s_i)$, where for $x\in S$, writing $n_x(s):=\#\{i: s_i=x\}$ for the number of agents in state $x$ and $H_\nu(s,x):=\sum_{y:\ \nu(x)<\nu(y)} n_y(s)$ for the number of agents in strictly higher-priority states,

$$q_\nu^M(s,x):=\begin{cases}0,& n_x(s)=0,\\[2pt]\dfrac{\min\big(n_x(s),\,M\ominus H_\nu(s,x)\big)}{n_x(s)},&\text{otherwise,}\end{cases}$$

with $\ominus$ denoting truncated natural subtraction (it is $0$ whenever $H_\nu(s,x)\ge M$). Nothing in the statement asserts that such a $\pi$ exists for a given $N$; for any $N$ admitting no such $\pi$ the inner claim is vacuous.

$\mathcal L_t$ is the law of the joint state after $t$ steps started deterministically at $s_0$, defined recursively by $\mathcal L_0(s)=1$ if $s=s_0$ and $0$ otherwise, and $\mathcal L_{t+1}(s')=\sum_{s}\mathcal L_t(s)\,\Pi(s,s')$, where one step is

$$\Pi(s,s')=\sum_{a:\mathrm{Fin}\,N\to\mathrm{Bool}}\pi(s,a)\prod_{j=0}^{N-1}\big(a_j\,?\,P_1(s_j,s'_j):P_0(s_j,s'_j)\big),$$

i.e. the agents draw a joint action profile from $\pi$ and then move independently, agent $j$ using $P_1$ if activated and $P_0$ otherwise.

$B$ is the set of joint states $s:\mathrm{Fin}\,N\to S$ satisfying

$$\Big(\sum_{j=0}^{t}K^{\,j}\Big)\,\delta\;\le\;\big\|\,\mathrm{cfg}(s)-\varphi^{t}\big(\mathrm{cfg}(s_0)\big)\,\big\|_\infty ,$$

a non-strict inequality with the geometric factor on the left, the sum running over $j=0,1,\dots,t$ (so it has $t+1$ terms and equals $1$ when $K=0$, since $0^0=1$). Here:

• $\mathrm{cfg}(s)(x)=n_x(s)/N$ is the empirical configuration (real division; $N>0$ is assumed);
• $\|v\|_\infty=\sup_{x\in S}|v(x)|$, a real supremum, which is $0$ when $S$ is empty;
• $\varphi=\Phi_{P_0,P_1,\nu,\beta}$ with activation fraction $\beta:=M_N/N=\lfloor\alpha N\rfloor_{\mathbb N}/N$ — the rounded fraction, not $\alpha$ itself — and $\varphi^t$ is the $t$-fold composite ($\varphi^0$ being the identity, so at $t=0$ the comparison point is $\mathrm{cfg}(s_0)$ itself). The map $\Phi$ acts on an arbitrary function $m:S\to\mathbb R$ (no constraint that $m$ be a probability vector is imposed by the definition) by

$$\Phi(m)(y)=\sum_{x\in S}\Big[\big(m(x)-f(m,x)\big)P_0(x,y)+f(m,x)\,P_1(x,y)\Big],\qquad f(m,x)=\min\!\Big(m(x),\ \max\big(0,\ \beta-\textstyle\sum_{y:\ \nu(x)<\nu(y)} m(y)\big)\Big).$$

The right-hand side is $2\,t\,|S|\,\exp\!\big(-N\delta^2/2\big)$, with $t$ and $|S|=\mathrm{card}(S)$ cast to reals, the constant $K$ appearing nowhere in it, and $\delta$ entering only through $\delta^2$. In particular, at $t=0$ the right-hand side is exactly $0$, so the claim there is that the total $\mathcal L_0$-mass of $B$ is $\le 0$; if $S$ is empty and $N>0$ then there are no joint states at all, both sides are $0$, and the whole statement is degenerate. For large $\delta$ the set $B$ may be empty, making the left side an empty sum equal to $0$. The quantifier order is essential: a single $K\ge 0$ must work simultaneously for all $N$, all admissible $\pi$, all starting states $s_0$, all horizons $t$, and all $\delta>0$.