We consider a system consisting of 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 objects moving in discrete time and each of which taking states in the finite set .
- We let be the state of the -th object at time .
- We let give the proportion of objects in state at time . Specifically,
- preforms transitions that depend on its previous state and the state of the system as recorded through a vector . Specifically, there is a Transition matrix such that
- Further the state of the system evolves according to the mean state vector and the previous state of the system:
We now take a limit where the number of objects in the system, , is sent to infinity. We make the following assumption
- We assume that converges uniformly to some probability transition matrix .
The following results shows that for and a sensible limit comes from our analysis
Thrm [MF:Thrm] Provided
for probability distribution and vector then, almost surely,
for each where and satisfy the equations
For the proof we will require the following elementary lemma followed by a proposition.
Prop [MF:Bern] Let be an integer in such that . Let be iid Bernoulli such that and we define
with when . Then, almost surely,
Proof By a Chernoff bound, there exists such that
for each . Thus
By the Borel-Cantelli Lemma
But we know that eventually for any so we can see that (almost surely) eventually . Since is arbitrary, it must be that
To prove the result we compare the chain with , the chain where we replace with its limit process . That is,
and . Further, we note that since our state-space is finite we can assume the elements of are ordered (with ordering ) and we can achieve a jump in our chain to with [or to with ) by taking a uniform random variable and setting
We will assume that the versions of and are achieved by this process and that we use the same uniform random variables the jumps of and respectively.
We now prove the convergence of :
Prop [MF:Prop] Provided for probability distribution then, almost surely, for each where satisfies the equation
Proof. We prove the result by induction on , where we assume that the convergence result holdsup until time . The result trivally holds at time .
Now, assuming that the result holds until time . We let be the indicator function if the -th object performs a jump from to at step .
Focusing on each term
We see that it counts up Bernoulli random variables and so Lemma [MF:Bern] applies and
provided . If the above term, which is bounded above by , must converge to zero.
We now prove the main result. The main idea is to show, by induction, that and exhibit the same behaviour as 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 with the hypothesis that
The hypothesis trivially holds for . Assuming that the induction hypothesis holds until time , we show that the result holds for time . Note that
Since the final term above converges to zero, it is sufficient to prove each converges to zero. Note that both the random variables and respectively are governed by the same condition with equal to and respectively. Letting and respectively equal the minimum and minimum of \
We see that and are not equal when
We let be the empircal distribution of our uniform random variables, that is
We note that
converges to zero by the Glivenko-Cantelli Theorem. Thus holds at time .
At this point we see the since holds at time and since . Further by continuity of and the induction hypothesis, we have that
This proves the induction hypothesis and the theorem.