Press "Enter" to skip to content

Month: March 2011

Philippe Flajolet

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.

Philippe Flajolet
Philippe Flajolet alias Algorithmix
Leave a Comment

No Dice!


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.

Leave a Comment

Uniform bits

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.

Leave a Comment

Beta laws: arcsine, uniform, semicircle

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.

Leave a Comment