Tag Archives: random

(A brief) history of randomness, and simulation techniques

Hearing “there is a 10% chance of rain today” or “the medical test has a positive predictive value of 75%” shows that the probabilities are now everywhere. A probability is a quantity that is difficult to grasp, but essential when trying to theorize and measure chance, or randomness. And if mathematical theory finally came very late, as Hacking (2006) points out, this did not prevent insurance from developing early enough, and from having the first (actuarial) mortality tables even before the “probability of death” or “life expectancy” had a mathematical basis. And in the same way, many techniques were invented to “generate randomness“, before the explosion of the so-called Monte Carlo methods, in parallel with the development of computing (and the fact that a machine could generate chance). Continue reading (A brief) history of randomness, and simulation techniques

Reproducibility and randomness

With Stéphane Tufféry, we were working this week on a chapter of a book, entitled Statistical Learning in Actuarial Science. The chapter should be based on R functions, and we wanted to reproduce some outputs he previously obtained with SAS. The good thing is that even complex functions (logistic regression, regression trees, etc) produce the same kind of outputs. But we found a problem that we could not fix: generating identical training subsets of observations… Out of 1,000 lines, we subsample about 600 lines. The problem is that we could not generate the same sets of indexes with R, and SAS. Even using similar random generators… (execpt if we want to extract 1 or 2 lines, no more).

Let us try to explain what’s going on (based on code produced by Stéphane). According to Eubank (2010), there are (at least) two generators of random numbers in SAS,

For instance, for the RAND function, if we generate a Gaussian sample – with Mersenne-Twister algorithm – the code should be

%LET SEED =6;
%LET NREP=10;
DATA TESTRANDOM ;
  CALL STREAMINIT(&SEED);
  DO REP = 1 TO &NREP;
   X = RAND ('NORMAL'); 
   OUTPUT;
  END;
RUN;
PROC PRINT DATA = TESTRANDOM ;
RUN ;

And we get here

Obs. REP X
1 1 2.10680
2 2 -0.25604
3 3 0.28692
4 4 -0.22806
5 5 1.34569
6 6 0.16341
7 7 -0.27788
8 8 0.02133
9 9 1.24050
10 10 1.01054

 

If we want a Uniform sample, it should be

%LET SEED =6;
%LET NREP=10;
DATA TESTRANDM ;
CALL STREAMINIT(&SEED);
DO REP = 1 TO &NREP;
  X = RAND ('UNIFORM'); 
  OUTPUT;
END;
RUN;
PROC PRINT DATA = TESTRANDOM ;
RUN ;
Obs. REP X
1 1 0.66097
2 2 0.48044
3 3 0.87849
4 4 0.19916
5 5 0.04838
6 6 0.19966
7 7 0.81353
8 8 0.53807
9 9 0.01105
10 10 0.53753

On good thing (so far) about the latest, is that Mersenne-Twister has been coded in R, in the RNGkind function

> RNGkind("Mersenne")
> set.seed(6)
> runif(10)
 [1] 0.64357277 0.91590888 0.09523258 0.29537280
 [5] 0.76993170 0.25589353 0.51789573 0.67784993
 [9] 0.14722782 0.70052604

But the output is different, even if we’re supposed to start, here, with the same seed. Now, if we want to make sure about what is done here, let us write our own codes of the Fishman and Moore (1982) algorithm (in order to reproduce the SAS output). The R version of

> a = 397204094      # RANUNI multiplier
> seed = 123         # seed
> n = 10             # sample size
> m = (2^31) - 1     # period
> for (i in (1:n-1)) {
+ seed = (a*seed)%%m
+ u = seed / m
+ print(u)
+ }
[1] 0.7503961
[1] 0.3209121
[1] 0.3453204
[1] 0.2683455
[1] 0.241798
[1] 0.9888181
[1] 0.3943279
[1] 0.9710172
[1] 0.001632214
[1] 0.921537

Let us now run a similar code with SAS,

%LET SEED =123;
%LET NREP=10;
DATA FRANUNI (KEEP = x) ;
seed = &SEED ;
DO REP = 1 TO &NREP;
  CALL RANUNI(seed, x);
  OUTPUT;
END;
RUN;
PROC PRINT DATA = FRANUNI ;
RUN ;

and we get the following output

Obs. x
1 0.75040
2 0.32091
3 0.17839
4 0.90603
5 0.35712
6 0.22111
7 0.78644
8 0.39808
9 0.12467
10 0.18769

It looks like here, indeed, we start with the same seed, since the first two numbers generated are similar. But then, it looks like we really have random numbers… If we change the seed, the first two numbers are similar, but that’s all.

We might be missing something trivial here, but we did not see it. So if anyone has a clue about reproducibility issues when generating random samples, with R and SAS, we are interested !

Martingale et journalisme scientifique

Être journaliste scientifique ne doit pas être facile. J’imagine qu’il faut être à l’écoute des nouvelles scientifiques, et d’informer, aussi justement que possible. C’est ce que fait avec brio Pierre Barthélémy (aka @PasseurSciences sur Twitter) dans sa chronique hebdomadaire sélection scientifique de la semaine. Il essaye ainsi de parler de sciences dans un journal qui a (trop) souvent confondu science et technologie (technologie étant aussi souvent un mot savant utilisé pour masquer de la publicité pour des appareils technologiques avancés). Et comme l’espace qui lui est imparti est restreint (c’est le moins qu’on puisse dire), la plupart des informations passent par son blog http://passeurdesciences.blog.lemonde.fr/, qui est riche ! Sylvestre Huet fait aussi ce travail pour Libération, avec son blog http://sciences.blogs.liberation.fr/ (là encore, on peut lire bien plus de choses en ligne que que dans la version papier, ce qui est d’autant plus intéressant pour les lecteurs de l’autre coté de l’océan atlantique). Sylvestre Huet arrive à parler géologie, puis démographie, avant d’évoquer dans un article truffé de références les réformes des instances qui régentent la recherche en France. Oui, les deux blogs sont malgré tout très français. Pour une vision plus internationale, on pourra citer l’admirable travail de Pascal Lapointe, par exemple (aka @paslap) sur http://sciencepresse.qc.ca/.

Mais si je commence à mettre les pieds dans le plat, je poserais la question de la légitimité d’un journaliste scientifique, à l’heure où la blogosphère scientifique explose. Par exemple, si je veux apprendre des choses en physique, ou en biologie, je sais que le blog de Tom Roud (que l’on peut suivre sur Twitter @tomroud) http://tomroud.cafe-sciences.org est une source infinie d’information (ok, peut-être pas “infinie” car comme nous tous, il a une vie en dehors de son blog, mais disons qu’il y a de quoi lire). En sciences humaines, il existe des centaines de blogs hébergés sur http://hypotheses.org/ tenus par des universitaires, ou http://www.cafe-sciences.org/ pour des blogs de sciences, en français. Les bloggers scientifiques s’expriment – le plus souvent – en restant dans leur champ d’expertise. Et c’est tant mieux. Le journaliste scientifique, lui, se doit de parler de tous les sujets scientifiques. Et c’est là que l’exercice devient délicat, car le journaliste se doit d’être critique. Compte tenu de la concurrence féroce qui existe dans le monde académique, on nous pousse à faire croire qu’on vient d’écrire l’article qui va révolutionner la science, sinon le monde. Que notre approche est novatrice, et qu’en plus, on vient de montrer ce qui pourrait ce qui pourrait être le sain Graal dans notre communauté. C’est le travail du journaliste de se demander si c’est vrai….

J’en arrive au point de mon billet. Le dernier article  le hasard, martingale boursière ? (en ligne sur http://lemonde.fr/sciences/…) de Pierre Barthélémy m’a un peu agacé. Pas sur le thème abordé, mais l’impression générale qui m’est restée après avoir lu l’article (samedi matin). Pour l’histoire complète, c’est ma femme qui est tombée la première sur l’article, et qui a été étonnée de lire un article pareil dans Le Monde, en tant que mathématicienne (et probabiliste). Et quand je l’ai lu, c’est en tant qu’économiste que je suis resté sans voix. En résumé (trop succinct, j’en convient), on nous résume l’article de physiciens italiens qui “expliquent qu’au grand dam des traders et autres analystes financiers, en quête perpétuelle de justifications rationnelles aux fluctuations des cours boursiers, les marchés demeurent obstinément imprévisibles“. Pour parcourir l’article mentionné, mais non cité – probablement car il s’agit de la version papier ? – l’article est en ligne sur http://arxiv.org/1303.4351  (trouvé via http://improbable.com/…). On retrouve cette idée dans le texte sous la forme suivante “our main result, which is independent of the market considered, is that standard trading strategies and their algorithms, based on the past history of the time series, although have occasionally the chance to be successful inside small temporal windows, on a large temporal scale, perform on average not better than the purely random strategy, which, on the other hand, is also much less volatile. In this respect, for the individual trader, a purely random strategy represents a costless alternative to expensive professional financial consulting, being at the same time also much less risky, if compared to the other trading strategies.” On apprend dans l’article paru dans Le Monde que “pour Pluchino et compagnie, le CAC 40 est une loterie, ce que les spécialistes ne veulent pas admettre“. Damned, rien que ça ? Pour les amateurs de lyrisme (il doit y en avoir dans les lecteurs du monde, moins parmi les lecteurs plus scientifiques qui aiment les phrases moins alambiquées), je passe les moments où Pierre Barthélémy est clairement plus journaliste que scientifique, comme lorsqu’il nous explique que ces quatre chercheurs “viennent d ‘attaquer à l’acide de l’aléatoire” les modèles financiers. Cela dit, cela a le mérite de mettre les points sur les i: ce sont des physiciens. Pas des économistes.

Je pense qu’il y a des milliers de raisons d’attaquer les traders (si ce sont bien les “spécialistes” visés). Mais qu’on ne les prenne pas pour plus bêtes qu’ils ne le sont (je le dis d’autant plus volontiers que j’en ai formé un paquet, à l’ENSAE ou à Polytechnique, au cours des 10 dernières années).

Avant de revenir sur la petite histoire de martingale financière (tel que le résume le titre de l’article) faisons un court détour par celle brillamment racontée dans Mansuy (en ligne sur http://math.harvard.edu/~ctm/… et traduit en anglais dans http://jehps.net/Mansuy.pdf) sur l’origine de la notion de martingale. D’un point de vue mathématique (disons comme propriété des processus stochastiques), il faut remonter aux travaux de Joseph Bernstein, Paul Lévy, Émile Borel, et surtout Joseph Leo Doob, au milieu au XXième siècle. Cela dit, le mot est plus ancien: il entre dans le dictionnaire de l’Académie Française en 1762. Jouer à la martingale, c’est jouer toujours tout ce que l’on a perdu.  Mais quelques années plus tot, on pouvait déjà trouver le mot sous la plume de l’Abbé Prévost (le jeu qu’il décrit en 1750 comme variante du jeu du pharaon est aussi appelé martingale d’Alembert) Cela dit, l’origine que je préfère est de relier le mot martingale à l’expression provençale “jouga a la martegalo” qui signifierait jouer de manière incompréhensible, absurde, comme l’évoque Frédéric Mistral dans Lou Tresor dòu Felibrige ou dictionnaire provençal-français. On retrouve une origine proche dans le dictionarie of the French and English tongues de Randle Cotgrave, datant de 1611, qui mentionne l’expression “à la martingale” avec le sens absurdly, foolishly, untowardly, grossely, rudely, in the homeliest manner. Il cite même l’usage de l’expression philosopher à la martingale (sans citer Bernard Henri Levy, mais il semble que ce soit l’idée). Cela dit, même dans Lapinot on parle de martingale,

Bref, à partir de ce comportement incompréhensible, voire absurde, des économistes vont définir une notion importante en finance, que l’on appellera efficience (qui est un mot dangereux car il évoque aux oreilles de tous les économiste une notion d’optimalité au sens de Pareto, on pourra relire Malkiel (2003) The Efficient Market Hypothesis and Its Critics sur ce point). L’idée d’utiliser une marche aléatoire pour modéliser le cours d’un actif est ancienne. Par exemple (je ne remontrais pas au XVIème siècle, mais http://e-m-h.org/history.html le suggère) on pourra relire les travaux de Bachelier datant du début du XXième siècle, mais comme le dit la légende, Bachelier a été peu lu, à l’époque (en tous les cas par des économistes). Publié quelques années plus tard, on pourra relire Cowles & Jones (1937), Some A Posteriori Probabilities in Stock Market ou surtout Samuelson (1965) Proof That Properly Anticipated Prices Fluctuate Randomly. Cet article est passionnant, si on prend le temps de le lire “There is no way of making an expected profit by extrapolating past changes in the future price, by chart or any other esoteric devices of magic or mathematics.” Paul Samuelson est d’une modestie remarquable pour un chercheur, “I have not here discussed what the basic probability distributions are supposed to come from. In whose mind are they ex ante? Is there any ex post validation of them? Are they supposed to belong to the market as a whole? And what does that mean? Are they supposed to belong to the “representative individual”, and who is he? Are there some defensible or necessitous compromises of divergent anticipations patterns? Do price quotations somehow produce a Pareto-optimal configuration of ex ante subjective probabilities? This paper has not attempted to pronounce on these interesting questions“. Il peut y avoir des bulles, des processus non Gaussien, un peu tout ce qu’on peut imaginer, le point important étant qu’il est impossible d’utiliser le passé pour prédire le futur, en finance.

Oui, depuis 50 ans, les économistes savent que la marche aléatoire peut être un bon modèle pour décrire le prix des actifs. Ou pour être plus précis (et rendre à Paul Samuelson ce que Paul Samuelson a dit le premier) les martingales. Mais il faudra surtout attendre les travaux d’Eugène Fama, en particulier Fama (1965) The Behavior of Stock Market Prices et Fama (1970) Efficient Capital Markets: A Review of Theory and Empirical Work, qui vont de manière définitive marquer le début de l’utilisation des martingales en finance. Eugène Fama y retient trois notions d’efficience (pour aller plus loin que le fameux “A market in which prices at any time “fully reflect” available information is called “efficient”“)

  1. Expected Returns or “Fair Game” Models
  2. Submartingale Models
  3. Random Walk Model

(en 1965, l’efficience devait être reliée, pour Eugène Fama, à la notion de marche aléatoire, alors que Paul Samuelson utilisait déjà la notion de martingale). Ces modèles disent tous (on est en 1970) qu’il est inutile d’utiliser l’information passée ou présente “to predict the future in a way which makes expected profits greater than they would be under a naive buy-and-hold model“. N’en déplaise à Pierre Barthélémy , depuis presque 50 ans ce principe est énoncé dans les cours d’asset pricing. Bachelier disait la meme chose en 1900, “l’espérance mathématique du spéculateur est nulle” dans Théorie de la spéculation. Et cela sera confirmé quelques années plus tard par les résultats empiriques de Cowles et Jones. Un an plus tard sera publié Black (1971) Implications of the random walk hypothesis for portfolio management, et trois ans plus tard, Hagerman & Richmond (1973) Random Walks, Martingales and the OTC. La littérature économique va se multiplier pendant les années 70, à tel point qu’en 1978, Michael Jensen, alors professeur à Harvard écrivait “I believe there is no other proposition in economics which has more solid empirical evidence supporting it than the Efficient Market Hypothesis” (cité dans http://economist.com/14030296). Plus récemment, à la fin des années 80 était publié le remarquable LeRoy (1989) Efficient Capital Markets and Martingales, qui étoffait la critique initiée dans LeRoy (1976). Efficient capital markets: Comment. LeRoy et Samuelson ont été les premiers à parler de martingale pour modéliser les prix des actifs. On continue (avec les articles qui font référence, et que tous les étudiants qui ont suivi un cours d’asset pricing ont lu) ? L’année suivante était publié Lehman (1990) Fads, Martingales, and Market Efficiency. Les martingales sont des outils incroyablement riches. Ils ne sont pas équivalent à une marche aléatoire: on peut avoir une martingale, sans avoir de marche aléatoire (par exemple avec un processus ARCH, on pourra relire sur le sujet les notes de cours Predictability of Asset Returns, en particulier le premier paragraphe, ou en français, avec des cours de licence, par Francis Diener,  http://math.unice.fr/~diener/…). Pour ceux qui veulent moins de formalisme, une martingale (en simplifant outrageusement) c’est, comme l’explique Nicolas Poupon,

Mais ces articles posent essentiellement les bases de la théorie financière. Qu’en est-il des aspects empiriques ? Andrew Lo et Craig MacKinlay ont publié un livre, en 2001, qui recense plusieurs articles sur le sujet, A Non-Random Walk Down Wall Street. Qui remet en cause l’idée de marche aléatoire, moins celle de marginale. On pourra aussi penser à Beechey Gruen & Vickrey (2000) et leur étude The Efficient Markets Hypothesis: A Survey, en ligne sur la Reserve Bank of Australia. Enfin, Pour une méthodologie plus proche de celle évoquée dans l’article en ligne sur arxiv, on pourra lire Martingales, the Efficient Market Hypothesis, and Spurious Stylized Facts de Joseph McCauley, Kevin Bassler et Gemunu Gunaratne (si on souhaite aussi utiliser des propriétés de mémoire longue). Moralité ? Non, ce n’est pas nouveau que l’on teste l’hypothèse d’efficience et de martingale. Et si je cite des articles académiques, il faut  ajouter que les journalistes économiques connaissent également cette littérature. Il y a 10 ans, Justin Fox posait la même question que nos chercheurs dans un article dans Fortune intitulé Is The Market Rational ? No, say the experts. But neither are you–so don’t go thinking you can outsmart it. On pourra aussi relire Efficiency and beyond (mentionné auparavant) qui revient sur la notion d’efficience des marchés. On y retrouve que les spécialistes savent tout ca: “on such ideas, and on the complex mathematics that described them [i.e martingales], was founded the Wall Street profession of financial engineering“. Enfin, en 2009, Richard Thaler faisait quelques rappels sur la difficulté d’interpréter correctement l’hypothèse d’efficience des marchés dans Markets can be wrong and the price is not always right. Pour conclure sur l’histoire des martingales en finance, en 2010, Fama répondait d’ailleurs de manière très claire à la question dans une interview – interview with Eugene Fama – lorsque John Cassidy lui demandait “the fundamental insight of the efficient market hypothesis [is] that you can’t beat the market ?“, et qu’il répondait “Right—that’s the practical insight. No matter what research gets done, that one always looks good“.

Pour revenir sur l’article de Pierre Barthélémy, je trouve qu’écrire “le CAC 40 est une loterie, ce que les spécialistes ne veulent pas admettre” est incroyablement méprisant envers des centaines, pour ne pas dire des milliers de chercheurs en mathématiques financières, et en économétrie de la finance. Mais rassure toi Pierre, je vais continuer à lire tes chroniques. C’est juste que ma grand mère est encore abonnée au Monde, et j’aimerais bien qu’elle continue de croire que je peux sauver l’humanité (et non pas que je refuse d’admettre ce que des chercheurs italiens viennent d’établir, même si cela confirmerait – à ses yeux – que je peux etre têtu comme une mule quand je veux).

Maintenant, pour conclure sur l’article mentionné, et sur l’analyse faite, on ne peut pas dire que les conclusions soient révolutionnaires. Disons, pour quiconque ayant lu un peu de littérature économique dans les 50 dernières années. En fait, pour être honnête, je pense qu’on peut dire que Alessandro Pluchino et Andrea Rapisarda se sont amusé (on inclura Biondo et Helbing). Sans plus de prétention. Pour ceux qui ne se souviennent pas, ils avaient eu un IGNobel en 2011, pour leur étude sur organizations would become more efficient if they promoted people at random. J’avais aussi beaucoup aimé leur article sur les aspects computationnels du principe de Peter, en ligne sur http://arxiv.org/0907.0455. Quand je lis leurs études, j’ai l’impression qu’ils s’amusent. Et le terme n’est absolument pas péjoratif dans ma bouche, loin de là. C’est un peu ce que disait Lucile Quillet la semaine passée dans http://etudiant.lefigaro.fr/…  lorsqu’en mentionnant une étude de Baptiste Coulmont, elle écrivait “c’est le jeu auquel c’est amusé Baptiste Coulmont sur son blog“. Je ne sais pas si le terme était voulu, si c’était basé sur le fait qu’un blog, c’est fait pour jouer… mais j’ai toujours revendiqué que je faisais de la recherche pour mon plaisir, pour m’amuser. Et comme me le rappelait Baptiste, le mot schola signifie école, en latin, et son étymologie grecque est le mot σχολή, signifiant loisir.

Bristish Statisticians and American Gangsters

A few months ago, I did publish a post (in French) following my reading of Leonard Mlodinow’s the Drunkard’s Walk. More precisely, I mentioned a paragraph that I found extremely informative

http://freakonometrics.hypotheses.org/files/2013/02/Capture-d%E2%80%99e%CC%81cran-2013-02-18-a%CC%80-13.27.42.png

But it looks like those gangsters were not only stealing money. They were also stealing ideas, here from a British statistician, manely Leonard Henry Caleb Tippett. Leonard Tippett is famous in Extreme Value Theory for his theorem (the so-called Fisher-Tippett theorem, which gives the possible limiting distributions for a normalized version of the maximum from an i.i.d. sequence, see old posts). According to Martin Gardner, Leonard Tippett suggested to use middle numbers (not the last ones) of larger ones to generate (pseudo) random sequences, or more precisely, in 1927, “published a table of 41,600 random numbers, obtained by taking the middle digits of the area of parishes in England

http://freakonometrics.hypotheses.org/files/2013/02/Capture-d%E2%80%99e%CC%81cran-2013-02-18-a%CC%80-11.34.23.png

I could not get a copy of the book Random Sampling Numbers by Leonard Tippett (I could only find reviews, e.g. Nair (1938)) but I do believe that this technique should work to generate sequences that do look like sequences of random numbers. Note that several techniques were mentioned in previous posts (in French) published a few years ago.

Now, I should also take some time to apologize because, sometimes, I am the one playing the gangster: I do steal a lot of illustrations on the internet. And I would like to apologize to the authors. On my previous blog, I did try – once – to add a short line at the end of a post, explaining where the illustration was coming from (trying to give credit to the illustrator). Less than 10 days after adding this short line, I received an email from a ‘publisher’, telling me that there were rights attached to the picture, and that I had 24 hours to remove it (if not, their lawyers will see what to do). Of course, I did remove the picture, and the mention. Now, I use pictures, and no mention. And I feel guilty. So I wanted to apologize for stealing others’ work. I am still discussing to hire an illustrator, to illustrate my blog. Work in progress….

De la difficulté de générer du hasard

J’avais parlé cet été de l’utilisation des chiffres du us treasury balance comme générateur (involontaire) de nombres aléatoires. Cet été, un débat intéressant a secoué le Québec, suite à la plainte déposée par deux joueurs (compulsifs) de l’Extra. L’histoire est raconté en détails sur le site de canoe.ca, ou de lapresse.ca. Le jeu est assez simple. L’histoire un peu moins (c’est pour cela que j’ai préféré renvoyer vers deux sources racontant la même histoire). Pour essayer d’expliquer simplement ce qui s’est passé revenons un peu sur le jeu. Tous les jours, Loto-Québec tire au hasard un nombre de 7 chiffres.

http://freakonometrics.hypotheses.org/files/2015/12/extra06.gif

Comme on le voit ci-dessus, le but est d’avoir les premiers (ou les derniers) chiffres bons.
Quand on achète un ticket, un numéro nous est attribué… et on espère qu’il sera tiré le soir. Mais le soucis est que les joueurs qui intentent un procès n’achetaient pas un mais dix tickets. Et étrangement, à chaque fois, ils avaient un ticket gagnant, et un seul.
En fait, quand on achetait dix combinaisons d’extra, il semble que le premier chiffre sans remise parmi 0 à 9, les cinq suivants avec remise parmi 0 à 9 et le dernier sans remise parmi 0 à 9 (pour reprendre la formulation qu’a utilisé Christian Léger de l’UdM pour me l’expliquer). Sur un achat, on ne voit rien, on a des nombres uniforme… mais avec répétition, ça se complique.
En fait, c’est toujours quand on étudie la dynamique des générateurs de nombres aléatoires que l’on a des surprises.
Par exemple sur les tirages de l’extra (et non pas les numéros des combinaisons des billets, car on ne les trouve pas sur internet, il faudrait acheter les billets pour refaire l’expérience). On peut récupérer l’historique des tirages en ligne, sur le site de loto-quebec.com.

> extra=read.table("http://freakonometrics.blog.
free.fr/public/data/extra-loto-quebec.csv",sep=";",header=TRUE)
> n=1940
> extra=extra[1:(n-1),1:2]
> X=extra[,2]/10000000
Si on regarde les 1940 derniers tirages (car avant, il semble qu’il n’y avait pas 7 mais 6 chiffres), on a la série suivante,

Et un test d’uniformité semble confirmer l’intuition que les nombres sont uniformément répartis,
> ks.test(X,'punif')

	One-sample Kolmogorov-Smirnov test

data:  X 
D = 0.021, p-value = 0.3895
alternative hypothesis: two-sided

Mais générer du hasard, ça n’est pas que ça… Et sur cette série, si on fait des tests sur l’indépendance des observations, on est un peu surpris,

> library(lawstat)
> runs.test(X, plot.it = FALSE, alternative = "two.sided")

	Runs Test - Two sided

data:  X 
Standardized Runs Statistic = -1.8, p-value = 0.07273

> runs.test(X, plot.it = FALSE, alternative = "positive.correlated")

	Runs Test - Positive Correlated

data:  X 
Standardized Runs Statistic = -1.8, p-value = 0.03637

> library(FitAR)
> LjungBoxTest(qnorm(X), k=0, lag.max=12, 
+ StartLag=1, SquaredQ=FALSE)
  m   Qm pvalue
  1  7.2 0.0075
  2  9.2 0.0102
  3 10.9 0.0125
  4 10.9 0.0276
  5 15.3 0.0090
  6 15.4 0.0171
  7 16.1 0.0244
  8 16.3 0.0380
  9 16.7 0.0538
 10 20.6 0.0240
 11 20.8 0.0357
 12 20.8 0.0533

A Million Random Digits: review of reviews

Recently on his blog (here), Robin mentioned an amazing book, called “A Million Random Digits” published by RAND corporation. The book was initially published in 1955, but RAND published a nice (and expensive) second edition.

A great thing is that on Amazon, there are several extremely interesting reviews of the book. E.g.

4.0 out of 5 stars Didn’t like the ending, February 10, 2009  By Damien Katz

Even though I didn’t really see it coming, the ending was kind of anti-climatic. But overall the book held my attention and I really liked the “10034 56429 234088” part. It’s nice to know I’m not the only one who feels that way.

5.0 out of 5 stars I found a typo, September 14, 2007  By fanfan

To whom do I write to report typographical errors? I noticed that the first “7” on the third line page 48 should be a “3”. The “7” that’s printed there now isn’t random. Other than that, this is really an excellent book.

5.0 out of 5 stars Superb and original plot, April 21, 2007  By Herr Tarquin Biskuitfaß

This one has a very unpredictable plot, sublime character development in a style that stubbornly defies any sort of development in its rare and iconoclastic brilliance, and is told remarkably with numbers instead of letters. Take, for example, this passage on page 202, “98783 24838 39793 80954”. I’m speechless. The symmetry is reminiscent of the I Ching, and it approaches a rare spiritual niveau lacking in American literature. It not only reads well, but it looks great too. I have a tattoo of page 214 on my arm, and I’m hoping to get 202 on my belly to celebrate my next birthday. It is an injustice that Rand Corporation has not received the Nobel Prize for Literature, nor even a Pulitzer.

3.0 out of 5 stars A serious reference work?, October 16, 2006  By BJ

For a supposedly serious reference work the omission of an index is a major impediment. I hope this will be corrected in the next edition.

1.0 out of 5 stars Not Nearly A Million, September 3, 2006  By Liron

This book does not even come close to delivering on its promise of one million random digits. My expectations were high after reading the first sentence, which contained ten unique digits. However, the author seems to have exhasted his creativity in this initial burst, because the other 99.999% of the book is filler in which those same ten digits are shamelessly reused!  If you are looking for a larger offering of numerals in various bases, I highly recommend “Peter Rabbit’s ABC and 123”.

3.0 out of 5 stars Wait for the audiobook version, October 19, 2006  By R. Rosini “Newtype”

While the printed version is good, I would have expected the publisher to have an audiobook version as well. A perfect companion for one’s Ipod.

5.0 out of 5 stars Wait for it…, February 10, 2009  By Cranky Yankee

It started off slow, single digit slow in the beginning but I stuck with it. I eventually learned all about the different numbers, 1,2,3,4,5,6,7,8,9 and 0 and their different combinations.  The author introduced them all a bit too quickly for my taste. I would have been perfectly happy with just 1,2,3,4 and 5 for the first 20,000 digits, but then again, I’m not a famous random-number author, am I?  After a while, patterns emerged and the true nature of the multiverse was revealed to me, and the jokes were kinda funny. I don’t want to spoil anything but you will LOVE the twist ending!  Like 4352204 said to 64231234, “2242 6575 0013 2829!”

Ok, I have to admit I tried to check a few of them (that’s my freaky part). For instance the first one is a fake: the two first numbers – for instance – never show up together (consecutively),

> DIGIT=read.table("
+ http://freakonometrics.blog.free.fr/public/data/digits.txt")
> DIGIT=DIGIT[,2:11]
> k=1
> I=apply(DIGIT[,1:2]==c(10034,56429),1,sum)==2
> for(k in 2:9){
+ I=cbind(I,apply(DIGIT[,k+0:1]==c(10034,56429),1,sum)==2)
+ }
> I0=which(apply(I,1,sum)>0)
> DIGIT[I0,]
 [1] V2  V3  V4  V5  V6  V7  V8  V9  V10 V11
<0 rows> (or 0-length row.names)

Nevertheless, I did have some fun reading those reviews. About the book, unfortunately I have to confess I stopped after 99998 appeared (the first time).

Passer des cassettes aux mp3

Plus le temps passe, plus j’ai l’impression d’être un dinosaure…. Lorsque j’étais jeune, j’écoutais de la musique sur des cassettes1. Je me souviens même avoir été enchanté par l’arrivée du premier walkman réversible: on n’était alors plus obligé de tourner la cassette au bout de 20 minutes. Quand soudain, à la fin des années 80 est arrivé le compact disc, et les lecteurs avec leur fonction Random ou Shuffle..

J’aurais du me douter que je tournerais mal parce que je me souviens avoir joué avec la platine de mes parents, en essayant de voir si la première chanson pouvait passer en premier avec une lecture aléatoire, mais aussi la seconde pouvait passer juste après. Bon, avec le recul, je me rends compte que j’ai du beaucoup user la platine parce qu’avec un disque de 10 titres, il faut 90 (ou 100) essais (en moyenne) pour qu’une lecture aléatoire commence effectivement par 1 et 2. C’est d’ailleurs à ce moment que j’ai aussi découvert les tirages avec et sans remises: avec certaines platines, on ne pouvait pas obtenir deux fois le même titre, alors que d’autres oui.
Puis sont arrivés les lecteurs mp3, où on n’avait plus 10 titres tirés au hasard, mais 200 voire 1000. Et l’autre jour en courant, je me suis posé les mêmes questions que lorsque j’étais tout petit (oui, je suis un dinosaure, mais j’étais jeune à cette époque): si le lecteur propose une fonction random avec remise, combien de chansons dois-je attendre, en moyenne, avant de réentendre une chanson que j’avais déjà entendu ?

  • De la probabilité d’entendre deux fois une chanson ?

Pour faire un peu formel, supposons que mon lecteur contienne https://perso.univ-rennes1.fr/arthur.charpentier/latex/mp301.png chansons.
La probabilité de n’avoir aucune répétition sur https://perso.univ-rennes1.fr/arthur.charpentier/latex/mp302.png lectures (on suppose https://perso.univ-rennes1.fr/arthur.charpentier/latex/mp303.png) est

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

qui correspond aussi au nombre d’arrangements de https://perso.univ-rennes1.fr/arthur.charpentier/latex/mp302.png éléments parmi https://perso.univ-rennes1.fr/arthur.charpentier/latex/mp301.png, divisé par https://perso.univ-rennes1.fr/arthur.charpentier/latex/mp305.png, soit

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

Si le ratio est faible (ou n est grand), on peut utiliser l’approximation https://perso.univ-rennes1.fr/arthur.charpentier/latex/mp307.png et donc la probabilité s’approche par

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

soit tout simplement – toujours en cherchant une approximation – une probabilité de n’avoir aucune répétition de

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

Si on se donne une probabilité de n’avoir aucune répétition de https://perso.univ-rennes1.fr/arthur.charpentier/latex/mp310.png, alors

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

Avec https://perso.univ-rennes1.fr/arthur.charpentier/latex/mp301.png=200 chansons sur mon lecteur mp3, en jouant 17 titres, j’ai environ 1 chance sur 2 d’avoir au moins un titre joué deux fois. Et 17 chansons, ça correspond à ce que j’écoute en faisant mon jogging…. Bref, le temps de faire mon jogging, j’ai 1 chance sur 2 d’entendre un titre deux fois.
Mais que se passerait-il si je tenais le raisonnement inverse ?

  • Problème dual et jogging interminable….

Autrement dit, combien de temps vais-je courir si je décide de m’arrêter lorsque j’entends (pour la première fois) un titre pour la seconde fois ? En fait, Donald Knuth en parle un peu dans son livre the art of computer programming: on peut montrer que l’espérance du nombre de titres qu’il faudra jouer pour avoir une première répétition parmi n titres est de la forme

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

qui admet un développement asymptotique

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

soit, toujours avec 200 titres dans mon lecteur, une vingtaine de titres à jouer, en moyenne. Ce qui rallongera un peu mon jogging, finalement…

> n=200
> sqrt(2*n*log(2))
[1] 16.65109
> 1+sqrt(pi*n/2)-1/3+1/12*sqrt(pi/2*n)-4/135/n
[1] 19.8681

Formellement, le premier correspond à une médiane, alors que le second à une espérance. Ce qui explique la différence.
Notons que si mon jogging classique dure la durée de 17 titres, la probabilité d’avoir un jogging deux fois plus long est quand même d’une chance sur 10,

> k=31
> exp(-k*(k-1)/(2*n))
[1] 0.09778344
> sqrt(2*n*log(1/.01))
[1] 42.91932

autrement dit, j’ai une chance sur 100 (ce qui devrait donc arriver une fois dans l’année, en moyenne) de courir pendant 43 chansons… qui vont me paraître très très longues….

1 je passais mon temps l’oreille sur la radio (car j’ai connu les premières radios libres, comme on disait alors), prêt à enregistrer dès qu’une super chanson passait.. je me souviens avoir guetter des jours durant le passage de you spin me around (ici) que mes élèves (qui n’ont pas connu cette époque) ou les cinéphiles connaissent probablement seulement sous la version right round () qui a abondamment samplé le thème. Oui, je suis un dinosaure..

"Générer" du hasard, partie 5

La dernière méthode que  je présenterais est est celle des générateurs congruentiels linéaires. On retrouve l’idée de linéarité que l’on avait pas exemple dans le premier générateur proposé (ici), la notion de congruence est liée à des problèmes d’arithmétique et d’écriture de nombres dans les bases. On retiendra une fonction de récurrence de la forme suivante

X_{n+1} = (a cdot X_n + c) mod m

Pour que l’algorithme marche bien, on essaye de partir d’une valeur initiale correspondant à un nombre premier.
Prenons un premier exemple simple (inspiré par wikipedia). Si on prend des valeurs un peu au hasard, par exemple on obtient

  • avec X0 = 10, la suite : 10, 10, 10, 10, 10, …
  • avec X0 = 11, la suite : 11, 35, 123, 19, 235, 3, 91, 243, 203, 227, 59, 211, 171, 195, 27, 179, 139, 163, 251, 147, 107, 131, …
  • avec X0 = 12, la suite : 12, 60, 236, 28, 204, 252, 172, 220, 140, 188, 108, 156, 76, 124, 44, 92, 12, 60, 236, 28, 204, 252, 172, …

Bref, on notera déjà qu’il est effectivement intéressant de partir d’un nombre premier, car on boucle alors beaucoup moins vite. Ah oui, et pour se ramener sur l’intervalle [0,1], on divise par m. On a alors intérêt à avoir m assez grand.
Prenons un second exemple simple (inspiré du générateur proposé par Robert Sedgewick). On prend , et on part de 0.

[1]         0        1 31415822 40519862 31536702 84962343
[7]  59428603 54128063 38284723  4802584 19281465 53057765
[13] 47900065 67928365 55662665 20022965 84329266 25717386
[19] 95163907 67972648 42464008 74270568 69856328 96165288
[25] 74221448 24728808  5671369 13328949 75902129 98182909

La série a l’allure suivante,
xxxxEt si on regarde l’histogramme et la fonction d’autocorrélation sur les 10 000 premières valeurs, on a gardé l’uniformité (ou tout du moins on ne doit pas en être trop loin), et on n’a plus d’autocorrélation.

Parmi les générateurs ultra-classiques, mais mauvais, on retiendra le RANDU, datant des années 60, implémenté alors sur les IBM, X_{n+1} equiv (65539 times X_n) mod 2^{31} Mais cet algorithme présente de très gros défauts numériques. Je n’aborderais pas ici les problèmes de ce générateur (je l’avais fait dans le chapitre sur les simulations dans le tome 2 du livre avec Michel Denuit).
Bref, voilà ce qu’on peut raconter rapidement sur les méthodes de construction de nombres aléatoires, ou comme on dit généralement pseudo-aléatoires. Pour quelques réflexions sur l’utilisation de méthodes déterministes pour générer du hasard, je renvoie au très beau petit livre d’Ivar Ekeland intitulé Chaos. Et histoire d’insister un peu lourdement, ces billets (comme la plupart de ceux présent sur ce blog) n’ont pas grande prétention, si ce n’est présenter des concepts parfois compliqués “avec les mains” (et des dessins). Pour aller plus loin, on trouvera de très bons résumés de ces techniques sur le net, ici ou . Je laisse les plus curieux continuer. Sinon le chapitre 7 du Monte Carlo de Fishman propose une analyse poussée de ces méthodes. Et je voulais aussi noter que ce que j’ai proposé dans ces billets, c’est simplement de tirer des nombres aléatoires uniformément répartis sur [0,1]. Pour générer autre chose que de l’uniformité, je renvoie à la bible de Luc Devroye, non-uniform random variate generation, épuisé chez Springer, mais en ligne ici.

"Générer" du hasard, partie 4

Bon l’idée de récurrence les dernières fois (ici et ) n’était pas forcément mauvaise, mais telle qu’elle était présentée, ça ne marchait pas très bien… Une autre méthode peut être celle proposée par John von Neumann, parfois appelée middle square. On prend un nombre à 4 chiffres, on l’élève au carré, et on prend les 4 chiffres du “milieu“.  Par exemple à partir de 1234, dont le carré est 1522756, puis on prend le carré de 2275, c’est à dire 5175625… etc. On prend alors comme nombre cette suite de nombres divisés par 10000 (pour revenir entre 0 et 1). Sur cette exemple on note que l’on peut assez rapidement boucler, et retomber sur la même suite (ceci reste le problème central de tous les algorithmes récursifs).
XXX

Bref, on n’y est toujours pas… Pourtant, de loi, la suite des nombres peut  sembler aléatoires (en oubliant le fait que l’on s’est restreint à 4 chiffres),

[1]  0.2756 0.5536 0.7296 0.1616 0.1456 0.9936 0.4096 0.7216
[9]  0.7065 0.4225 0.5062 0.3844 0.6336 0.4896 0.7081 0.4056
[17] 0.1136 0.0496 0.6016 0.2256 0.9536 0.5296 0.7616 0.3456
[25] 0.3936 0.2096 0.3216 0.2656 0.4336 0.8008 0.8064 0.8096
[33] 0.5216 0.6656 0.2336 0.6896 0.4816 0.3856 0.8736 0.7696

Mais si on regarde cet exemple de plus prêt, on note que le chiffre 6 apparaît très fréquemment à la fin, par exemple…. Même si cette méthode est souvent présentée (par exemple dans la page de wikipedia consacrée aux méthodes de simulations, ici), elle marche beaucoup moins bien que les méthodes que j’avais présentées auparavant (ici et ) et que l’on cite assez peu.

"Générer" du hasard, partie 3

Pour poursuivre l’idée développée dans le billet précédant (ici), prenons une autre fonction de récurrence.

Toujours dans ces notes de cours (donné il y a un peu plus de 10 ans par Christian Gouriéroux), il y avait cette tent function que l’on retrouve sur le graphique de gauche. Si je fais tourner l’algorithme à partir de π-3, on obtient, avec une simple fonction R

[1]  0.14159265 0.28318531 0.56637061 0.86725877 0.26548246 0.53096491
[7]  0.93807017 0.12385966 0.24771932 0.49543864 0.99087728 0.01824545
[13] 0.03649090 0.07298179 0.14596358 0.29192717 0.58385434 0.83229132
[19] 0.33541736 0.67083471 0.65833057 0.68333886 0.63332228 0.73335543
[25] 0.53328913 0.93342173 0.13315654 0.26631308 0.53262615 0.93474770

Bref, ça marche bien là aussi (à condition là aussi d’avoir une écriture très longue de π). On peut là aussi montrer simplement que l’on génère une suite de nombre uniformément distribués sur [0,1], car cette loi est invariante par la fonction de récurrence (tout comme celle proposée par Whittle). Mais on n’a toujours pas d’indépendance….

“Générer” du hasard, partie 2

Une première piste (qui n’est pas de moi mais qui a été proposé par Peter Whittle en 1963, et que j’ai retrouvé dans des notes prises lors d’un cours de Christian Gouriéroux) est une idée simple de récurrence. On prend un nombre u entre 0 et 1 (si possible irrationnel, sinon ça n’a pas grand intérêt), et on considère la suite. Par exemple si on prend comme valeur initiale π-3, on obtient, avec une simple fonction R

[1]  0.14159265 0.28318531 0.56637061 0.13274123 0.26548246 0.53096491
[7]  0.06192983 0.12385966 0.24771932 0.49543864 0.99087728 0.98175455
[13] 0.96350910 0.92701821 0.85403642 0.70807283 0.41614566 0.83229132
[19] 0.66458264 0.32916529 0.65833057 0.31666114 0.63332228 0.26664457

Bref, ça marche bien (à condition numériquement d’avoir une écriture avec un nombre infini de décimales).  Le plus simple est de passer en base 2 (on peut trouver π en base 2 sur le net, par exemple ici). Bref, on peut obtenir la série suivante,
Plus généralement sur le caractère aléatoire des décimales de π, je renvoie aux publications de David H. Bailey (ici).
Bref, cette méthode pourrait marcher car on génère effectivement des nombres uniformément sur l’intervalle [0,1]… sauf que les tirages ne sont pas du tout indépendants. On observe un beau processus autorégressif AR(1), avec une autocorrélation  en 2-h.
XXBref, en l’état cette méthode n’est pas vraiment géniale pour générer du “hasard“… à suivre donc.

“Générer” du hasard, partie 1

J’ai déjà mis plusieurs billets sur mon blog afin d’évoquer les méthodes de Monte Carlo (ici ou là), car de mon point de vue, ce sont des techniques fondamentales en économétrie par exemple, si on travaille sur des petits échantillons. Mais pour l’instant, j’avais toujours éludé le problème délicat du générateur… J’avais toujours admis que l’on avait à notre disposition un générateur de nombres aléatoires sur [0,1], qui génère à chaque appel des nombres indépendants, supposés uniformément distribués sur [0,1].

Je voulais prendre un peu de temps pour présenter quelques pistes de méthodes simples de méthodes permettant de générer des suites de nombre donnant l’illusion du hasard….
Une méthode plus ancienne (que j’ai connue, et oui) est celle des tables de nombres aléatoires, que l’on retrouvait par exemple dans les anciennes éditions du livre de Philippe Tassi ou de Gilbert Saporta. Je laisse les plus curieux traîner dans les vieux livres pour voir comment lire ce genre de table…. Une autre solution est celle que j’évoquais en introduction de mon (vieux) cours de séries temporelles à Dauphine (ici), à savoir l’idée de Slutsky d’utiliser les tirages du loto pour modéliser des prix (et donc inventer ainsi les processus MA, moving average), dans The Summation of Random Causes as the Source of Cyclical Processes. On peut trouver sur  le net les tirages du loto en France depuis des dizaines d’années (ici par exemple) et je suppose qu’en cherchant un peu, on peut trouver des choses similaires dans beaucoup d’autre pays.

Pour ma part, pour revenir sur une loi uniforme sur [0,1], je vais dans un premier temps diviser par 50.

Dans un second temps, on va concaténer deux boules consécutives (en base 50), puis se ramener sur [0,1].
Aussi, les boules 13 et 37 donnent comme nombre 0.2548.

On a ainsi un peu plus de possibilités sur les valeurs atteintes. Graphiquement, on obtient les résultats suivants,
XXXBref, on a à notre disposition des gens qui ont tiré des boules dans une urne. Alors rigoureusement, il faut faire attention car les tirages sont fait sans remise pour les 7 premières boules, puis on remet les boules pour le tirage suivant… Bref, les tirages ne sont pas rigoureusement indépendant les uns des autres (on ne peut pas avoir 3 fois consécutives le nombre “13”, alors qu’en théorie cela devrait être possible).
Bref, on est un peu limité avec ce genre d’outils, car ce qui m’intéresse c’est que mon ordinateur me génère autant de nombres aléatoires que je le souhaite.

An Open Lab-Notebook Experiment