Tag Archives: Lévy

Hackers (par Steven Levy)

Ce soir, j’ai pris un peu de temps (au lieu d’avancer le corrigé pour mon examen) pour finir les dernières pages qui me restaient de L’Ethique des Hackers, traduction en français de Hackers: Heroes of the Computer Revolution, par Steven Levy. Et je vais prendre un peu de temps pour en parler ici, parce que ce livre m’a captivé (et poussé à en acheter d’autres car je suis resté sur ma faim, mais on en reparlera plus loin).

Avant de commencer, pour être honnête, je dois avouer que le style m’a un peu dérouté (surtout au début) et j’ai un peu regretté de ne pas l’avoir acheté en anglais. Le style m’a fait pensé à Tom Holland, par exemple, qui romance énormément l’Histoire. Par moment, on a des doutes, et on se demande s’il n’en fait pas un peu trop, en prêtant à ses personnages des propos fictifs, et imaginés. Mais d’un autre côté, cette humanisation permet de suivre davantage, et de rester accroché tout du long !

La première section est assez incroyable. Surtout pour moi qui connaît peu de choses sur les ordinateurs. Elle parle des hackers de Boston dans les années 60. C’est d’ailleurs fascinant de noter (ça reste vrai assez longtemps dans le livre) que le mot hacker est très souvent associé à hacker de matériel. Autrement dit, les hackers ne font pas du code, ils font avant tout de la soudure, du câblage, et du hardware. On comprend vite pourquoi le Tech Model Railroad Club du MIT – un peu exotique quand on y pense – était au cœur de cette bande ! J’étais content de retrouver des histoires que pouvait raconter André, un informaticien que je côtoyais quand je travaillais à l’INSEE, et qui avait connu l’époque des cartes perforées, et des gros algorithmes pour manipuler un fichier de recensement avec plusieurs dizaines de millions d’enregistrements. Car malgré tout, Levy parle un peu de code et d’algorithme, et surtout de collaboration : les codes sont libres, l’information doit circuler. Bref, Levy parle de choses qui me parlent énormément… Le seul reproche sur cette période est qu’il y a peu de photos.

Par exemple, j’ai découvert l’importance de Spacewar, jeu que l’on voit longuement évoqué… mais je me demandais en permanence: mais à quoi ça peut ressembler un jeu de fusées en 1960 (la seule photo est celle représentée au dessus) ? Eh bien, ça ressemble à ça…

Décevant, non ? un peu je trouve… La première partie est vraiment instructive, mais les étudiants de Boston passent pour des fous, autant prévenir. En fait, j’ai nettement préféré la seconde partie, correspondant aux années 70, sur la côte ouest cette fois, où on quitte le MIT pour Berkeley. D’ailleurs, en lisant cette partie, j’ai regretté de ne pas avoir eu le temps d’aller au Computer History Museum cet été, lorsque nous étions à San Francisco (il va falloir y retourner !).

Dans cette partie, on commence à parler de micro-informatique, de BASIC et de FORTRAN. Et de philosophie de l’informatique. J’y ai découvert la lettre de Bill Gates, datant de 1976 (il a alors tout juste 20 ans) qui pose des questions dont il est question dans tout le livre, sur la propriété des codes, sur les droits d’auteurs… autant de concepts qui me sont totalement étrangers, comme tous ceux qui passent sur le blog doivent noter. Je ne comprends pas quand quelqu’un met des © sur ses graphiques, ou quand quelqu’un me demande la permission d’utiliser mes codes dans ses notes de cours… J’avais eu une discussion avec Marin sur mon utilisation d’images sur mon blog (cela dit, j’ai supprimé mes images de Tintin) mais j’avoue que c’est un sujet qui me dépasse et que je ne comprends pas. Et en ce sens, lire sur le Homebrew Computer Club par exemple m’a permis de mieux comprendre ma philosophie vis à vis de l’informatique… J’ai appris à quel point le logiciel libre (je parle de logiciel, mais dans les années 70, on parle autant de hardware que de software) est au cœur de l’histoire de l’informatique (car plus qu’une histoire de hackers, c’est une histoire de l’informatique que livre Levy). Et au milieu de cette effervescence des années 70, en Californie, des gens comme Bill Gates sont des marginaux,

Toute la seconde partie du livre est réellement fascinante, autour de Steve Wozniak (entre autres) et du libre. La troisième partie est autour des jeux vidéos, et c’est un sujet qui me passionne moins, donc je passerais (même si j’ai appris plein de choses, et que la discussion sur la propriété et les licences commence réellement autour des jeux, on pensera aux pages sur les copies de PacMan pour ordinateurs, inspirés par les versions arcade).

Un bémol est qu’il s’agit de l’histoire américaine de l’informatique. Certes, cela englobe une grande partie de l’histoire, mais quitte à lire sur les logiciels libres, et sur la philosophie des hackers (ce qui Levy appelle éthique), j’aurais bien aimé voir apparaître des gens comme Linus Torvalds voire Eric Raymond. Cela dit, on a déjà 500 pages, et je dois avouer que j’ai appris plein de choses. Mon père m’a fait découvrir l’informatique dans les années 80, je me souviens avoir tapé du BASIC pour faire des jeux, et j’ai découvert l’informatique avant l’époque des logiciels propriétaires. Et je suis content d’avoir appris beaucoup de choses sur cette époque où les propos tenus par Bill Gates étaient les propos que peu de gens tenaient… J’ai aussi aimé lire un livre où le mot hacker n’était pas connoté négativement (je m’étais déjà énervé dans un précédant billet).

Bref, j’ai dévoré cette Ethique des Hackers (il faut dire qu’il fait froid en ce moment à Montréal, et que j’ai tendance à préférer le métro à mon vélo… ce qui me laisse plus de temps pour lire), et je vais probablement continuer, avec Where Wizards Stay Up Late sur l’histoire de l’internet… à suivre donc.

Pour la petite histoire, j’ai pris un coup de vieux le week-end dernier, quand j’ai voulu revoir (avec mon fils) War Games de John Badham (qui date de 1983). Le film m’avait beaucoup impressionné lorsque je l’avais vu, par son caractère science fiction (je pense que la réflexion sur l’utilisation de l’ordinateur m’avait alors échappé). En le revoyant, 30 ans après sa sortie, j’ai eu du mal à expliquer à mon fils ce qu’était une disquette (la 8 pouces, dans le film… même moi je n’ai pas connu ça), ou le bruit que faisait quand on se connectait sur internet… tiens, d’ailleurs, je ne vais pas bouder mon plaisir,

Surtout, dans le film, on y voit qu’un hacker est avant tout un hacker de matériel… tout comme le livre de Levy,

Bref, plusieurs expériences qui m’ont donné envie de me replonger dans l’histoire de l’informatique, pour en savoir plus ! A suivre donc !

Simulation d’un processus de Lévy, et discrétisation

Avec @renaudjf, on discutait l’autre jour de la simulation d’un processus de Lévy. Et on se posait la question d’un algorithme optimal pour combiner un processus de Poisson (ou un process Poisson composé) avec un processus de Wiener (avec éventuellement un drift, voire une diffusion plus générale). En fait, pour générer des processus de Poisson, j’ai toujours eu l’habitude de simuler les durées entre sauts (avec des lois exponentielles, indépendantes, comme dans des vieux billets). Jean François me suggérait d’utiliser une propriété d’uniformité des sauts sur un intervalle de temps donné, conditionnellement aux nombres de sauts.

Commençons par la première piste. On peut générer un processus de Wiener, éventuellement avec un drift, et à coté, on peut générer les lois exponentielles  (qui vont correspondre aux durées entre sauts), et éventuellement aussi des amplitudes de sauts (e.g. des pertes qui suivent des lois exponentielles). On a ici

où . On commence par générer  en notant que

où les incréments  sont Gaussiens (centrés et de variance ) et indépendants les uns des autres. Quant aux durées entre sauts, les  , ce sont des lois exponentielles indépendantes, de moyenne . Voilà le code qui permet de générer les trois composantes,

n=1000
h=1/n
lambda=5
set.seed(2)
W=c(0,cumsum(rnorm(n,sd=sqrt(h))))
W=rexp(100,lambda)
N=sum(cumsum(W)<1)
T=cumsum(W[1:N])
X=-rexp(N)

Le hic est que pour le processus de Wiener, on a du discrétiser, alors que pour le processus de Poisson composé, non. Pourtant, il va bien se ramener sur une même échelle de temps. Une première piste est de créer vraiment la fonction 

Lt=function(t){
W[trunc(n*t)+1]+sum(X[T<=t])+lambda*t
}

et pour faire un dessin ensuite, c’est un jeu d’enfant

L=Vectorize(Lt)
u=seq(0,1,length=n+1)
plot(u,L(u),type="l",col="blue")

Une autre possibilité est d’utiliser une propriété d’uniformité du processus de Poisson que j’évoquais en introduction. Car le processus de Poisson vérifie une propriété remarquable: si  est la date où survient le ième saut, , alors conditionnellement au fait que , les variables  correspondent aux statistiques d’ordres de  variables indépendantes, uniformément distribuées sur , i.e.

Cette propriété se trouve dans Wolff (1982). L’idée de la démonstration est relativement simple. Commençons avec un (unique) saut, alors pour ,

i.e. on retrouve la fonction de répartition d’une loi uniforme sur . On itère ensuite avec 2 sauts, 3 sauts, etc.

La traduction en R de cette idée est tout simplement (car on se place sur )

N=rpois(1,lambda)
T=runif(N)
X=-rexp(N)

Ensuite, une stratégie est de discrétiser le processus de Poisson, avec le même pas de temps que le processus de Wiener,

indice=trunc(T*n)+1
saut=rep(0,n+1)
saut[indice]=X
processus=W+cumsum(saut)+lambda*u

On retrouve la même trajectoire qu’auparavant

plot(u,processus,type="l",col="red")

,,

Sauf qu’on a eu de la chance. Avec cette procédure, il ne faut pas que l’on ait deux sauts dans le même intervalle de temps ! Bon, il est vrai qu’une caractérisation du processus de Poisson est que

et donc on doit avoir très peu de chance d’avoir deux sauts au même instant d’autant plus que le pas de temps est petit. Mais “peu de chance” ne veut pas dire nul, et si on génère des milliers de trajectoires, la probabilité d’avoir une fois un soucis n’est pas négligeable.

Jean-François a eu l’idée brillante de proposer de tirer non pas des lois uniformes sur , mais des lois uniformes discrètes, dans

T=c(0,sort(sample((1:(n-1)/n),size=N,replace=FALSE)))

sans remise afin d’éviter d’avoir deux sauts au même moment. L’idée était séduisante, mais il me restait à etre convaincu que les durées entre sauts… continuaient à être (presque) exponentielles.

Pour ça, on peut faire quelques tests. Par exemple, générer quelques simulations pour avoir une centaines de sauts (et donc une centaine de durées entre sauts), puis faire un test de loi exponentielle (de moyenne )

VT=0
for(ns in 1:20){
N=rpois(1,lambda)
if(N>0){
T=c(0,sort(sample((1:(n-1)/n),size=N,replace=FALSE)))
VT=c(VT,diff(T))
}}

On fait ici 20 boucles car on avait fixé

lambda=5

et j’avais dit que je voulais une centaine d’observations pour faire un test de loi (ce qui est purement arbitraire, on en conviendra). On peut ensuite faire un test d’ajustement de loi exponentielle,

ks.test(VT[-1],"pexp",lambda)$p.value

Si on répète un grand nombre de fois, en changeant le pas de temps (ou le nombre de subdivisons de l’intervalle de temps), on notera qu’effectivement, avec un grand pas de temps (à gauche ci-dessous) on rejette souvent, voire presque toujours, l’hypothèse de loi exponentielle. Mais qu’assez vite, c’est une hypothèse qui n’est pas invraisemblable,

Je ne sais pas entre ces deux fonctions ce qui serait le plus rapide, mais on a deux jolis algorithmes pour générer les processus de Lévy. Non ?

Marc Levy n’utilise que 150 mots ?

L’intérêt des voyages en avion, c’est que ça offre beaucoup de temps pour lire… Et comme j’avais fini mon polar arrivé à Paris, je me suis rabattu sur la version papier de Rue89. Et un article m’a beaucoup plus, où l’on apprenait que les hommes ne pouvaient pas lire Marc Levy… Ne l’ayant jamais lu moi même je ne suis pas apte pour juger, mais une raison évoquée était qu’il utilisait trop peu de mots… En particulier, l’article reprenait une déclaration de François Busnel qui affirmait (ici) “Ces livres sont cousus de fil blanc et écrits avec 150 mots. C’est comme la série Les Feux de l’amour.”

Ah, voilà une affirmation qui m’intéresse en tant que statisticien… combien les écrivains utilisent de mots dans leurs romans…?

Si on regarde Le Voleur d’Ombre, il contient environ 64 000 mots, en tout. Parmi ces mots, on en compte 6 830 uniques (en sachant qu’ici abandonnèrent,abandonne et abandonnait, par exemple, sont considérés comme différents). Le code R est d’ailleurs assez simple,

> livre=scan("Levy-Marc-Le voleur d'ombres.txt", 
+ what=character())
> minlivre=tolower(livre)
> TABLE=rev(sort(table(minlivre)))
> length(TABLE)
[1] 6827
> length(livre)
[1] 64122
> D1=data.frame(mot=names(x),N=as.numeric(x),
+ Freq=as.numeric(x)/sum(x)*100)

(je tiens à préciser que j’ai remplacé les virgules, les points, les apostrophes, etc par des espaces, dans le texte de base afin de récupérer dans le fichier simplement des mots, sans symboles – et j’ai transformé les mots pour n’avoir que des minuscules).

Histoire de comparer avec d’autres auteurs, j’ai pris un auteur plus ancien (pour éviter les soucis de droits d’auteurs, car les textes se trouvent en ligne), à savoir Théophile Gautier, et plus particulièrement son Capitaine Fracasse (oui, on reste dans les pavés). En tout, 127 177 mots, dont 15 595 uniques. Si on compare les courbes de Lorentz, on obtient le graphique suivant,

Les 20 mots les plus fréquents sont (en nombre et surtout en fréquence) respectivement

cbind(D1[1:20,],D2[1:20,])
    mot    N      Freq mot    N      Freq
1    de 2310 3.6025077  de 6284 4.9411450
2    la 1591 2.4812077  et 3862 3.0367126
3    je 1534 2.3923147  la 3720 2.9250572
4     à 1270 1.9805995  le 3235 2.5436989
5    le 1165 1.8168491   à 2429 1.9099365
6    et 1121 1.7482299 les 2214 1.7408808
7   que 1096 1.7092418   d 2192 1.7235821
8     j  889 1.3864196  un 2075 1.6315843
9     l  873 1.3614672   l 2055 1.6158582
10   un  857 1.3365148 une 1678 1.3194210
11   en  780 1.2164312  en 1497 1.1770996
12   me  736 1.1478120  il 1494 1.1747407
13  pas  701 1.0932285 des 1455 1.1440748
14  les  665 1.0370856  se 1178 0.9262681
15   il  654 1.0199308 que 1085 0.8531417
16 elle  653 1.0183712  du 1072 0.8429197
17   tu  596 0.9294782 qui 1064 0.8366293
18   ai  588 0.9170020 son  971 0.7635028
19 dans  549 0.8561804   s  922 0.7249739
20    d  542 0.8452637  qu  915 0.7194697

On retrouve malgré tout que Marc Levy utilise une autre manière d’écrire, qu’il utilise beaucoup le je ou le moi (par rapport à Théophile Gautier). Mais critiquer car il utilise peu de mots me semble un peu léger…. il semble en utiliser autant que des vrais grands écrivains….

Some historical remarks on extreme values

I will start here a short post on extreme values, with some historical perspective. In a recent paper (in French), I mentioned the use of the Pareto distribution as a standard model for extremes, but if reinsurers have been using the Pareto distribution for a long time (see here e.g.), the oldest mathematical models when dealing with extreme value should be related to work on maximum values in finite samples.

  • The work of Ronald Fisher and Leonard Tippett

Leonard Henry Tippett, a former student of Karl Pearson published in Biometrika a note on extremes, in 1925. The goal was “the determination of the distribution of the range and the extremes for a large number of samples“. In 1925, everyone was looking for the Gaussian distribution everywhere, and Leonard Tippett observed that the distribution of the largest value did not have a Gaussian distribution.
A few years after, a joint work with Ronald Fisher was presented to the Cambridge Philosophical Society. The starting point was the idea of “stability” (even if the term did not appear explicitely in their work): the limiting distribution the maximum should be of the “same type” as the underlying distribution. Thus, if https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-01.png stands for the cumulative distribution function, it should satisfy functional equation

https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-02.png

Solutions of that functional equation will give all possible limiting distributions. Thus, Fisher and Tippett obtained three possible limits,

  • solutions of https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-03.png, i.e. https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-04.png
  • solutions of https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-05.png, i.e. https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-06.png with https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-07.png (i.e. finite lower bound for the support), i.e. https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-08.png
  • solutions of https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-05.png, i.e. https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-10.png if https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-11.png (i.e. finite upper bound for the support), i.e. https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-09.png

Based on those possible limiting distributions, Fisher and Tippett wanted to derive what has been called later on the “domain of attraction” of those distributions.

  • The work of Maurice Fréchet, at the same time

In 1926, Maurice Fréchet wrote a paper on “la loi de probabilité de l’écart maximum“. That paper, as well as the one by Fisher and Tippett (wrote at the same time), investigated asymptotic limits. Both obtained functional equations, but only Maurice Fréchet understood the importance of the stability concept, pointed out by Paul Levy in the context of sums. Thus, Maurice Fréchet introduced the concept of what is called now “max-stability“. But Fréchet solve only functional equation https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-05.png. The point is that Fréchet studied absolute values of errors, i.e. strictly positive random variables. Thus, Maurice Fréchet considered distribution

https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-12.png

wherehttps://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-92.png is an arbitrary positive constant. The “2” comes from the fact that Fréchet considered errors with respect to the median. But he did not introduced that new distribution function, he also proved that the distribution appears as a limit when the underlying distribution of the https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-13.png‘s has an algebraic behavior at infinity, i.e. equivalent to https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-90.png, for some https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-91.png. I.e. he proved that Pareto-type tailed distibutions where in the domain of attraction of the Fréchet distribution.

  •  Later on, the work of Emil Gumbel

In 1932, Emil Gumbel gave a talk in France on the “âge limite“. But as he wrote it “on peut donc supposer que la distribution de l’âge limite – c’est à dire la probabilité que la probabilité de cet âge ait une valeur donnée – soit Gaussienne“. But a few years after, he read about Fisher’s work, and observed also that “la distribution d’une valeur extrêmes peut être représentée pour un nombre suffisant d’observations par la formule doublement exponentielle, pourvu que la distribution initiale se comporte asymptotiquement comme une exponentielle. La formule devient rigoureuse si la distribution initiale est exponentielle“, as he wrote in 1935. Thus, as Fréchet proved that Pareto type distribution were in the max-domain of attraction of Fréchet’s distribution, Gumbel obtained that exponential type distributions were in the max-domain of attraction of Gumbel’s distribution. He also introduced the term “distribution de type exponentiel
For Emil Gumbel, it was natural to study the logarithmic derivative of the distribution, since it is the mortality rate in demography (area that Emil Gumbel studied previously). As he mentioned “d’un point de vue théorique, il est intéressant de noter que M. Fréchet a construit une distribution initiale d”une variable aléatoire pour laquelle la valeur absolue de la dérivée logarithmique diminue sans limite“. But since it was not a valuable property for practical applications, he decided that “nous nous bornerons au traitement des données de type exponentiel“. Emil Gumbel always tried to relate his work on extremes and what he did on demograpy.
For instance in 1937, he wrote a paper on “les centennaires” that can also be related to the work of Bortkiewicz on rare events. He also applied his work on radioactivity, and hydrology.
In the 30’s, hydrographs as Hazen or Graszberger introduced the concept of “yearly maximum” of
a river level. They actually proposed to look for actuarial models to study decennial or centennial floods.  But they only used the lognormal distribution to model yearly maxima. In 1936, French hydrologist Aimé Coutagne met Emil Gumbel (who was teaching at the ISFA, in Lyon). At that time, Emil Gumbel was looking for possible applications (outside demography) for his doubly exponential distribution. As as pointed out by Aimé, “sa formule devait être applicable au cas des crues; c’est à dire des plus grands débits, problème analogue à celui des plus grands âges“. Not only Gumbel’s distribution gave better empirical results, but also it came with a theoritical justification.

  • Gumbel’s distribution properties

Consider the Gumbel distribution, with location and scale parameters alpha and beta respectively, i.e.

https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-40.png

Note that the associated quantile function is

https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-41.png

with mean

https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-43.png

and variance

https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-44.png
  • The work of Waloddi Weibull

Waloddi Weibull, a Swedish physict proposed a distribution in 1939, to represent the distribution of breaking strength of materials. He used it in the 50’s in reliability concept. Actually, Weibull appeared late in the story of extremes, since Fréchet, Fisher and Tippett mentioned it already in the mid-20’s.

  • From the central limit theorem (on the average) to Fisher-Tippett theorem (on the maxima)

In order to visualize those two theorem, consider the following animation, where samples of 20 exponential variables are generated. From those 20 values, we plot the maximum in blue, and the average in red, on top. Just below, be rescale those points by considering https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-16.png, and below again, https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-15.png}. When then look at the position of https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-14.png and the one of the mean of https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-15.png. We then build an histogram to visualize the distribution of the rescaled maximum (in blue) and the rescale average (in red).

For those who might be busy, after 1000 generations of samples, we obtain the following histograms (below), including the Gaussian distribution below (i.e. the average of exponential variables looks Gaussian, even with only 20 observations, actually the Gaussian distribution is only asymptotic, i.e. we should consider samples of size 2000), and the maximum over 20 observations of exponential variables (on top) looks like a Gumbel distribution (actually, here it is the exact distribution, and it is the asymptotic distribution for exponential type variables).

  • The GEV distribution

The unified expression of those three distributions is call the GEV distribution. The generalized extreme value distribution has cumulative distribution function

https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-20.png

for https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-21.png, where https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-22.png is the location parameter, https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-23.png the scale parameter and https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-24.png the shape parameter. Note that the expected value is
https://perso.univ-rennes1.fr/arthur.charpentier/latex/ext-30.png