Press "Enter" to skip to content

# Month: February 2017 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.

Random walk on ${\mathbb{N}}$. The transition kernel is ${\mathbf{P}(x,x+1)=p}$ for ${x\in\{0,1,\ldots\}}$ and ${\mathbf{P}(x,x-1)=1-p}$ for ${x\in\{1,2,\ldots\}}$ and ${\mathbf{P}(0,0)=1-p}$. Here again ${p\in(0,1)}$. The kernel is irreducible. All invariant measures are geometric, reversible, and take the form

$\mu(x)=\mu(0)\left(\frac{p}{1-p}\right)^x,\quad x\geq0.$

If ${p<1/2}$ then the chain is positive recurrent and there is a unique invariant probability measure which is the geometric law on ${\{0,1,\ldots\}}$ 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 blowing measure which cannot be normalized into a probability measure.

The continuous time analogue of this chain is known as the M/M/1 queue.

We could consider instead the reflected random walk on ${\mathbb{N}}$, by taking ${\mathbf{P}(0,1)=1}$. This deformation at the origin has a price: the invariant distribution in the case ${p<1/2}$ is no longer geometric, it is a mixture between a Dirac mass at ${0}$ and the geometric law on ${\{1,2,\ldots\}}$.

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)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.

Last Updated on 2020-06-22 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. Elle donne une idée du prix annuel par étudiant si l’université devait être financée entièrement par les frais de scolarité ! De ce point de vue, l’université française est d’une efficité sociale impressionnante : ~ 50 K€ pour un Master.

É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.

Last Updated on 2018-01-31

Syntax · Style · .