Dauphine : frais de scolarité

January 23rd, 2016 No comments

Université_Paris-Dauphine

La plupart des établissements d’enseignement supérieur français du secteur public font face depuis quelques années à des dépenses de plus en plus importantes, liées notamment au vieillissement de leurs salariés, à l’accroissement de leur autonomie, ou à la réforme de la taxe d’apprentissage. Comme l’État ne s’engage pas plus, et ne le fera sans doute pas de si tôt, ces établissements sont conduits inexorablement à rechercher des sources de refinancement, notamment en augmentant les frais de scolarité acquittés par les étudiants. En la matière, l’université Paris-Dauphine ne fait pas exception. C’est dans ce contexte que le département LSO de Paris-Dauphine s’apprête à suivre l’exemple de Sciences Po : faire payer les riches en modulant le montant des frais de scolarité en fonction des revenus des parents. La mise en place de la modulation est délicate, et doit tenir compte de la composition des familles, des cas spéciaux des étudiants venus de l’étranger, etc. Tout comme les classes préparatoires, et contrairement à la plupart des universités françaises, Paris-Dauphine accueille beaucoup d’étudiants issus de familles aisées, qui payent les mêmes frais de scolarité que leurs camarades issus de familles moins aisées (exception faite des boursiers, exonérés de frais de scolarité). Du côté des mathématiques et de l’informatique, le département MIDO de Paris-Dauphine est en pleine réflexion sur cette question particulièrement épineuse. Les conditions de travail généreuses dont bénéficient les enseignants-chercheurs pourraient être à ce prix.

La modulation fait peur car elle correspond symboliquement à un changement de paradigme, à une forme d’abandon de l’État providence, à une porte ouverte sur des excès à l’américaine. Cette crainte conduit à une ligne de fracture politique, au parfum d’absolu à gauche, et aux senteurs de dérégulations à droite. Quoi qu’il en soit, les frais de scolarité augmentent discrètement ici et là, et sont à l’heure actuelle plus de dix fois plus élevés dans les (très) grandes écoles d’ingénieurs que dans les universités ! Ces frais de scolarité des établissements français restent néanmoins la plupart du temps dérisoires par rapport aux niveaux des salaires de première embauche.

En France, le vrai marché de l’éducation n’est pas celui des frais de scolarité, mais plutôt celui de la valeur socio-économique des diplômes et donc du prestige des établissements. À Paris-Dauphine, les étudiants viennent chercher un label qui leur garantira une carrière intéressante. Tant qu’ils pourront s’offrir ce label, il le feront, et s’ils peuvent s’offrir un meilleur label ailleurs, il le feront aussi. La faible ampleur de la modulation des frais de scolarité ne change rien à cet état de fait, d’autant plus que les étudiants issus des milieux les moins favorisés ne sont pas impactés. Ce thème des frais de scolarité est décidément passionnant, et donne envie de relire Pierre Bourdieu (et ses détracteurs) !

Des collègues m’ont demandé de préciser mon opinion personnelle sur la question.  Dans la société idéale dont je rêve, la santé et l’éducation sont gratuites, sont financées par des impôts collectés par l’état, et ces impôts sont progressifs et redistributifs. Malheureusement la réalité est différente. Nous traversons une époque dans laquelle l’éducation nécessite plus de moyens tandis que l’état ne s’engage pas d’avantage. La question est donc de savoir comment s’organiser en attendant le retour éventuel de l’état (si si c’est possible !). L’instauration de frais de scolarité progressifs basés sur les revenus est une solution socialement juste, qu’on peut préférer à la réforme libérale adoptée en Grande Bretagne, mais qui fait prendre le risque de possibles dérives. On peut alternativement opter pour la posture de la résistance et du statu quo, quitte à détériorer les conditions de travail des enseignants-chercheurs et les conditions d’étude des étudiants. Charybde et Scylla ! L’idéal bien à l’esprit, peut-on dire que d’une certaine manière, en terme d’abandon de la quasi-gratuité, les frais de scolarité progressifs sont à l’éducation ce que les mutuelles sont à la santé ?

Share
Categories: Universities

EJP-ECP : twenty years of freeness

December 20th, 2015 No comments

EJP www logo designed by PKP ECP www logo by PKP

Electronic Journal of Probability (EJP) and Electronic Communications in Probability (ECP) are electronic journals free for authors and free for readers. Created in 1995, they are sponsored by the Bernoulli Society and the Institute of Mathematical Statistics (IMS) who publishes several other journals such as the Annals of Probability (AoP) and the Annals of Applied Probability (AoAP).

Up to now, the administrative and technical tasks of managing editor and production editor are supported by a university professor, reducing the direct cost of the journal. This scheme is not sustainable due to the success of EJP-ECP : see the graphics below. Also starting from January 2016, the journals will be handled by Mattson Publishing Services (MPS) and VTEX, just like AoP and AoAP. Technically, this new organization for EJP-ECP implies that the editorial software Open Journals Software (OJS) will be replaced by the Electronic Journal Management System (EJMS) developed by VTEX, while the diffusion and archival will be handled by Project Euclid, just like for AoP and AoAP. In contrast with AoP and AoAP, EJP and ECP will stay purely electronic and free for authors and for readers. This will cost about $30K per year to the IMS, and it is expected that at most 30% will be covered by publication charges contributed by authors via the Open Access Fund. In fact EJP-ECP will follow exactly the workflow used by the IMS for Electronic Journal of Statistics.

Note that MPS is a small US company specialized in open access publications, while VTEX is a small Lithuanian company specialized in typesetting and editorial hosting. Both companies are handling most of the IMS journals. Note also that Lithuania belongs to the Euro zone.

In France, the Centre de diffusion des revues académiques mathématiques (CEDRAM) plays a role similar to the one of the IMS, for some French based journals such as Annales de l’Institut Fourier (AIF). Presently the CEDRAM is willing to deploy OJS, and to handle typesetting internally. For French readers:  La solution retenue par l’IMS pour EJP-ECP est à la fois généreuse et cohérente avec sa logique de fonctionnement. OJS est un très bon produit, qui a contribué au succès de EJP-ECP pendant près de dix ans. Je reste disponible pour aider à améliorer la situation des revues françaises, et les faire évoluer si possible vers un modèle qui les rendrait libres d’accès pour les auteurs et les lecteurs. Le reste est, de mon point de vue, plus de l’ordre des moyens que de la fin.

Papers published in ECP (red) and EJP (blue)

Papers published in ECP (red) and EJP (blue)

Pages per paper in ECP (red) and EJP (blue)

Pages per paper in ECP (red) and EJP (blue)

Pages published in ECP (red) and EJP (blue)

Pages published in ECP (red) and EJP (blue)

Note. Personally, I have served as a Managing and Production Editor for EJP+ECP mainly from 2012 to 2015 inclusive. In particular, I had to process (format check and metadata) 341+467 = 808 accepted papers (about 3544 + 12556 = 16100 pages). This support mission consisted also in solving all the technical issues with the editors, the reviewers, and the authors. Among other tasks, I also wrote a bunch of Bash / Python / LaTeX files to produce statistics, monitoring, and style. I was also involved in the 2012 database transition to OJS 2.x and in the 2015 transition from OJS to EJMS. All in all, it was for me a fantastic experience, during which I have learned many things about the internals of publishing.

Note (en français). On m’a souvent reproché de passer du temps sur EJP/ECP alors que je n’étais pas payé pour ça. Ces reproches sont venus aussi bien d’acteurs de l’édition que de certains collègues ! Pourtant la lourde tâche qui était la mienne ne faisait pas plus partie de mes attributions théoriques que toutes sortes d’autres corvées que les scientifiques universitaires doivent affronter : administration, copies, surveillances, etc. Ma conviction après cette expérience est qu’il est tout à fait acceptable qu’un scientifique joue le rôle de l’homme à tout faire temporairement d’une revue qui démarre ou qui est en difficulté, ou durablement d’une revue qui publie peu comme le journal de l’École Polytechnique. Cela étant dit, lorsque le volume de publication est au niveau atteint par EJP/ECP, ceci n’est pas durable et il est évidemment préférable que ce travail technique et de gestion éditoriale soit accompli à terme par des professionnels mutualisés dont c’est le métier. C’est en cela que le projet du CEDRAM est particulièrement pertinent.

Share
Categories: Uncategorized

Le rouge et le noir

December 19th, 2015 No comments

Les cartes visualisant les résultats commune par commune du premier tour des élections régionales de décembre 2015 sont très intéressantes. En voici trois. Elles figuraient sur le site lemonde.fr mais ont été malheureusement remplacées par celles du second tour, beaucoup moins intéressantes. Elles mettent en lumière des homogénéités spatiales locales socio-économiques et socio-culturelles. Ces cartes font penser aux analyses d’Emmanuel Todd.

Lille, rare île rose dans une mer noire.

Les idées noires du littoral et… de Montauban !

Paris : réalités urbaines et périurbaines.

Le Moulin, de Gilbert Garcin.

De tout temps, la jeunesse s’oppose à l’ordre établi, tandis que la vieillesse préfère le maintenir. Il semble qu’actuellement, notre jeunesse instruite, qui peuple surtout les grandes villes, s’oppose avec du rouge ou du vert, tandis que notre jeunesse peu instruite le fait plutôt avec du noir.

Share
Categories: Uncategorized

Back to basics – Pólya urns

November 30th, 2015 No comments

Georges Pólya

Georges Pólya (1887 – 1985)

This post is devoted to Pólya urns, probably the simplest stochastic model of reinforcement. At time \( {n=0} \), we prepare an urn containing \( {a>0} \) azure balls and \( {b>0} \) black balls. To produce the configuration of the urn at time \( {n=1} \), we draw at random a ball in the urn, and then we replace this ball in the urn together with a new ball of the same color. We repeat this mechanism independently to produce the configuration of the urn at any time \( {n\in\mathbb{N}} \).

Let \( {M_n\in[0,1]} \) be the proportion of azure balls in the urn at time \( {n\in\mathbb{N}} \). At time \( {n\in\mathbb{N}} \), the urn contains \( {a+b+n} \) balls, and \( {(a+b+n)M_n} \) azure balls. Conditional on \( {M_n} \), an azure ball is added to the urn at time \( {n+1} \) with probability \( {M_n} \). Hence

\[ M_0=\frac{a}{a+b} \quad\text{and}\quad M_{n+1}=\frac{(a+b+n)M_n+\mathbf{1}_{\{U_{n+1}\leq M_n\}}}{a+b+n+1} \]

where \( {{(U_n)}_{n\geq1}} \) are iid uniform random variables on \( {[0,1]} \), and the event \( {\{U_{n+1}\leq M_n\}} \) corresponds to add an azure ball. The stochastic recursive sequence \( {{(M_n)}_{n\geq0}} \) is a non-homogeneous Markov chain with state space \( {[0,1]} \), and also a martingale.

If we encode the result of the \( {n} \) drawing by a random variable \( {X_n} \) with values in \( {\{\alpha,\beta\}} \) where \( {\alpha} \) and \( {\beta} \) indicate respectively that the ball is azure or black. Let \( {Y_n} \) and \( {Z_n} \) be respectively the number of azure and black balls added to the urn after the first \( {n} \) drawing. At time \( {n} \), the urn contains

\[ a+Y_n+b+Z_n=a+b+n \]

balls, more precisely the number of azure balls is

\[ a+Y_n=a+\sum_{k=1}^n\mathbf{1}_{\{X_k=\alpha\}}=(a+b+n)M_n \]

while the number of black balls is

\[ b+Z_n=b+\sum_{k=1}^n\mathbf{1}_{\{X_k=\beta\}}. \]

We have \( {Y_n+Z_n=n} \). The sequence \( {{(X_n,Y_n,Z_n)}_{n\geq1}} \) satisfies the stochastic recursion

\[ (X_{n+1},Y_{n+1},Z_{n+1}) = \left\{ \begin{array}{rl} (\alpha,Y_n+1,Z_n) & \mbox{if } U_{n+1}\leq\frac{a+Y_n}{a+b+n},\\ (\beta,Y_n,Z_n+1) & \mbox{if } U_{n+1}>\frac{a+Y_n}{a+b+n}, \end{array} \right. \]

with by convention \( {Y_0=0} \) and \( {Z_0=0} \) (the value of \( {X_0} \) is useless).

Martingale. The sequence \( {{(M_n)}_{n\geq0}} \) is a martingale taking its values in \( {[0,1]} \) for the filtration \( {{(\mathcal{F}_n)}_{n\geq0}} \) defined by \( {\mathcal{F}_n=\sigma(U_1,\ldots,U_n)} \). Indeed \( {M_n\in L^1(\mathcal{F}_n)} \) and

\[ \mathbb{E}(M_{n+1}\,|\,\mathcal{F}_n) =\mathbb{E}(M_{n+1}\,|\,M_n) =\frac{(a+b+n)M_n+M_n}{a+b+n+1} =M_n. \]

In particular we have the following conservation law: for all \( {n\in\mathbb{N}} \),

\[ \mathbb{E}(M_n)=\mathbb{E}(M_0)=\frac{a}{a+b}. \]

It follows from martingale limit theorems (the martingale is uniformly bounded and thus uniformly integrable!) that there exists a random variable \( {M_\infty} \) on \( {[0,1]} \) such that

\[ \lim_{n\rightarrow\infty}M_n = M_\infty \]

almost surely and in \( {L^p} \) for any \( {p\geq1} \). In particular \( {\mathbb{E}(M_\infty)=\mathbb{E}(M_0)=\frac{a}{a+b}} \).

Limiting distribution. The random variable \( {M_\infty} \) follows the Beta distribution on \( {[0,1]} \) with parameter \( {(a,b)} \) and density

\[ u\in[0,1]\mapsto\frac{u^{a-1}(1-u)^{b-1}}{\mathrm{Beta}(a,b)} \quad\text{where}\quad \mathrm{Beta}(a,b):=\int_0^1\!p^{a-1}(1-p)^{b-1}\,dp. \]

In particular if \( {a=b=1} \) then \( {M_\infty} \) follows the uniform distribution on \( {[0,1]} \).

To see it let us recall first of all that

\[ \mathrm{Beta}(a,b) =\frac{\Gamma(a)\Gamma(b)}{\Gamma(a+b)} \quad\text{where}\quad \Gamma(x):=\int_0^\infty\!t^{x-1}e^{-x}\,dx. \]

For any \( {c} \) and \( {k} \) we set

\[ c^{(k)}=c(c+1)\cdots(c+k-1)=\frac{(c+k-1)!}{(c-1)!}=\frac{\Gamma(c+k)}{\Gamma(c)}. \]

Now for any \( {x_1,\ldots,x_n} \) in \( {\{0,1\}} \), we have, denoting \( {k=x_1+\cdots+x_n} \),

\[ \mathbb{P}(\mathbf{1}_{\{X_1=\alpha\}}=x_1,\ldots,\mathbf{1}_{\{X_n=\alpha\}}=x_n) =\frac{a^{(k)}b^{(n-k)}}{(a+b)^{(n)}}. \]

This probability is invariant by permutation of \( {x_1,\ldots,x_n} \): this means that the distribution of the random vector \( {(\mathbf{1}_{\{X_1=\alpha\}},\ldots,\mathbf{1}_{\{X_n=\alpha\}})} \) is exchangeable. Hence the random variable

\[ Y_n=\sum_{k=1}^n\mathbf{1}_{\{X_k=\alpha\}} \]

satisfies, for any \( {k\in\{0,1,\ldots,n\}} \),

\[ \begin{array}{rcl} \mathbb{P}(Y_n=k) &=&\binom{n}{k}\frac{a^{(k)}b^{(n-k)}}{(a+b)^{(n)}}\\ &=&\binom{n}{k} \frac{\Gamma(a+k)\Gamma(b+n-k)\Gamma(a+b)}{\Gamma(a)\Gamma(b)\Gamma(a+b+n)}\\ &=&\binom{n}{k} \frac{\mathrm{Beta}(a+k,b+n-k)}{\mathrm{Beta}(a,b)}\\ &=&\int_0^1\! \binom{n}{k}p^{k}(1-p)^{n-k}\frac{p^{a-1}(1-p)^{b-1}}{\mathrm{Beta}(a,b)}\,dp. \end{array} \]

We say that \( {Y_n} \) follows the Beta-binomial distribution, which is a a mixture of binomial laws of size \( {n} \) with a parameter \( {p} \) which follows the Beta distribution of parameter \( {(a,b)} \). We have \( {M_n=(a+Y_n)/(a+b+n)} \) with \( {Y_0=0} \). When \( {a=b=1} \), then formula for the law of \( {Y_n} \) indicates that \( {Y_n} \) is uniform on \( {\{0,1,\ldots,n\}} \), and thus \( {M_n} \) is uniform on \( {\{1/(n+2),\ldots,(n+1)/(n+2)\}} \), which implies that \( {M_\infty} \) is uniform on \( {[0,1]} \). In the general case, for any \( {t\in[0,1]} \),

\[ \begin{array}{rcl} \mathbb{P}(M_\infty\leq t) &=&\lim_{n\rightarrow\infty}\mathbb{P}(Y_n\leq(a+b+n)t-a)\\ &=&\cdots =\frac{1}{\mathrm{Beta}(a,b)}\int_0^t\!u^{a-1}(1-u)^{b-1}\,du. \end{array} \]

The computation is based on the so-called Beta-binomial correspondence, which states that if \( {U_1,\ldots,U_n} \) are iid and uniform on \( {[0,1]} \) and if \( {U_{(1)}\leq\cdots\leq U_{(n)}} \) is their reordering, then for any \( {k=1,\ldots,n} \) the random variable \( {U_{(k)}} \) follows the Beta distribution on \( {[0,1]} \) with parameter \( {(k,n-k+1)} \) and

\[ \mathbb{P}(S_n\geq k) =\mathbb{P}(\mathbf{1}_{\{U_1\leq p\}}+\cdots+\mathbf{1}_{\{U_n\leq p\}}\geq k) =\mathbb{P}(U_{(k)}\leq p). \]

From discrete to continuous. The results remain valid when \( {a} \) and \( {b} \) are positive reals. This motivates the usage of Beta and Gamma functions instead of factorials. In this case we may use an interval partition instead of an urn.

General urns and sampling schemes. We generalized the reinforcement mechanism as follows: we fix an integer \( {r\geq-1} \), and, at each drawing, we replace in the urn \( {1+r} \) balls of the drawn color.

  • if \( {r=1} \) then we recover the Pólya urn studied above for which \( {Y_n} \) follows the Beta-binomial distribution;
  • if \( {r=0} \) then we recover a sampling with replacement and \( {Y_n} \) follows then the binomial distribution;
  • if \( {r=-1} \) then we recover a sampling without replacement and \( {Y_n} \) follows the hypergeometric distribution;
  • more generally, for any \( {r\geq-1} \) and \( {k\in\{0,1,\ldots,n\}} \), we have

    \[ \mathbb{P}(Y_n=k)=\frac{a^{(r,k)}b^{(r,k)}}{(a+b)^{(r,k)}} \quad\text{where}\quad c^{(r,k)}:=c(c+r)\cdots(c+(k-1)r) \]

    and in this case \( {M_\infty} \) follows the Beta distribution of parameter \( {(a/r,b/r)} \).

It is also possible to consider an arbitrary number of colors, which produces a model which includes as a particular case the sampling model of the multivariate hypergeometric distribution. It is also possible to use a replacement matrix as follows: fix a matrix

\[ A={(A_{i,j})}_{1\leq i,j\leq k}\in\mathcal{M}_{k}(\mathbb{N}) \]

and consider the generalized Pólya urn with \( {k} \) colors defined as follows: we draw a ball at random, we denote by \( {i} \) its color, and then we replace in the urn \( {A_{i,j}} \) balls of color \( {j} \) for any \( {j=1,\ldots,k} \). The standard Pólya urn corresponds to \( {k=2} \) and \( {A=2I_2} \).

Rubin’s theorem on generalized Pólya urns. We consider two non-decreasing functions

\[ S_\alpha,S_\beta:\mathbb{N}\rightarrow\mathbb{R}_+ \]

such that \( {S_\alpha(0)>0} \) and \( {S_\beta(0)>0} \). We construct a random recursive sequence \( {{(X_n)}_{n\geq1}} \) taking its values in \( {\{\alpha,\beta\}} \) as follows: for any \( {n\in\mathbb{N}} \), conditional on \( {X_1,\ldots,X_n} \), denoting \( {Y_n=\sum_{k=1}^n\mathbf{1}_{\{X_k=\alpha\}}} \) and \( {Z_n=n-Y_n} \), we set

\[ (X_{n+1},Y_{n+1},Z_{n+1})= \left\{ \begin{array}{rl} (\alpha,Y_n+1,Z_n) & \text{if } U_{n+1}\leq \frac{S_\alpha(Y_n)}{S_\alpha(Y_n)+S_\beta(Z_n)}, \\ (\beta,Y_n,Z_n+1) & \text{if } U_{n+1}>\frac{S_\alpha(Y_n)}{S_\alpha(Y_n)+S_\beta(Z_n)}, \end{array} \right. \]

where \( {{(U_n)}_{n\geq1}} \) are iid uniform random variables on \( {[0,1]} \). Such a sequence \( {{(X_n)}_{n\geq1}} \) encodes the drawings of a generalized Pólya urn. If \( {(S_\alpha(0),S_\beta(0))=(A_0,B_0)} \) is deterministic and \( {S_\alpha(n)=S_\beta(n)=r(n)} \) for any \( {n>0} \), then we say that we have

  • no reinforcement when \( {r} \) is linear (sampling with replacement);
  • linear reinforcement when \( {r} \) is affine (standard Pólya urn);
  • geometric reinforcement when \( {r} \) is a power function.

To study the general case, we introduce the probability \( {p_\alpha} \) (respectively \( {p_\beta} \)) that the sequence \( {{(X_n)}_{n\geq1}} \) contains a finite number of \( {\beta} \) (respectively of \( {\alpha} \)) in other words only \( {\alpha} \) (respectively \( {\beta} \)) for large enough \( {n} \). These probabilities are given by

\[ p_\alpha =\mathbb{P}\left(\cup_n\cap_{k\geq n}\{X_k=\alpha\}\right) \quad\text{and}\quad p_\beta =\mathbb{P}\left(\cup_n\cap_{k\geq n}\{X_k=\beta\}\right). \]

We have

\[ p_\alpha+p_\beta\leq1. \]

The following numbers in \( {[0,\infty]} \) will play an crucial role:

\[ \varphi_\alpha=\sum_{n=0}^\infty\frac{1}{S_\alpha(n)} \quad\text{and}\quad \varphi_\beta=\sum_{n=0}^\infty\frac{1}{S_\beta(n)}. \]

We are now ready to state Rubin‘s theorem: \( {p_\alpha,p_\beta} \) are linked to \( {\varphi_\alpha,\varphi_\beta} \) via

\[ \begin{array}{c||c|c} & \varphi_\beta<\infty & \varphi_\beta=\infty \\\hline\hline \varphi_\alpha<\infty & p_\alpha>0, p_\beta>0, p_\alpha+p_\beta=1 & p_\alpha=1 (\Rightarrow p_\beta=0)\\\hline \varphi_\alpha=\infty & p_\beta=1 (\Rightarrow p_\alpha=0) & p_\alpha=0, p_\beta=0\\ \end{array} \]

In particular the triviality of \( {p_\alpha} \) and \( {p_\beta} \) depends only on the asymptotic behavior of the reinforcement functions \( {S_\alpha} \) and \( {S_\beta} \), and the critical cases are related to the Riemann condition. In the case of absence of reinforcement (\( {S_\alpha} \) and \( {S_\beta} \) are linear) and in the case of linear reinforcement (\( {S_\alpha} \) and \( {S_\beta} \) are affine) we have \( {\varphi_\alpha=\varphi_\beta=\infty} \) since the harmonic series diverges. As soon as the reinforcement is over-linear, we get \( {\varphi_\alpha<\infty} \) and \( {\varphi_\beta<\infty} \), and this is the case in particular for the quadratic reinforcement and more generally for the geometric reinforcement.

Proof of Rubin’s theorem. Let \( {{(E^\alpha_n)}_{n\geq0}} \) and \( {{(E^\beta_n)}_{n\geq0}} \) be two independent sequences of independent random variables with, for any \( {n\geq0} \),

\[ \mathbb{E}(E^\alpha_n)=\frac{1}{S_\alpha(n)} \quad\text{and}\quad \mathbb{E}(E^\beta_n)=\frac{1}{S_\beta(n)} \]

Now let us define the random sets

\[ \mathcal{A}=\left\{\sum_{k=0}^n E^\alpha_k:n\geq0\right\} \quad\text{and}\quad \mathcal{B}=\left\{\sum_{k=0}^n E^\beta_k:n\geq0\right\} \quad\text{and}\quad \mathcal{G}=\mathcal{A}\cup\mathcal{B}. \]

Let \( {\xi_0<\xi_1<\cdots} \) be the reordering of the elements of \( {\mathcal{G}} \). We consider the random sequence \( {{(X_n’)}_{n\geq1}} \) taking values in \( {\{\alpha,\beta\}} \) defined by \( {X_n’=\alpha} \) if \( {\xi_{n-1}\in\mathcal{A}} \) and \( {X_n’=\beta} \) if \( {\xi_{n-1}\in\mathcal{B}} \). The sequences \( {{(X_n’)}_{n\geq1}} \) and \( {{(X_n)}_{n\geq1}} \) have same distribution, and this follows from the properties of exponential distributions (including the lack of memory). Namely, let us examine the equality in distribution of \( {X_1} \) and \( {X’_1} \). If \( {U} \) and \( {V} \) are two independent exponential random variables with respective means \( {1/u} \) and \( {1/v} \) then \( {\mathbb{P}(U<V)=u/(u+v)} \) and \( {\mathbb{P}(V<U)=v/(u+v)} \), which gives

\[ \mathbb{P}(X_1’=\alpha) =\mathbb{P}(\xi_0\in\mathcal{A}) =\mathbb{P}(E^\alpha_0\leq E^\beta_0) =\frac{S_\alpha(0)}{S_\alpha(0)+S_\beta(0)} =\mathbb{P}(X_1=\alpha). \]

The same idea gives (tedious!) the equality in distribution of \( {{(X_n)}_{n\geq1}} \) and \( {{(X_n’)}_{n\geq1}} \). Next, by the zero-one law for the sum of independent exponential random variables,

\[ p:=\mathbb{P}\left(\sum_{n=0}^\infty E^\alpha_n<\infty\right)\in\{0,1\}, \]

with \( {p=1} \) if and only if \( {\varphi_\alpha<\infty} \). The same property holds for the sequence \( {{(E^\beta_n)}_{n\geq0}} \) with \( {\varphi_\beta} \). On the other hand we have the formulas

\[ p_\beta =\mathbb{P}\left(\sum_{n=0}^\infty E^\alpha_n<\sum_{n=0}^\infty E^\beta_n\right) \quad\text{and}\quad p_\alpha =\mathbb{P}\left(\sum_{n=0}^\infty E^\beta_n<\sum_{n=0}^\infty E^\alpha_n\right). \]

Notes and further reading. The content of this post is extracted and translated from a book written with Florent Malrieu in French. Pólya urns are named after the Hungarian mathematician George Pólya. We refer to the books by Hosam Mahmoud, by Norman Johnson and Samuel Kotz, and to the survey articles by Samuel Kotz and Narayanaswamy Balakrishnan, and by Robin Pemantle. Rubin’s theorem can be found in the appendix of a paper by Burgess Davis (suggested to us by Amine Asselah). Pólya urns are fundamental models of reinforcement. They play an important role in learning theory. They are also connected to a class of stochastic algorithms such as the stochastic approximation algorithm of Robbins-Monro, linked with the theory of dynamical systems and attractors. The concept of martingale is a central tool in the stochastic approach of game theory and strategies.

Share
Categories: Probability