# Month: March 2011

Il y a quelques jours s’éteignait Philippe Flajolet (1948 – 2011). Voilà un  scientifique dont l’âme était aussi grande que l’esprit, et dont la technicité n’occultait pas l’intellectualité. Ils sont si rares, ces personnages à la fois riches, curieux, ouverts, accessibles et attentifs à tous, bien au delà de la comédie humaine. Je mesure à présent la chance que j’ai eu de le rencontrer. C’était aussi un fabuleux conteur (compteur), qui savait faire vibrer l’émerveillement et l’imagination de l’enfance.

Do you use dice as a symbol of randomness in your writings? According to the probabilist David Aldous, this is not a good idea, because “dice are greatly overused, both as a verbal metaphor and as a visual image, and because dice are simply unrepresentative of the way we really do encounter chance in the real world“. He proposes to use for instance dart throws. Personally, I never play darts, and I do believe that dice are  conceptually beautiful and  truly real for  game players. We may also use cards, coins, stocks, … any concrete cultural situation expressing randomness. But nothing replaces the pure and minimalist beauty of dice.

PS : I have learned the Aldous opinion on dice from the probabilist Marc Lelarge.

Last Updated on 2014-06-09

For any ${u\in[0,1]}$, let us consider a binary expansion

$u=0.b_1b_2\ldots=\sum_{n=1}^\infty b_n2^{-n}$

where ${b_1,b_2,\ldots}$ belong to ${\{0,1\}}$ (bits). This expansion is not unique when ${u}$ is rational, e.g.

$0.011111\cdots=0.10000\cdots.$

If ${U}$ is a uniform random variable on ${[0,1]}$ then almost surely, ${U}$ is irrational and its binary expansion is unique with ${b_1,b_2,\ldots}$ independent uniform random variables on ${\{0,1\}}$:

$\mathbb{P}(b_1=\varepsilon_1,\ldots,b_n=\varepsilon_n)=2^{-n}$

for any ${n\geq1}$ and every ${\varepsilon_1,\ldots,\varepsilon_n}$ in ${\{0,1\}}$. Conversely, if ${b_1,b_2,\ldots}$ are independent uniform random variables on ${\{0,1\}}$ then the random variable

$U:=\sum_{n=1}^\infty b_n2^{-n}$

follows the uniform law on ${[0,1]}$. Actually the odd/even separation map

$U=\sum_{n=1}^\infty b_n2^{-n}\mapsto (V_1,V_2):=\left(\sum_{n=1}^\infty b_{2n}2^{-n},\sum_{n=1}^\infty b_{2n-1}2^{-n}\right).$

allows to extract from ${U}$ a couple ${(V_1,V_2)}$ of independent uniform random variables on ${[0,1]}$. More generally, one can extract from ${U}$ a countable family ${{(W_n)}_{n\in\mathbb{Z}}}$ of independent uniform random variables on ${[0,1]}$ by considering the diagonals (or the columns, or the rows) in

$\begin{array}{ccccc} b_1 & b_2 & b_5 & b_{10} & \cdots \\ b_4 & b_3 & b_6 & b_{11} & \cdots \\ b_9 & b_8 & b_7 & b_{12} & \cdots \\ b_{16} & b_{15} & b_{14} & b_{13} & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{array}$

This reduces the simulation of any law to the simulation of the Bernoulli law.

The Beta law on ${[0,1]}$ with parameters ${a>0}$ and ${b>0}$ has density

$x\mapsto \frac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)} x^{a-1}(1-x)^{b-1}\mathbf{1}_{[0,1]}(x).$

This family of laws allows to interpolate between the arcsine law ${a=b=1/2}$ and the semicircle law ${a=b=3/2}$, passing thru the uniform law ${a=b=1}$. It is sometimes more convenient to work on the interval ${[-1,1]}$ instead of ${[0,1]}$. The Jacobi polynomials are orthogonal for this ${(a,b)}$-model. We recover the Chebyshev polynomials of the first and second kind in the arcsine and semicircle cases respectively.

Syntax · Style · .