Nonlinear Markov Chains with Finite State Space: Invariant Distributions and Long-Term Behaviour

Nonlinear Markov processes are a particular class of stochastic processes, where the transition probabilities do not only depend on the state, but also on the distribution of the process. McKean [10] introduced these type of processes to tackle mechanical transport problems. Thereafter they have been studied by several authors (see the monographs of Kolokoltsov [9] and Sznitman [17]). Recently, the close connection to continuous time mean field games led to significant progress in the analysis of McKean-Vlasov SDEs, in particular the control of these systems (see for example [4, 14]).

In this paper, we consider a special class of these processes, namely, nonlinear Markov chains in continuous time with a finite state space and provide first insights regarding the long-term behaviour of these processes. Nonlinear Markov chains with finite state space arise naturally, in particular in evolutionary biology, epidemiology and game theory. Namely, the replicator dynamics, several infection models, but also the dynamics of learning procedures in game theory are nonlinear Markov chains [9]. Moreover, also the population’s dynamics in mean field games with finite state and action space are nonlinear Markov chains [12].

The main focus of this paper lies in the characterization of the long-term behaviour of these processes. We show that always an invariant distribution exists and provide a sufficient criterion for the uniqueness of this invariant distribution. Thereafter, we turn to the long-term behaviour, where we first illustrate by two examples that the limit behaviour is much more complex than for classical Markov chains. More precisely, we show that the marginal distributions of a nonlinear Markov chain might be periodic and that irreducibility of the generator does not necessarily imply ergodicity. Then we provide easy-to-verify sufficient criteria for ergodicity for small state spaces (two or three states). All conditions that we propose are simple and rely only on the shape of the nonlinear generator, not on the shape of the transition probabilities.

The long-term behaviour of nonlinear Markov chains in continuous time with a finite state space has not been analysed before. The closest contribution in the literature are ergodicity criteria for nonlinear Markov processes in discrete time [3, 16]. These criteria are a generalization of Dobrushin’s ergodicity condition and the proofs crucially rely on the sequential nature of the problem.

The rest of the paper is structured as follows: In Section 2 we review the relevant definitions and notation. In Section 3 we present the results on existence and uniqueness of the invariant distribution. In Section 4 we provide examples of limit behaviour that cannot arise in the context of classical Markov chains. In Section 5 we present the ergodicity results for small state spaces. The Appendix A contains the proofs of two technical results.

This section gives a short overview over the relevant definitions, notations and preliminary facts regarding nonlinear Markov chains. For more details regarding these processes we refer the reader to [9, Chapter 1]. Moreover, it introduces the relevant notions to characterize the long-term behaviour of these processes.

Let $\mathcal{S}=\{1,\ldots,S\}$ be the state space of the nonlinear Markov chain and denote by $\mathcal{P}(\mathcal{S})$ the probability simplex over $\mathcal{S}$. A nonlinear Markov chain is characterized by a continuous family of nonlinear transition probabilities $P(t,m)=(P_{ij}(t,m))_{i,j\in\mathcal{S}}$ which is a family of stochastic matrices that depends continuously on $t\geq 0$ and $m\in\mathcal{P}(\mathcal{S})$ such that the nonlinear Chapman-Kolmogorov equation

is satisfied. As usual $P_{ij}(t,m_{0})$ is interpreted as the probability that the process is in state $j$ at time $t$ given that the initial state was $i$ and the initial distribution of the process was $m_{0}$. Such a family yields a nonlinear Markov semigroup $(\Phi^{t}(\cdot))_{t\geq 0}$ of continuous transformations of $\mathcal{P}(\mathcal{S})$ via

Also $\Phi^{t}(m_{0})$ has the usual interpretation that it represents the marginal distribution of the process at time $t$ when the initial distribution is $m_{0}$. A nonlinear Markov chain with initial distribution $m_{0}\in\mathcal{P}(\mathcal{S})$ is then given as the time-inhomogeneous Markov chain with initial distribution $m_{0}$ and transition probabilities $p(s,i,t,j)=P_{ij}(t-s,\Phi^{s}(m_{0}))$.

As in the theory of classical continuous time Markov chains the infinitesimal generator will be the cornerstone of the description and analysis of such processes: Let $\Phi^{t}(m)$ be differentiable in $t=0$ and $m\in\mathcal{P}(\mathcal{S})$, then the (nonlinear) infinitesimal generator of the semigroup $(\Phi^{t}(\cdot))_{t\geq 0}$ is given by a transition rate matrix function $Q(\cdot)$ such that for $f(m):=\left.\frac{\partial}{\partial t}\Phi^{t}(m)\right|_{t=0}$ we have $f_{j}(m)=\sum_{i\in\mathcal{S}}m_{i}Q_{ij}(m)$ for all $j\in\mathcal{S}$ and $m\in\mathcal{P}(\mathcal{S})$.

By [9, Section 1.1] any differentiable nonlinear semigroup has a nonlinear infinitesimal generator. However, the converse problem is more important: Given a transition rate matrix function (that is a function $Q:\mathcal{P}(\mathcal{S})\rightarrow\mathbb{R}^{S\times S}$ such that $Q(m)$ is a transition rate matrix for all $m\in\mathcal{P}(\mathcal{S})$) is there a nonlinear Markov semigroup (and thus a nonlinear Markov chain) such that $Q$ is the nonlinear infinitesimal generator of the process? Relying on the semigroup identity $\Phi^{t+s}=\Phi^{t}\Phi^{s}$ this problem is equivalent to the following Cauchy problem: Is there, for any $m_{0}\in\mathcal{P}(\mathcal{S})$ a solution $(\Phi^{t}(m_{0}))_{t\geq 0}$ of

such that $\Phi^{t}(\cdot)$ is a continuous function ranging from $\mathcal{P}(\mathcal{S})$ to itself and such that $\Phi^{t}(m)\in\mathcal{P}(\mathcal{S})$ for all $t\geq 0$ and $m\in\mathcal{P}(\mathcal{S})$.

In the monograph [9] the problem to construct a semigroup from a given generator is treated in a very general setting. Here, we present a result with easy-to-verify conditions tailored for the specific situation of nonlinear Markov chains with finite state space. The proof of the result, which relies on classical arguments from ODE theory, is presented in the appendix.

In this paper we are now mainly interested in the characterization of the long-term behaviour of nonlinear Markov chains: We say that $m\in\mathcal{P}(\mathcal{S})$ is an invariant distribution if $\frac{\partial}{\partial t}\Phi^{0}(m)=0$ and thus also $\frac{\partial}{\partial t}\Phi^{t}(m)=0$. An equivalent condition with respect to the generator is that a vector $m\in\mathcal{P}(\mathcal{S})$ is an invariant distribution if it solves $0=m^{T}Q(m)$.

We say that a nonlinear Markov chain with nonlinear semigroup $(\Phi^{t}(\cdot))_{t\geq 0}$ is strongly ergodic if there exists an $\bar{m}\in\mathcal{P}(\mathcal{S})$ such that for all $m_{0}\in\mathcal{P}(\mathcal{S})$ we have

The invariant distributions of a nonlinear Markov chain are exactly the fixed points of the set-valued map

Using Kakutani’s fixed point theorem, we directly obtain the existence of an invariant distribution for any generator:

If $Q(m)$ is irreducible for all $m\in\mathcal{P}(\mathcal{S})$, the sets $s(m)$ will be singletons [1, Theorem 4.2]. Let $x(m)$ denote this point. We remark that there are explicit representation formulas for $x(m)$ (e.g. [13, 15]). With these insights we provide the following sufficient criterion for the uniqueness of the invariant distribution:

The following examples show that the limit behaviour for nonlinear Markov chains (also in the case of small state spaces) is more complex than for classical continuous time Markov chains. In particular, the marginal distributions might not converge, but are periodic and a nonlinear Markov chain with an irreducible nonlinear generator might not be strongly ergodic, but we observe convergence towards several different invariant distributions.

Although the limit behaviour is more complex for nonlinear Markov chains, we still obtain sufficient criteria for ergodicity in the case of a small number of states. Here, we present these criteria, discuss applicability as well as the problems that occur for larger state spaces.

We also obtain a sufficient criterion for the case of three states. The proof technique is similar to the two state case. Indeed, we first show that our system is equivalent to a two-dimensional system, for which we can then use standard tools for two-dimensional dynamical systems exploiting that the dynamical system has a particular shape since $Q(\cdot)$ is a conservative generator.

As mentioned, we obtain for systems with three states that given $m_{0}\in\mathcal{P}(\mathcal{S})$ the function $\Phi^{t}(m_{0})=(\Phi^{t}_{1}(m_{0}),\Phi^{t}_{2}(m_{0}),\Phi^{t}_{3}(m_{0}))$ is a solution of $\frac{\partial}{\partial t}\Phi^{t}(m_{0})=Q(\Phi^{t}(m_{0}))^{T}\Phi^{t}(m_{0})$, $\Phi^{0}(m_{0})=m_{0}$ if and only of $(\Phi^{t}_{1}(m_{0}),\Phi^{t}_{2}(m_{0}))$ is a solution of

where

and $\hat{m}=(m_{1},m_{2},1-m_{1}-m_{2})$. Indeed, the proof is analogous to the proof for the two state case, the central adjustment is to prove the flow invariance of $\{(m_{1},m_{2})\in[0,\infty):m_{1}+m_{2}\leq 1\}$ for $(\Phi^{t}_{1}(m_{0}),\Phi^{t}_{2}(m_{0}))^{T}=f(\Phi^{t}_{1}(m_{0}),\Phi^{t}_{2}(m_{0}))$ instead of the flow invariance of $[0,1]$ for $\Phi^{t}_{1}(m_{0})=f(\Phi^{t}_{1}(m_{0}))$. This statement is proven in the appendix (Lemma A.1).

To show the desired convergence statement, we now rely on the Poincaré-Bendixson Theorem [18, Chapter 7], which characterizes the $\omega$-limit sets $\omega_{+}(m_{0})$ of a trajectory with initial condition $\Phi^{0}(m_{0})=m_{0}$: