Press "Enter" to skip to content

Month: February 2017

Back to basics – irreducible Markov kernels

Markov chain

Let \( {{(X_n)}_{n\geq0}} \) be a Markov chain on an at most countable state space \( {E} \), with transition kernel \( {\mathbf{P}} \). For any \( {x,y\in E} \), the number of passages in \( {y} \) before returning to \( {x} \) is given by

\[ \mu_x(y)=\mathbb{E}_x\left(\sum_{n=0}^{T_x-1}\mathbf{1}_{X_n=y}\right) \quad\mbox{where}\quad T_x=\inf\{n>0:X_n=x\}. \]

Note that \( {\mu_x(x)=1} \) and \( {\mu_x(E)=\mathbb{E}(T_x)} \).

I like very much the following classical theorem about irreducible kernels:

Irreducible kernels. Suppose that \( {\mathbf{P}} \) is irreducible. Then every invariant measure \( {\mu} \) has full support and satisfies \( {\mu(y)\geq\mu(x)\mu_x(y)} \) for any \( {x} \) and \( {y} \) in \( {E} \). Moreover there are three cases:

  1. \( {\mathbf{P}} \) is transient. Then \( {\mu(E)=\infty} \) for every invariant measure \( {\mu} \), \( {E} \) is infinite, and there is no invariant probability measure;
  2. \( {\mathbf{P}} \) is recurrent. Then \( {\mu_x} \) is invariant for every \( {x\in E} \); the invariant measures are all proportional; and if \( {\mu} \) is invariant then \( {\mu(y)=\mu(x)\mu_x(y)} \) for any \( {x,y\in E} \). In particular \( {\mu_x(y)\mu_y(x)=1} \). There are two sub-cases:
    1. \( {\mathbf{P}} \) is positive recurrent. Then there exists a unique invariant probability measure \( {\mu} \) given by \( {\mu(x)=1/\mathbb{E}_x(T_x)} \) for every \( {x\in E} \);
    2. \( {\mathbf{P}} \) is null recurrent. Then \( {\mu(E)=\infty} \) for every invariant measure \( {\mu} \), \( {E} \) is infinite, and there is no invariant probability measure.

Here are my three favorite examples with infinite countable state space:

Random walk on \( {\mathbb{Z}} \). The transition kernel is given by \( {\mathbf{P}(x,x+1)=p} \) and \( {\mathbf{P}(x,x-1)=1-p} \) for every \( {x\in\mathbb{Z}} \), with \( {p\in(0,1)} \). The kernel is irreducible. A measure \( {\mu} \) on \( {\mathbb{Z}} \) is invariant for \( {\mathbf{P}} \) iff for every \( {x\in\mathbb{Z}} \),

\[ \mu(x)=\sum_{y\in\mathbb{Z}}\mu(y)\mathbf{P}(y,x)=p\mu(x-1)+(1-p)\mu(x+1). \]

This gives that all invariant measures take the form

\[ \mu(x)=a+b\left(\frac{p}{1-p}\right)^x,\quad x\in\mathbb{Z}, \]

where \( {a,b\geq0} \) are parameters such that \( {\mu(0)=a+b>0} \). We recover the counting measure if \( {b=0} \) and a sort of geometric measure when \( {a=0} \) which is reversible. If \( {p=1/2} \) then both terms are the same and the counting measure is reversible.

The chain never admits an invariant probability measure. If \( {p=1/2} \) then the chain is null recurrent, all invariant measures are proportional. If \( {p\neq 1/2} \) then the chain is transient, there is a two parameters family of invariant measures.

Reflected random walk on \( {\mathbb{N}} \). The transition kernel is \( {\mathbf{P}(x,x+1)=p} \) and \( {\mathbf{P}(x,x-1)=1-p} \) for any \( {x\in\{1,2,\ldots\}} \) and \( {\mathbf{P}(0,1)=1} \). Here again \( {p\in(0,1)} \). The kernel is irreducible. This time the reflection at zero kills the counting measure. All invariant measures are of geometric type, are reversible, and take the form

\[ \mu(x)=\mu(0)\left(\frac{p}{1-p}\right)^x,\quad x\in\mathbb{N}. \]

If \( {p<1/2} \) then the chain is positive recurrent and there is a unique invariant probability measure which is the geometric distribution with parameter \( {p/(1-p)} \). If \( {p=1/2} \) then the chain is null recurrent and the invariant measures are all proportional to the counting measure. If \( {p>1/2} \) then the chain is transient and all invariant measures are proportional to a geometric measure which cannot be normalized into a probability measure.

Growth and collapse walk on \( {\mathbb{N}} \). The transition kernel is given by \( {\mathbf{P}(x,x+1)=p_x} \) and \( {\mathbf{P}(x,0)=1-p_x} \), for every \( {x\in\mathbb{N}} \), where \( {p_0=1} \), \( {p_1,p_2,\ldots\in[0,1]} \). The kernel is irreducible iff

\[ \{x\in\mathbb{N}:p_x>0\}=\mathbb{N} \quad\text{and}\quad \mbox{Card}\{x\in\mathbb{N}:p_x<1\}=\infty. \]

The very special growth-collapse nature of \( {\mathbf{P}} \) gives

\[ \mathbb{P}_0(T_0>n)=\prod_{x=0}^n\mathbf{P}(x,x+1)=p_0p_1\cdots p_n. \]

Also, if the kernel is irreducible, then it is recurrent iff

\[ \lim_{x\rightarrow\infty}p_0p_1\cdots p_x=0. \]

If \( {\mu} \) is invariant then for any \( {x\in\mathbb{N}} \) with \( {x>0} \),

\[ \mu(x)=\sum_{y\in\mathbb{N}}\mu(y)\mathbf{P}(y,x)=\mu(x-1)p_{x-1}=\mu(0)\cdots=p_0p_1\cdots p_{x-1}. \]

It follows that if the kernel is irreducible, then it is positive recurrent iff

\[ \sum_{x=0}^\infty p_0p_1\cdots p_x<\infty, \]

and in this case there exists a unique invariant probability measure given by

\[ \mu(x)=\frac{1}{\mathbb{E}_x(T_x)},\quad x\in\mathbb{N}. \]

Note that if \( {p=\prod_{x\in\mathbb{N}}p_x\in(0,\infty)} \) and if \( {\mu} \) is invariant then \( {\mu(x)\geq p\mu(0)} \), and since \( {\mu(0)=\sum_{x\in\mathbb{N}}(1-p_x)\mu(x)} \), we get \( {\mu(0)\geq p\mu(0)\sum_{x\in\mathbb{N}}(1-p_x)} \), which forces either \( {\mu(0)=0} \) or \( {\mu(0)=\infty} \), and therefore there is no invariant measure in this case.

Further reading. Markov chains, by James Norris.

Leave a Comment

Prix des études supérieures

La comptabilité analytique fait peu à peu son apparition dans les administrations des universités françaises. À Paris-Dauphine, le calcul du coût par étudiant en fonction du département est mené au moyen d’un modèle de répartition subtilement paramétré. Bien que le modèle soit arbitraire et discutable, les résultats obtenus sont intéressants car source de questionnements sur le mode d’organisation et sur l’efficacité des composantes. Ainsi, pour le département MIDO – licences et masters en mathématiques et informatique – le prix moyen d’un étudiant par an serait de l’ordre de 18000 Euros. Ceci inclut la masse salariale, sauf celle des chercheurs qui n’enseignent pas comme ceux du CNRS. L’ordre de grandeur est facile à retrouver. En effet, en divisant le budget de l’université, d’environ 110 Millions d’Euro, par le nombre d’étudiants, environ 10000, on obtient environ 11000 Euros par étudiant et par an. Voici le résultat de cette division toute simple menée pour quelques autres établissements d’enseignement supérieur français. Les données – budgets et effectifs – sont extraits des pages de Wikipédia.

Établissement    Budget(M€)    Étudiants      B/E 
-------------------------------------------------
ÉNS-Paris              102         2400   42500 €
Polytechnique          100         2899   34495 €
HEC                    127         4000   31750 €
Sciences-Po            173        13000   13308 €
Paris-Dauphine         110        10320   10659 €
Strasbourg             500        48011   10414 €
Toulouse-III           328        31987   10254 €
UPMC                   345        33789   10210 €
Paris-Diderot          244        25000    9760 €
Aix-Marseille          722        74000    9757 €
Lyon-I                 421        45000    9356 €
Paris-Sud              275        30200    9106 €

À Paris-Dauphine, le feuilleton des frais de scolarité se poursuit, notamment au sein du département MIDO, qui a finalement décidé de temporiser. Au delà du département MIDO, certains défendent l’idée que des frais de scolarité modulés en fonction du revenu risquent de faire fuir les riches, qui ne sont pas captifs comme dans la situation des cantines scolaires. Il s’agit là d’une idée souvent agitée par la droite contre les impôts progressifs défendus par la gauche. La réalité du phénomène ne fait aucun doute, et c’est plutôt son ampleur et son impact final qui font débat. Excités par cette idée, certains vont même plus loin et pensent qu’il faudrait afficher le vrai prix des études, les fameux 18000 Euros, et attribuer des bourses « virtuelles » qui effacent plus ou moins ce montant en fonction du revenu. Cela modifierait la perception de la part des riches, et ne changerait rien pour les pauvres. Il resterait tout de même à doser la progressivité pour les classes moyennes. On retrouve la question initiale. Elle alimente chez les collègues une sourde angoisse du déclassement. Il est vrai qu’ils sont les dominants et bénéficiaires du secteur de l’éducation.

Leave a Comment