A Mean Field Limit

We consider a system consisting of $N$ interacting objects. As we let the number of objects increase, we can characterize the limiting behaviour of the system.

We define our model as follows:

The are $N$ objects moving in discrete time and each of which taking states in the finite set ${\mathcal X}$ .
We let $X_n^N(t)$ be the state of the $n$ -th object at time $t$ .
We let $M_x^N(t)$ give the proportion of objects in state $x\in{\mathcal X}$ at time $t$ . Specifically, $M_x^N(t) = \frac{1}{N} \sum_{n=1}^N {\mathbb I} [X^N_n(t)=i].$
$X^N_n$ preforms transitions that depend on its previous state and the state of the system as recorded through a vector $S^N(t) \in {\mathbb R}^d$ . Specifically, there is a Transition matrix $P^N_{xy}(r)$ such that

${\mathbb P}( X^N_n(t+1) = y | X^N_n(t)=x , S^N_n(t) = s) = P_{xy}^N(r).$

Further the state of the system $S^N$ evolves according to the mean state vector $M^N$ and the previous state of the system:

We now take a limit where the number of objects in the system, $N$ , is sent to infinity. We make the following assumption

We assume that $P_{xy}^N(\cdot)$ converges uniformly to some probability transition matrix $P_{xy}(\cdot)$ .

The following results shows that for $M^N$ and $S^N$ a sensible limit comes from our analysis

Thrm [MF:Thrm] Provided

$M^N(0) \rightarrow \mu(0) \quad\text{and}\quad S^N(0) \rightarrow \sigma(0)$

for probability distribution $\mu (0)$ and vector $\sigma(0)$ then, almost surely,

$M^N(t) \rightarrow \mu(t) \quad\text{and}\quad S^N(t) \rightarrow \sigma(t)$

for each $t\in{\mathbb Z}_+$ where $\mu(t)$ and $\sigma(t)$ satisfy the equations

$\mu(t+1) = \mu(t) P(\sigma(t)),\qquad \sigma(t+1) = g( \sigma(t) , \mu(t+1) ).$

For the proof we will require the following elementary lemma followed by a proposition.

Prop [MF:Bern] Let $B^N$ be an integer in $\{0,1,...,N\}$ such that $\lim_{N\rightarrow\infty} B^N/N = \beta>0$ . Let $Y^N_b$ $b=1,...,B$ be iid Bernoulli such that ${\mathbb E} Y^N_b = y$ and we define

$Z^N = \frac{1}{B^N} \sum^{B^N}_{b=1} Y^N_b$

with $Z^N=0$ when $B^N=0$ . Then, almost surely,

$\lim_{N\rightarrow \infty} Z^N = y.$

Proof By a Chernoff bound, there exists $\alpha >0$ such that

${\mathbb P}( | Z^N -y| \geq \epsilon | B^N=b) \leq e^{-\alpha \epsilon b}$

for each $\epsilon >0$ . Thus

${\mathbb P} ( | Z^N -y| \geq \epsilon , B^N > b )$

$= {\mathbb E} \left[ \sum_{\tilde{b} \geq b N} {\mathbb P} ( | Z^N -y| \geq \epsilon | B^N = \tilde{b} ) {\mathbb I} [B^N =\tilde{b} \right]$

$= e^{-\alpha \epsilon b} {\mathbb P} ( B^N/N > b ).$

By the Borel-Cantelli Lemma

${\mathbb P} ( | Z^N- y | > \epsilon, B^N/N > b\text{ infinitely often }) = 0.$

But we know that $B^N/N > b$ eventually for any $b<\beta$ so we can see that (almost surely) eventually $\limsup_{N\rightarrow \infty} | Z^N-y| <\epsilon$ . Since $\epsilon$ is arbitrary, it must be that

$\lim_{N\rightarrow \infty} Z^N =y,$

as required. $\square$

To prove the result we compare the chain $X^N(t)$ with $\tilde{X}^N_n(t)$ , the chain where we replace $S^N(t)$ with its limit process $\sigma(t)$ . That is,

${\mathbb P}(\tilde{X}^N_n(t+1) = y | \tilde{X}_n^N(t)=x) = P_{xy}^N(\sigma(t)).$

and $X^N_n(0)=\tilde{X}^N_n(0)$ . Further, we note that since our state-space is finite we can assume the elements of ${\mathcal X}$ are ordered (with ordering $x\leq y$ ) and we can achieve a jump in our chain $X^N_n(t)$ to $X^N_n(t+1)$ with $S^N(t)=s$ [or $\tilde{X}^N_n(t)$ to $\tilde{X}^N_n(t+1)$ with $\sigma(t)=s$ ) by taking a uniform $[0,1]$ random variable $U$ and setting

$\label{MF:Xmoves} X^N_n(t+1)=y \qquad\text{if}\qquad \sum_{z: z<y} P_{xz}(s) < U_i < \sum_{z: z\leq y} P_{xz}(s) .$

We will assume that the versions of $X^N$ and $\tilde{X}^N$ are achieved by this process and that we use the same uniform random variables the jumps of $X^N_n(t)$ and $X^N_n(t+1)$ respectively.

We now prove the convergence of $\tilde{X}$ :

Prop [MF:Prop] Provided $M^N(0) \rightarrow \mu(0)$ for probability distribution $\mu(0)$ then, almost surely, $\tilde{M}^N(t) \rightarrow \mu(t)$ for each $t\in{\mathbb Z}_+$ where $\mu(t)$ satisfies the equation $\mu(t+1) = \mu(t) P(\sigma(t)).$

Proof. We prove the result by induction on $t$ , where we assume that the convergence result holdsup until time $t$ . The result trivally holds at time $0$ .

Now, assuming that the result holds until time $t$ . We let $I_{xy}^n$ be the indicator function if the $n$ -th object $X^N_n$ performs a jump from $x$ to $y$ at step $t$ .

$\tilde{M}^N_y(t+1) = \frac{1}{N} \sum_{n=1}^N {\mathbb I} [\tilde{X}_n^N(t+1) = y ]$ $= \frac{1}{N} \sum_{x\in{\mathcal X}} \sum_{n=1}^N I_{xy}^n {\mathbb I} [ \tilde{X}^N_n(t) = x ]$

Focusing on each term

$\frac{1}{N}\sum_{n=1}^N I_{xy}^n {\mathbb I} [ \tilde{X}^N_n(t) = x ].$

We see that it counts up $\tilde{M}^N_x(t)$ Bernoulli random variables and so Lemma [MF:Bern] applies and

$\frac{1}{N}\sum_{n=1}^N I_{xy}^n {\mathbb I} [ \tilde{X}^N_n(t) = x ] \xrightarrow[N\rightarrow\infty]{} \mu_x(t) P_{xy}(\sigma(t))$

provided $\lim_{N\rightarrow\infty}\tilde{M}^N_x(t) >0$ . If $\lim_{N\rightarrow\infty}\tilde{M}^N_x(t) >0$ the above term, which is bounded above by $\tilde{M}^N_n(t)$ , must converge to zero. $\square$

We now prove the main result. The main idea is to show, by induction, that $\tilde{X}^N$ and $X^N$ exhibit the same behaviour as $N$ goes to infinity.

Proof [Proof of Theorem [MF:Thrm]] One could think of this as an extension of Proposition [MF:Prop]. We preform induction on $t$ with the hypothesis that $\begin{aligned} \lim_{N\rightarrow\infty} \sum_{n=1}^N {\mathbb I} [ \tilde{X}^N_n(t) \neq X^N_n(t) ] =0,\label{MF:Xdiff}\\ M^N(t) \rightarrow \mu(t) \quad\text{and}\quad S^N(t) \rightarrow \sigma(t).\end{aligned}$

The hypothesis trivially holds for $t=0$ . Assuming that the induction hypothesis holds until time $t$ , we show that the result holds for time $t+1$ . Note that $\frac{1}{N}\sum_{n=1}^N {\mathbb I} [ \tilde{X}^N_n(t+1) \neq X^N_n(t+1) ]$ $=\frac{1}{N} \sum_{n=1}^N {\mathbb I} [ \tilde{X}^N_n(t+1) \neq X^N_n(t+1) , \tilde{X}^N_n(t) = X^N_n(t) ]$ $+\frac{1}{N}\sum_{n=1}^N {\mathbb I} [ \tilde{X}^N_n(t+1) \neq X^N_n(t+1) , \tilde{X}^N_n(t) \neq X^N_n(t) ]$ $\leq \sum_{x\in{\mathcal X}} A_x + \frac{1}{N}\sum_{n=1}^N {\mathbb I} [ \tilde{X}^N_n(t) \neq X^N_n(t) ] .\label{MF:last}$

where

$A_x = \frac{1}{N}\sum_{n=1}^N {\mathbb I} [ \tilde{X}^N_n(t+1) \neq X^N_n(t+1) , \tilde{X}^N_n(t) = X^N_n(t)=x ].$

Since the final term above converges to zero, it is sufficient to prove each $A_x^N$ converges to zero. Note that both the random variables $X^N_n(t)$ and $\tilde{X}^N_n(t)$ respectively are governed by the same condition with $s$ equal to $S^N(t)$ and $\sigma(t)$ respectively. Letting $L_{xy}$ and $V_{xy}$ respectively equal the minimum and minimum of \

$\bigg\{ \sum_{z: z\leq y} P_{xz}(S^N(t)) , \sum_{z: z\leq y} P_{xz}(\sigma(t)) \bigg\}.$

We see that $X^N_n(t)$ and $\tilde{X}^N_n(t)$ are not equal when

$U^N_n(t) \in [L_{ij},V_{ji}].$

We let $G^N(z)$ be the empircal distribution of our uniform random variables, that is

$G^N(z) = \frac{1}{N}\sum_{n=1}^N {\mathbb I} [ U^N_u \leq z].$

We note that

$A_x = \sum_{y\in{\mathcal X}}| G^N(V_{xy})-G^N(L_{xy}) |$ $\leq \sum_{y\in{\mathcal X}} \left| G^N(V^N_{xy}) -V^N_{xy}\right| + \left| G^N(L^N_{xy}) -L^N_{xy}\right| + \left| V^N_{xy} -L^N_{xy}\right|$ $\leq 2 |{\mathcal X}| \sup_z | G^N(z) -z | + \sum_{y\in{\mathcal X}} |V_{xy}^N-L^N_{xy} | \xrightarrow[N\rightarrow \infty]{} 0.$

$\sup_z | G^N(z) -z |$ converges to zero by the Glivenko-Cantelli Theorem. Thus holds at time $t+1$ .

At this point we see the $M^N_n(t+1)\rightarrow \mu(t+1)$ since holds at time $t+1$ and since $\tilde{M}^N_n(t)\rightarrow\mu(t)$ . Further by continuity of $g(\cdot,\cdot)$ and the induction hypothesis, we have that