MacGyver et la théorie des groupes

L’autre jour, quelqu’un me félicitait pour mon blog, c’était une étudiante en maths, qui disait comprendre certaines choses en probas et en stats (entre autres sur les applications possibles)…. mais pour la théorie des groupes, elle ne voyait toujours pas d’intérêt…

J’étais bien entendu ravi que mon blog serve à quelque chose, mais en fait la théorie des groupes peut avoir des applications amusantes (bon, tout dépend aussi de ses centres d’amusement). Par exemple MacGyver pourrait avoir eu besoin de connaître des résultats sur les groupes pour sortir des prisonniers des geôles afghanes…

Considérons le gardien de prison sadique qui annonce le “jeu” suivant (Anatole, un collègue ici me l’avait suggéré l’autre jour en me mettant au défi de trouver une solution…. mais faut pas pousser, je suis plus fort que MacGyver ! bon, et il faut dire que le jeu est classique…on le trouve expliqué ici ou ):

Tous les prisonniers (disons qu’ils sont 20) se voient attribuer un numéro, entre 1 et 20. Le premier prisonnier est appelé et se retrouve face à 20 portes, derrière lesquelles sont cachés des numéros (allant de 1 à 20 là encore). Il a droit d’en ouvrir 10 (au maximum) et il doit retrouver son numéro. S’il n’y arrive pas,tous les prisonniers sont exécutés (lui compris). S’il y arrive, il n’est pas sauvé pour autant car le commandant appelle le second prisonnier, qui se retrouve à son tour devant les 20 portes, et doit trouver son numéro… Etc.

Les prisonniers commencent à paniquer, car tout le monde doit trouver son numéro pour être sauvé. En raisonnant rapidement, un des prisonniers explique qu’un seul prisonnier aurait 50% de chances d’y arriver. Avec deux, comme ils ont tous les deux 50% de chances, on tombe à 25%, etc. Avec n prisonniers, on est à 1/2n, qui est de l’ordre d’une chance sur un million avec 20 prisonniers…. Et qu’ils ont de la chance de n’être que 20 ! Avec 30 prisonniers, ils
auraient une chance sur un milliard de s’en sortir (ce qui est faible, on en conviendra).

Mais MacGyver, qui avait pris le cours Théorie des Groupes 101 à l’université (et qui avait R installé dans sa montre digitale) dit

  • pas du tout, j’ai une stratégie qui nous donne environ une chance sur trois de tous s’en sortir (vu comme ça c’est pas terrible, mais par rapport à 1 chance sur un milliard, c’est vachement bien),
  • et accessoirement, cette probabilité ne dépend pas du nombre de prisonnier (tant que l’on puisse ouvrir moitié moins de portes qu’il y a de prisonniers)

Bon, sur le moment, les autres prisonniers se fichent du fait que même s’ils étaient 1000 ils auraient une chance sur trois de survivre, ils veulent comprendre la stratégie de Mac… Comme le rappelle Mac, le commandant ne fait que choisir une permutation de https://perso.univ-rennes1.fr/arthur.charpentier/latex/prison99.png, même s’il est sadique (ou parce qu’il est sadique, les profs de maths sont sadiques, tout le monde sait ça). Et toute permutation peut se décomposer en un produit ds combinaisons cycliques (on parle de la décomposition en produit de cycles à supports disjoints, c’est un truc utilise je crois pour les amateurs de Rubik’s cube),

Par exemple, considérons la permutation suivante (c’est la première que j’ai eu sous R),

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

Elle se décompose en 5 permutations cycliques

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

La plus grande est la dernière, et elle permute sur 7 nombres. Autrement dit, si chacun utilise cette stratégie, il ouvrira au plus 7 portes. Le point important est qu’ils ne peuvent pas être pris dans une autre permutation que la leur, car ils ont pris leur porte, donc au pire, il tire le numéro de la première porte qu’ils ont ouvert… qui est le numéro qu’ils doivent tirer pour survivre ! Regardons sur notre exemple

> set.seed(1)
> portes = sample(1:n,size=n,replace=FALSE)
>  prisonnier=1
>  essai = c(prisonnier)
>  nessai = 1
>  i = porte[prisonnier]
>  while(nessai <= 50) {
+  essai = c(essai, i)
+  if(i == prisonnier) {
+  cat(“Le prisonnier”, prisonnier, “a ouvert”, nessai, “portes\n”)
+  break; }
+  else {
+  i = porte[i]}
+ n essai =n essai+1 }
Le prisonnier 1 a ouvert 4 portes
>  cat(“Le prisonnier”, prisonnier, “a ouvert les portes suivantes”, 
paste(essai[-length(essai)], collapse=” – “), “\n”)
Le prisonnier 1 a ouvert les portes suivantes 1 – 6 – 14 – 10

soit ici

Le prisonnier 1 a ouvert 4 portes
Le prisonnier 1 a ouvert les portes suivantes 1 – 6 – 14 – 10
Le prisonnier 2 a ouvert 7 portes
Le prisonnier 2 a ouvert les portes suivantes 2 – 8 – 9 – 19 – 18 – 17 – 12
Le prisonnier 3 a ouvert 2 portes
Le prisonnier 3 a ouvert les portes suivantes 3 – 11
Le prisonnier 4 a ouvert 5 portes
Le prisonnier 4 a ouvert les portes suivantes 4 – 16 – 7 – 15 – 5
Le prisonnier 5 a ouvert 5 portes
Le prisonnier 5 a ouvert les portes suivantes 5 – 4 – 16 – 7 – 15
Le prisonnier 6 a ouvert 4 portes
Le prisonnier 6 a ouvert les portes suivantes 6 – 14 – 10 – 1
Le prisonnier 7 a ouvert 5 portes
Le prisonnier 7 a ouvert les portes suivantes 7 – 15 – 5 – 4 – 16
Le prisonnier 8 a ouvert 7 portes
Le prisonnier 8 a ouvert les portes suivantes 8 – 9 – 19 – 18 – 17 – 12 – 2
Le prisonnier 9 a ouvert 7 portes
Le prisonnier 9 a ouvert les portes suivantes 9 – 19 – 18 – 17 – 12 – 2 – 8
Le prisonnier 10 a ouvert 4 portes
Le prisonnier 10 a ouvert les portes suivantes 10 – 1 – 6 – 14
Le prisonnier 11 a ouvert 2 portes
Le prisonnier 11 a ouvert les portes suivantes 11 – 3
Le prisonnier 12 a ouvert 7 portes
Le prisonnier 12 a ouvert les portes suivantes 12 – 2 – 8 – 9 – 19 – 18 – 17
Le prisonnier 13 a ouvert 2 portes
Le prisonnier 13 a ouvert les portes suivantes 13 – 20
Le prisonnier 14 a ouvert 4 portes
Le prisonnier 14 a ouvert les portes suivantes 14 – 10 – 1 – 6
Le prisonnier 15 a ouvert 5 portes
Le prisonnier 15 a ouvert les portes suivantes 15 – 5 – 4 – 16 – 7
Le prisonnier 16 a ouvert 5 portes
Le prisonnier 16 a ouvert les portes suivantes 16 – 7 – 15 – 5 – 4
Le prisonnier 17 a ouvert 7 portes
Le prisonnier 17 a ouvert les portes suivantes 17 – 12 – 2 – 8 – 9 – 19 – 18
Le prisonnier 18 a ouvert 7 portes
Le prisonnier 18 a ouvert les portes suivantes 18 – 17 – 12 – 2 – 8 – 9 – 19
Le prisonnier 19 a ouvert 7 portes
Le prisonnier 19 a ouvert les portes suivantes 19 – 18 – 17 – 12 – 2 – 8 – 9
Le prisonnier 20 a ouvert 2 portes
Le prisonnier 20 a ouvert les portes suivantes 20 – 13

En adaptant un code développé ici par Matt Asher, on peut d’ailleurs visualiser tout ça sur un petit dessin,
,

Bref, la grande question est “quelle est la probabilité que la plus grande sous permutation cyclique soit sur un ensemble de taille supérieure à 10” ? On peut faire un peu de Monte Carlo pour voir…. c’est ce que fait Matt. Mais sinon on peut aussi faire du dénombrement (ce qui est pareil que les probas). Le nombre de permutations contenant un cycle de longueur supérieure à 10 (strictement) se calcule de la manière suivante: soit k la taille du cycle, alors je peux choisir les https://perso.univ-rennes1.fr/arthur.charpentier/latex/prison00.png nombres de https://perso.univ-rennes1.fr/arthur.charpentier/latex/prison03.png manières. Il y a alors https://perso.univ-rennes1.fr/arthur.charpentier/latex/prison04.png permutations circulaires de ces k nombres, et on permute les https://perso.univ-rennes1.fr/arthur.charpentier/latex/prison05.png nombres qui reste comme on veut, ce qui donne https://perso.univ-rennes1.fr/arthur.charpentier/latex/prison06.png possibilités. Bref, j’en suis à

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

permutations ayant un cycle de longueur k, soit en tout,

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

Or comme on a en tout https://perso.univ-rennes1.fr/arthur.charpentier/latex/prison08.png permutations possibles, la probabilité de s’en sortir vivant est

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

Et là où Mac est fort, c’est qu’effectivement, avec n prisonniers

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

Soit environ 30% de chances de s’en sortir….
Moralité, la théorie des groupes peut être marrante et intéressante…. Bon, c’est la seule application à la vraie vie qui me vient à l’esprit, et à moins d’être enfermé en prison avec un geôlier sadique, c’est dur de trouver des applications. N’empêche que la solution est passionnante (mais MacGyver a toujours été mon héros pour ça…)

Extracting information from a keyboard…

Yesterday, Baptiste published a post on “ethno-photography” (here). As he mentioned it, in Paris 8, they experience a real absence of serious cleaning of office equipment. He then shows the keyboard of the only computer they can use in the sociology department (for forty researchers),

Apart from the fact that everyone in France should be ashamed to see how much is spent in universities (which is the first information we have from that picture), we should also be able to guess in which langage people work in this department.
I considered three books (two in French, one in English) and I would like to see the frequency of each letter,

  • Mauss, manuel d’éthnographie (here), 1926
  • Durkheim, Livre II: Les croyances élémentaires in Les formes élémentaires de la vie religieuse (here), 1912
  • Ferri, Criminal Sociology (here), 1896

Those three books are in rich text format, I just changed it to get text files… Then, it is easy to count appearance of letters. E.g. for Mauss,

> library(corpora)
> textfile=scan("MAUSS-manuel.txt",
+ what="char", sep="\n")
Read 1550 items
> textfile<-tolower(textfile)
> M=NA
> for(i in 1:length(textfile)){
+ line=textfile[i]
+ M=c(M,strsplit(as.character(line),"")[[1]])
+ }
> T=table(M)
> T
M
    '     -           \t     !     "     %     &     (     )     ,     .     / 
 5308  1049 86589    44     3     3     2     2   370   391  6609  4909    12 
    :     ;     ?     @     ]     _     ~     ’     =     «     »     ¬     ° 
  819  1178   113     1     1     4     1    39     1   108   107   823     3 
    …     0     1     2     3     4     5     6     7     8     9     a     à 
    1    69   213    83    73    34    48    33    28    64   151 30559  1651 
    â     ä     b     c     ç     d     e     é     è     ê     ë     f     g 
  224     3  3562 14678   110 17713 63955 10354  1798  1000     5  4555  4911 
    h     i     î     ï     j     k     l     m     n     ñ     o     º     ô 
 4359 30851   226    47  1147   247 24792 12844 32525     6 25562     2   151 
    ö     œ     p     q     r     s     t     u     ù     û     ü     v     w 
   12    52 12696  4667 28237 37630 32945 25001   211    40     9  4787   164 
    x     y     z 
 1996  1222   343

Then, we can summarize in to see proportion of standard 26 letters, and we have, for Mauss,

and for Durkeim,

If we compare the two, we have almost the same proportions,

If we look at our book in English now, we have

i.e., if we compare with Mauss for instance

So we have much more E in French than in English, but still, people writing in English use a lot the E. So looking at the E should not give us any clue…. But we can see that in English, the H is as common as the L, or the C. Not in French, where L is much more frequent than the H. But on the picture, the C is more clear than the H. We can also look at the U, which is common in French, not in English… Here, on the keyboard, it is perfectly clear… so I guess people use it frequently.
So I would say that they write more in French than the write in English, on that computer.
Actually, the same idea has been used a long time ago on calculators to see that Benford’s law works: some numbers are really used (as well as the legend pretends that some pages in logarithm books were never used….), see here orthere. So Baptiste, if one day the keyboard is cleaned up, please send me another picture after a few weeks to see if things have changed….
An for those who cannot imagine how it is to work in some universities in France, just look at his blog (here). Pictures are unbelievable….Good luck Baptiste….

Lottery, and martingales

I recently got a comment on a post I published one year ago, here, about the fact that in September 2009, on the 6th and the 10th, the 6 same numbers came out at the lottery, in Bulgaria (but  I do not understand the question: the author of the comment ask about the order the numbers came out…)
Xi’an published also a post on that topic, there, since last week, the same thing happened in Israel.
All that reminded me a discussion I had with a colleague about another post (here) where I mentioned that I found a strange distribution of numbers in the French lottery (the old one actually). For those who want to check, all historical events are here, in a zip file. My colleague was wondering if I found the martingale to win the lottery…

First, I do not like that term, since martingale is something different from a mathematical point of view… Second, let us look if it would have been possible to make some money… (free lunch ?)

> loto=read.table("D:\\loto.csv",dec=",",header=TRUE,sep=";")
> ntirage=nrow(loto)
> loto=loto[51:ntirage,]
> ntirage=nrow(loto)
>   N=as.matrix(loto[,c("boule_1","boule_2","boule_3","boule_4","boule_5","boule_6")])
> n=as.vector(N)
> length(n)
[1] 28848
> (TN=table(n))
n
1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20
607 576 571 618 579 598 608 582 588 590 562 577 577 580 591 630 558 567 594 608
21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40
578 562 579 583 574 589 602 572 550 598 604 582 545 646 597 618 599 636 609 588
41  42  43  44  45  46  47  48  49
576 589 577 585 618 596 560 571 604

So, it might look nice, but we have to compare that distribution with the one we should have with “independent” draws. It is not possible to look at a discrete uniform distribution: the six numbers are not independent. Each day, the 49 balls are back in the urn, but within a day, we do not have independent draws (it is a sample without replacement of balls). Hence, with 4808 lottery draws, each number cannot be obtained more than 4808 times. So, let us use monte carlo techniques to  look at the theoretical distribution,

> M=matrix(NA,49,1000)
> for(s in 1:1000){
+ B=NA
+ for(i in 1:ntirage){B=c(B,sample(1:49,size=6,replace=FALSE))}
+ B=B[-1]
+ M[,s]=sort(table(B))
+ }
> q50=function(x){quantile(x,.5)}
> Q50=apply(M,1,q50)
> lines(1:49,Q50,col="red",lwd=2)
> q10=function(x){quantile(x,.1)}
> Q10=apply(M,1,q10)
> q90=function(x){quantile(x,.9)}
> Q90=apply(M,1,q90)
> polygon(c(1:49,49:1),c(Q10,rev(Q90)),col="light blue",border=NA)
> lines(1:49,Q10,col="red",lty=2)
> lines(1:49,Q90,col="red",lty=2)
> lines(1:49,Q50,col="red",lwd=2)
> points(1:49,sort(TN),pch=19,type="b")

Looking at the graph, it looks like some numbers appeared too frequently, especially the ones that did not appear frequently (bottom left). So, since I have removed the last 50 draws, let us see if we could have used that information, somehow…

> nb=names(sort(TN))
> loto=read.table("D:\\loto.csv",dec=",",header=TRUE,sep=";")
> loto=loto[1:50,]
> N=as.matrix(loto[,c("boule_1","boule_2","boule_3","boule_4","boule_5","boule_6")])
> n=as.vector(N)
> TN=table(n)
> TN[nb]
> barplot(TN[nb])

Unfortunately, numbers that came out too frequently over 4800 draws did not appear that frequently of the last 50. Playing top number might not have been a great strategy.

(numbers that came out frequently are on the right, while those we did not see much are on the left)… What about worst numbers: if I had decided to play the 6 that did not come out very frequently (we’ve seen earlier that they should have appeared even less, actually), would it have been interesting ? As we can see, our top 2 numbers were numbers that did not appear frequently earlier (29 and 47 appears respectively 10 and 11 times over 50 draws)….
Over 50 draws of 6 balls, the expected frequency of 6 given number is around 36.7,..

> S=rep(NA,10000)
> for(s in 1:10000){
+ B=NA
+ for(i in 1:50){B=c(B,sample(1:49,size=6,replace=FALSE))}
+ B=B[-1]
+ S[s]=sum(B%in%(1:6))
+ }
> mean(S)
[1] 36.7694

But here for the top 6, we have

> z=TN[nb]
> sum(rev(z)[1:6])
[1] 29

i.e. the top 6 appeared 29 times over 50 draw of 6 balls (which looks low) and for the worst 6, it is a bit higher,

>  sum(z[1:6])
[1] 38

If we look at the theoretical density of the frequency of 6 given number, we have

i.e. our worst 6 is a nice average (in green) while top 6 did not appear frequently this time (here in blue) ! So we could not have used that information….
Anyway, if some of you are interesting using statistics to get a free lunch, with the nouveau loto, I did not see any strange pattern (data can be downloaded here).

I am terribly sorry, but I cannot help anyone winning at the French Lottery….

Prétentieux, va !

Depuis quelques semaines, mes billets sont presque exclusivement en anglais… En fait, même si je fais cours en français, et que la plupart de mes collègues ici parlent français, je me rends compte qu’on parle naturellement anglais…. en tous les cas plus naturellement qu’en France. Les séminaires sont toujours en anglais, dès qu’on discute à plus de 3, la probabilité qu’une personne ne parle pas français est tellement grande qu’on parle le plus souvent en anglais….

Finalement, comme toujours quand je ne suis pas en France, je trouve naturel d’écrire en anglais… (ok, d’essayer d’écrire quelque chose qui ressemble à de l’anglais). Mais hier soir, ma femme m’a fait remarqué que c’était prétentieux d’écrire en anglais… Et effectivement, quand je traîne sur les blogs francophones, presque tous sont exclusivement en français…. Bref, je me remets à douter.
J’ai vu l’autre jour que David Monniaux s’en prenait sur son blog à un édito de Jacques Julliard (ici), et d’ailleurs David publie de plus en plus en anglais ces derniers temps (en tous les cas dès que l’on quitte les sujets franco-français). J’ai vu aussi que de plus en plus de doctorants blogueurs se lancent en anglais…
Le débat reste ouvert, et je suis preneur de toutes les remarques….

When should I optimally shoot at my son ? (part 2)

Following my previous post of yesterday, online here, assume now that I do not know if my son came when I turned my back at time, and missed me… Then the payoff function is the one propose by Vincent, i.e.

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

In that particular case,

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

becomes

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

i.e.

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

If we draw those functions, on [0,1], the optimal value is solution of https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel103.png

i.e. https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel104.png (we focus only on solutions in [0,1]). Because here the game is symmetric, my son should also shoot at time https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel105.png
Thus, the payoff is then

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

Since we consider here a  zero-sum game, this cannot be a solution of the game. So the game does not have pure strategy solution.

Assume that now I have a mixed strategy, i.e. a distribution of the optimal time to shot. My strategy has distribution https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel110.png, with density https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel111.png (we assume here that the density exists, or we seek only solution that are differentiable). Assume further that there exists https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel112.png>0 such that the support of my optimal shooting time (the time to shoot is now a random variable) is (https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel112.png,1] (or [https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel112.png,1] since we assume that https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel110.png is differentiable). There is a discussion at the end of Vincent’s post where he needs that assumption, at the end. Actually, I think we can make it now, since we can rationally assume that
I will not shot at time 0 (even on a neighborhood of 0 since I have zero chance to hit my son).
The expected payoff function, assuming that my son shoots at time y is

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

Since the zero-sum game is symmetric, again, the expected payoff should be zero. It comes that necessarily,

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

if https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel121.png. Hence, if we differentiate (with respect to y), we have

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

and if we differentiate one more time, it comes

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

i.e. a general solution should be of the form https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel130.png.
Here, we have the same solution as the one considered in Vincent’s blog. His solution is obtained as follows (with slightly different expressions) conditional to https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel03.png, my expected payoff is

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

i.e.

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

With a simple integration by parts,

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

where https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel134.png, i.e.

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

Thus,

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

So, if we want to be indifferent to https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel03.png‘s strategy, https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel141.png, where

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

with https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel143.png,

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

Consider solutions https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel150.png, then https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel151.png=1, i.e. either https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel152.png=1 and then https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel153.png is constant, or https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel152.png=-1. This means that https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel154.png is in proportional to https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel155.png.
If we substitute in the equation we had, initially, it comes that

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

i.e.

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

If we consider https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel03.png=a and https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel03.png=1, it comes that https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel112.png=1/3 while https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel162.png=1/4 (but we don’t really care about that normalizing constant).
It means that we should not start shooting before 1/3 of the tank is fulled. Actually, it makes sense, since

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

if https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel03.png<1/3 (while https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel164.png=0 if  https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel03.png>1/3).

When should I optimally shoot at my son ? (part 1)

when playing with water guns ! It is not a reverse oedipal fantasy, it is simply a (stochastic) game. Actually, that game was mentioned here, in the context of a duel with laser guns, and the answer is there. Vincent (alias @Vicnent) presented the problem this way: consider a single combat between two single warriors (a duel) with laser guns. The probability to kill the other one is proportional to time https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel01.png (duel started at time 0). Initially, the have no chance to kill the other one, and after one hour, they are certain to kill the other one. At time https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel01.png, they kill the other one with probability https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel01.png (and miss him with probability https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel04.png). What is the optimal time to shot ?

An alternative can be the following (yes, I prefer personal experience to science fiction): consider two warriors playing with water gun. We start with empty guns, and assume that both warriors fill their guns at two different tap water. The more water we have in guns, the more likely the other one will be wet. What is my optimal strategy to stop filling the gun, and start shooting at the other player ?
In order to formalize the game, assume that I will win 1 point if my son gets wet (and not me), I’ll get -1 if I am wet, and not him, and 0 if we are both wet (in Vincent’s game, we have the same payoff matrix, but I find odd to say that I have -1 if I die).
Let https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel02.png and https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel03.png denote time where players shoot. Vincent derived the following expected payoff function: for me (I shoot at time https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel02.png) the payoff is

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

If we know that the other player shoot us, but missed us, it should be different: if I shot first, but missed my son, then he should wait until the end, and so, the payoff should be (thanks Jérôme)

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

Actually, we can consider a more general game, where probabilities are not proportional to https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel01.png, but functions https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel10.png for me (https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel13.png stands for dad), and https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel11.png for the other player (here my son https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel12.png). The expected payoff becomes,

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

Thus my best strategy is obtained by solving

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

that is

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

Let

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

If https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel11.png and https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel10.png are assumed to be continuous (we assume that water goes continuously into the tank of the gun), then there is https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel26.png such that

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

If https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel30.png, then https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel32.png and

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

and so https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel35.png. So

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

Similarly, if https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel31.png, then https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel33.png and

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

and so https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel40.png. So

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

So finally, the optimal strategy is to shoot at the same time, https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel01.png.
In the game considered initially by Vincent, https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel43.png. Hence, https://perso.univ-rennes1.fr/arthur.charpentier/latex/duel01.png=1/2.
But it is also possible that I did not hear my son coming, shooting at me (and missing me). So in that case, the payoff is different, and closer to what Vincent proposed… but that will be in another post…

Lecture notes on risk measures

I just finished some lectures notes on risk measures. The notes, that can be downloaded [pdf], are in French, and will be used at the JES (Journées d’Etudes Statistiques), organised at the CIRM (mentioned here). The short course will follow a short introductionary course by Jean Marc Tallon. He recently published on his website a survey on decision theory under uncertainty (here) which is almost what he will talk about in Marseille. All comments are welcome…

Qui a eu l’idée d’élargir les trottoirs en France ?

J’étais tombé l’autre jour sur un joli dessin expliquant pourquoi les policiers et les syndicats n’estimaient jamais le même nombre de manifestants, avec une explication scientifique, et vaguement rationnelle, ici.

C’est  effectivement joli… et on retrouve un rapport de 3 dont pas mal de monde semble parler, sauf que si c’était vrai, le rapport entre les estimations de la police et des syndicats devrait être stable d’une manifestation à l’autre, non ?
Si on compare le 19 mars dernier (ici) et le 16 octobre (), on arrive aux chiffres suivants,

Les traits pointillés sont la droite de régression. La courbe en trait plein et la régression (passant par l’origine car on cherche un rapport de proportionnalité) en prenant en compte un effet taille, i.e. en introduisant des poids différents dans ma régression. J’ai pris la taille des villes, autrement dit, plus la ville est grosse, plus je donne un poids important au rapport… L’idée étant d’intégrer un effet médiatique, même si la pente n’est plus le ratio moyen…  Avec cette dernière méthode, j’obtiens des pentes de 4,06 pour mars, et 6,12 pour octobre… ce qui est à un peu différents des rapports nationaux mentionnés sur le site du monde, i.e. (3 millions selon les syndicats et 1,2 selon la police, en mars, contre  2,5 millions contre 825 milliers l’autre jour). Notons qu’on peut vérifier rapidement que ce n’est pas un problème statistique, les valeurs sont sensiblement différentes, si l’on compare les distributions des estimateurs..

Bref, quelque chose semble avoir changé entre ces deux dates…. la taille des trottoirs ?

Mandelbrot, fractals and counterexamples in applied probability

Benoît Mandelbrot died yesterday. Like most of the blogs dealing with applied mathematics, it looks like I have to mention this event. Unfortunately, I don’t know much about fractals…

The first time I heard about Mandelbrot and chaos was when I have been working on fractional time series (see eghere). Murad Taqqu gave a very interesting short course in Paris, and I have been using it in two papers (actually one more should appear soon in Climate Change).

The second time was in Québec (city), five years ago, when Roger Nelsen gave a talk on copulas with fractal suppport (here). By that time, we were finishing our paper with Alessandro (in mathematical finance, and limiting theorems). I remember adding a Remark in the paper (that can be found here), since using that kind of copulas was a nice way to show that, without sufficient regularity conditions, the limit we were looking for had no sense.

A few months after, with Johan, in a paper on pitfalls on lower tail dependence for Archimedean copulas (here), we used again this fractal construction (here applied to Archimedean copulas) to find a nice counterexample to a (false) theorem on regular variation. Again, the goal was to understand how the dependence structure of https://perso.univ-rennes1.fr/arthur.charpentier/latex/mandel01.png given https://perso.univ-rennes1.fr/arthur.charpentier/latex/mandel02.png and https://perso.univ-rennes1.fr/arthur.charpentier/latex/mandel03.png changed when https://perso.univ-rennes1.fr/arthur.charpentier/latex/mandel04.png goes to 0. In the case of Archimedean copulas, the copula of the conditional pair is still Archimedean (with another generator, except for Clayton copula). The graph below show how https://perso.univ-rennes1.fr/arthur.charpentier/latex/mandel05.png changes, as https://perso.univ-rennes1.fr/arthur.charpentier/latex/mandel04.png decreases… Actually, I draw https://perso.univ-rennes1.fr/arthur.charpentier/latex/mandel06.png since Archimedean generators are not unique.

I have also decided to plot https://perso.univ-rennes1.fr/arthur.charpentier/latex/mandel07.png.

Here, we see that there is no way of talk about a possible limit for the conditional copula because of a fractal behavior in 0 of the generator (even if my fractal are not as nice as the one you can find on the internet….). So thanks Benoît for giving us a nice toy to build interesting counterexamples !

Margin of error, and comparing proportions in the same sample

Irecently tried to answer a simple question, asked by @adelaigue. Actually, I thought that the answer would be obvious… but it is a little bit more compexe than what I thought. In a recent survey about elections in Brazil, it was mentionned in a French newspapper that “Mme Rousseff, 62 ans, de 46,8% des intentions de vote et José Serra, 68 ans, de 42,7%” (i.e. proportions obtained from the survey). It is also mentioned that “la marge d’erreur du sondage est de 2,2% ” i.e. the margin of error is 2.2%, which means (for the journalist) that there is a “grande probabilité que les 2 candidats soient à égalité” (there is a “large probability” to have equal proportions).
Usually, in sampling theory, we look at the margin of error of a single proportion. The idea is that the variance of https://latex.codecogs.com/gif.latex?%20\widehat{p}, obtained from a sample of size https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial15.png is

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

thus, the standard error is

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

The standard 95% confidence interval, derived from a Gaussian approximation of the binomial distribution is

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

The largest value is obtained when p is 1/2, and then we have a worst case confidence interval (an upper bound) which is

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

So with a margin of error https://perso.univ-rennes1.fr/arthur.charpentier/latex/m205.png means that https://perso.univ-rennes1.fr/arthur.charpentier/latex/m206.png. Hence, with a 5% margin of error, it means that n=400. While 2.2% means that n=2000:
> 1/.022^2
[1] 2066.116
Classically, we compare proportions between two samples: surveys at two different dates, surveys in different regions, surveys paid by two different newpapers, etc. But here, we wish to compare proportions within the same sample. This has been consider in an “old” paper published in 1993 in the American Statistician,

It contains nice figures to illustrate the difference between the standard approach,

and the one we would like to study here.

This point is mentioned in the book by Kish, survey sampling (thanks Benoit for the reference),


Let https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial05.png and https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial06.png denote empirical frequencies we have obtained from the sample, based on https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial15.png observations. Then since

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

and

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

we have

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

Thus, a natural margin of error on the difference between the two proportion is here

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

which is here 4 points
> n=2000
> p1=46.8/100
> p2=42.7/100
> 1.96*sqrt((p1+p2)-(p1-p2)^2)/sqrt(n)
[1] 0.04142327
Which is exactly the difference we have here ! Hence, the probability of reaching such a value is quite small (2%)
> s=sqrt(p1*(1-p1)/n+p2*(1-p2)/n+2*p1*p2/n)
> (p1-p2)/s
[1] 1.939972
> 1-pnorm(p1-p2,mean=0,sd=sqrt((p1+p2)-(p1-p2)^2)/sqrt(n))
[1] 0.02619152

Actually, we can compare the three margin of errors we have so far,

  • the upper bound
https://perso.univ-rennes1.fr/arthur.charpentier/latex/m208.png
  • the “average one”
https://perso.univ-rennes1.fr/arthur.charpentier/latex/m209.png

where

https://perso.univ-rennes1.fr/arthur.charpentier/latex/m212.png
  • the more accurate one we just obtained,
https://perso.univ-rennes1.fr/arthur.charpentier/latex/m213.png

where https://perso.univ-rennes1.fr/arthur.charpentier/latex/m214.png.
> p=seq(0,.5,by=.01)
> ic1=rep(1.96/sqrt(4*n),length(p))
> ic2=1.96*sqrt(p*(1-p))/sqrt(n)
> delta=.01
> ic31=1.96*sqrt(2*p-delta^2)/sqrt(n)
> delta=.2
> ic32=1.96*sqrt(2*p-delta^2)/sqrt(n)
> plot(p,ic32,type=”l”,col=”blue”)
> lines(p,ic31,col=”red”)
> lines(p,ic2)
> lines(p,ic1,lty=2)
So on the graph below, the dotted line is the standard upper bound, the plain line in black being a more accurate one when the probability is https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial19.png (the x-axis). The red line is the true margin of error with a large difference between candidates (20 points) and the blue line with a small difference (1 point).


Remark: an alternative is to consider a chi-square test, comparering two multinomial distributions, with probabilities https://perso.univ-rennes1.fr/arthur.charpentier/latex/m215.png and https://perso.univ-rennes1.fr/arthur.charpentier/latex/m216.png where https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial19.png is the average proportion, i.e. 44.75%. Then

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

i.e.  https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial22.png=3.71
> p=(p1+p2)/2
> (x2=n*((p1-p)^2/p+(p2-p)^2/p))
[1] 3.756425
> 1-pchisq(x2,df=1)
[1] 0.05260495
Under the null hypothesis, https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial22.png should have a chi-square distribution, with one degree of freedom (since the average is fixed here). Here the probability to reach that level is around 5% (which can be compared with the 2% we add before).

So finally, I would think that here, stating that there is a “large probability” is not correct…

et c’est parti pour les élections…

Ce soir, @imparibus reprenait  une information du Point (ici). “Un sondage de l’institut Sensus diffusé jeudi crédite Mme Rousseff, 62 ans, de 46,8% des intentions de vote et José Serra, 68 ans, de 42,7% […]  la marge d’erreur du sondage est de 2,2%, a expliqué un reponsable de l’enquête [… ce qui donne une ] grande probabilité que les 2 candidats soient à égalité”. @imparibus affirmait que c’était faux,@adelaigue me demandant mon avis…
Bon, je suis flâté qu’Alexandre m’appelle à l’aide, mais je suis plutôt nul en sondage… Bref, pour faire une réponse intelligente et détaillée, il me faudra un peu plus de place que ce que ne me propose Twitter…
Soit https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial01.png la probabilité de voter pour R, et https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial02.png la probabilité de voter pour S. On note https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial03.png la probabilité de voter pour un autre candidat, https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial04.png.
Si https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial05.png et https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial06.png sont les fréquences empiriques obtenues à partir de https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial15.png personnes sondées, rappelons que

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

et

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

Aussi,

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

Si on veut tester https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial12.png (hypothèse https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial13.png) car c’est finalement de ça qu’on parle ici, l’idée la plus naturelle serait d’introduire la statistique de test d’égalité des proportions,

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

qui suit – à la louche – une loi normale sous https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial13.png.
C’est bien joli tout ça, mais je ne connais pas https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial15.png ! En fait, on va essayer de s’aider de la petite phrase “la marge d’erreur du sondage est de 2,2%”
Alors si j’en crois le site d’ipsos (ici),  cette marge d’erreur correspond à 2000 personnes interrogées…
Or ici https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial05.png =46% et et https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial06.png = 42.7%, avec

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

soit,

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

Si on compare à une loi normale, on a 2.6% de chances d’atteindre une telle valeur…
On peut aussi faire un test du chi-deux. En cas d’égalité des proportions, on devrait avoir https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial19.png=44.75%
et si on utilise un test du chi-deux pour mesurer la distance entre les deux lois multinomiale (sous https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial13.png et sous H1), on a comme distance du chi-deux

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

soit ici https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial22.png=3.71 avec 2000 personnes interrogées. Sous https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial13.pnghttps://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial22.png devrait suivre une loi du chi-deux à 1 degré de liberté, ce qui donne une p-value de 5.26%.
On peut aussi tenter un test de rapport de vraisemblance. Sous https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial13.png, on a

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

alors que sous https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial23.png

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

(en utilisant la forme des lois multinomiales). Le rapport des vraisemblances s’écrit alors

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

soit ici https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial27.png= 10.436. La statistique de test est icihttps://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial27.png qui doit suivre, sous https://perso.univ-rennes1.fr/arthur.charpentier/latex/multinomial13.png une loi du chi-deux à un degré de liberté. La p-value associée est alors de l’ordre de 0,1%….
Bon, il semble qu’on puisse raffiner un peu les tests, en reprenant les idées de Nass (1959) et de Hoel (1938) – mais qui sont intéressant si on a peu de données (ce qui n’est pas vraiment le cas ici).
Bref, j’aurais tendance à être plutôt d’accord avec @imparibus. Maintenant, je suis nul en sondage, donc si quelqu’un a d’autres idées, je suis preneur ! Surtout que j’ai peut-être fait quelques erreurs de calculs ici ou là….

Copules et risques corrélés

https://blogperso.univ-rennes1.fr/arthur.charpentier/public/perso2/.copula-density-proj_m.jpg

J’avais promis dans un commentaire que je mettrais bientôt en ligne un survey sur les copules…. après plusieurs mois de retard, le document est en ligne [pdf], et il est sobrement intitulé copules et risques multiples. Toutes les remarques et critiques sont les bienvenues ! Il s’agit d’un chapitre pour un livre dont je mettrais la référence en ligne ultérieurement. A priori, ce document devrait servir de base pour le cours qui sera donné dans un mois au CIRM (mentionné ici, dans le cadre des Journées d’Études Statistiques).

Quelques heures d’effervescence sur Twitter

Pour ceux qui dormaient entre 11 heures et 15 heures (à Montréal, soit 17 heures – 21 heures en France), hier, Bernard Clavel est mort. Auparavant, j’allais sur le site de Libé, ou du Monde, pour me tenir informé de ce qui se passe en dehors de mon bureau (ou de ma cuisine),

Maintenant je suis sur Twitter… et autant l’avouer, j’ai essayé des outils comme TweetDeck mais au bout de 2 heures, force est de constater que j’ai arrêté l’application car j’en avais marre d’être harcelé par ces fenêtres…
Sur Twitter, tout le monde a quelque chose à dire sur tout, et ne peut s’empêcher de vouloir le dire à tout le monde…. Par exemple “Bernard Clavel” ne faisait pas franchement parti des mots tapé régulièrement sur Twitter…. Mais à l’annonce de sa mort, tout le monde veut diffuser l’information à son réseau…. Ça allait tellement vite que j’étais obligé de faire des backups des pages internets tous les quarts d’heure (sinon l’historique disparaît, ce qui limite l’intérêt des outils statistiques). Pour être précis, ma recherchait était

http://twitter.com/#search?q=bernard%20clavel

et pendant près de 4 heures, ça allait du tweet original, au retweet, au message recopié sans citation, etc…. J’ai récupéré ainsi plus de 400 tweets, mais sans l’horaire…. Finalement, j’ai découvert

http://search.tweetreports.com/search_results.php?search=bernard+clavel&sear=Y

Pendant l’heure qui suit les premiers tweets, c’est l’effervescence, puis ça retombe… avec un pic à 20 heures, visiblement certains l’apprenant aux informations du soir…

Manifestement la loi gamma (la date initiale étant le premier tweet annonçant le décès) n’est pas adaptée…

Moralité, pour poursuivre le billet de la semaine dernière (ici), on peut tenter un mélange, en l’occurrence un mélange gamma/exponentielle…. la première loi gamma permet d’intégrer le délai de transmission de l’information au réseau, alors que pour le second, il semble que ce soit une annonce au 20 heures qui ait déclenché la soudaine envie de tweeter..

Allez, le jour où je maîtrise mieux les outils linguistiques, je regarde en plus quand les tweets anglophone et hispaniques sont arrivés…..

Journées d’Etudes Statistiques, 2010

Cette année, les Journées d’Études Statistiques seront organisées du lundi 15 novembre au vendredi 19 (ici pour les inscriptions) au CIRM, à Marseille, et portera cette année sur les approches statistiques du risque.

Les journées sont organisées par Jean Jacques Droesbeke, Gilbert Saporta et Christine Thomas-Agnan. Et parmi les intervenants, on retrouvera Patrice Bertail, Anne Laure Fougères, Stéphane Loisel, Jean Marc Tallon, ou encore Eric Parent. Les journées de 2008 portaient sur les variables latentes et les mélanges (ici) et celles de 2006 sur les méthodes nonparamétriques en régression. Les contributions sont d’ailleurs régulièrement publiées. A suivre donc…

Too large datasets for regression ? What about subsampling….

recently, a classmate working in an insurance company told me he had too large datasets to run simple regressions (GLM, which involves optimization issues), and that they were thinking of a reward for the one who will write the best R-code (at least the fastest). My first idea was to use subsampling techniques, saying that 10 regressions on 100,000 observations can take less time than a regression on 1,000,000 observations. And perhaps provide also better results…

  • Time to run a regression, as a function of the number of observations

Here, I generate a dataset as follows

https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp01.png

and we fit

https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp02.png

where https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp03.png is a spline function (just to make it as general as possible, since in insurance ratemaking, we include continuous variates that do not influence claims frequency linearly in the score). Yes, there might be also useless variables, including one of them which is strongly correlated with one that has an impact in the regression. The code to generate the dataset is simply

> n=10000
> X1=rexp(n)
> X2=sample(c("A","B","C"),size=n,replace=TRUE)
> X3=runif(n)
> Z=rmnorm(n,c(0,0),matrix(c(1,0.8,.8,1),2,2))
> X4=Z[,1]
> X5=Z[,2]
> X6=X1^2
> E=runif(n)
> lambda=.2*X5-4*dbeta(X3,2,5)+X1+
+1*(X2=="A")-2*(X2=="B")-5*(X2=="C")
> Y=rpois(n,exp(lambda))
> base=data.frame(Y,X1,X2,X3,X4,X5,X6,E)

We would like the study the time it takes to run a regression, as a function of the size (i.e. the number of lines https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp04.png) of the dataset.

> system.time( glm(Y~bs(X1)+X2+X3+X4+
+ X5+X6+offset(log(E)),family=poisson,
+ data=base) )
utilisateur     système      écoulé
0.25        0.00        0.25

Here, the time I look at is the last one. But so far, it was rather simple, but it is not the best model I can get. Let us use a stepwise (backward) variable selection,

> system.time( step(glm(Y~bs(X1)+X2+X3+
+ X4+X5+X6+offset(log(E)),family=poisson,
+ data=base)) )
Start:  AIC=2882.1
Y ~ bs(X1) + X2 + X3 + X4 + X5 + X6 + offset(log(E))
Step:  AIC=2882.1
Y ~ bs(X1) + X2 + X3 + X4 + X5 + offset(log(E))
Df Deviance    AIC
<none>        2236.0 2882.1
- X5      1   2240.1 2884.2
- X4      1   2244.1 2888.2
- X3      1   4783.2 5427.3
- X2      2   5311.4 5953.5
- bs(X1)  3   6273.7 6913.8
utilisateur     système      écoulé
1.82        0.03        1.86

Finally, from the first regression, we have points in black (based on 200 simulated datasets), and with a stepwise procedure, we have the points in red.

i.e. it might look linear (proportional), but if it was linear, then on a log-log scale, we should have also straigh lines, with slope 1,

Actually, it looks like a convex function.

The interpretation of that convexity might lead to misinterpretation. On the graph below on the left, on a dataset two times bigger than the previous one (black point) will be less than two times longer to run, while on the right, it will be more than two timess longer,

Convexity can simply be interpreted as “too large datasets take time, and too small too…”. Which is a first step: it should be interesting, in some cases, to run several regressions on smaller datasets….

  • Running 100 regressions on 100 lines, or running 1 regression on 10,000 lines ?

Here, we have datasets with https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp04.png=200,000 lines. The questions is how long will it take if we subdived into https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp05.png subsamples (of equal size), and run https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp05.png regressions ?

> nk=trunc(n/k)rep(1:k,each=nk); nt=nk*k
> base=data.frame(Y[1:nt],X1[1:nt],
+ X2[1:nt],X3[1:nt],X4[1:nt],X5[1:nt],
+ X6[1:nt],E[1:nt],classe)
> system.time( for(j in 1:k){
+  glm(Y~bs(X1)+X2+X3+X4+X5+
+ X6+offset(log(E)),family=poisson
+ ,data=base,subset=classe==j) })
utilisateur     système      écoulé
1.31        0.00        1.31
> system.time( for(j in 1:k){
+      step(glm(Y~bs(X1)+X2+X3+
+ X4+X5+X6+offset(log(E)),family=
+ poisson,data=base,subset=classe==j)) })
Start:  AIC=183.97
Y ~ bs(X1) + X2 + X3 + X4 + X5 + X6 + offset(log(E))

[…]

  Df Deviance    AIC
<none>        117.15 213.04
- X2      2   250.15 342.04
- X3      1   251.00 344.89
- X4      1   420.63 514.53
- bs(X1)  3   626.84 716.74
utilisateur     système      écoulé
11.97        0.03       12.31

On the graph below, we have the time (y-axis, here on a log scale) it took to run https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp05.png regression on samples of size https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp06.png, as function of https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp05.png (x-axis), including the time it took to run the regression on a dataset of size https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp04.png which is the concentration of dots on the left (i.e. https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp05.png=1), both on the 6 regressors – in black – and with a strepwise procedure – in red. One has to keep in mind that I did not remove the printing option in the stepwise procedure, so it might be difficult to compare the two clouds (black vs. red). Nevertheless, we clearly see that if we run https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp05.png regression on samples of size https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp06.png, when https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp05.png is not too large, i.e. less than 10 or 15, it is not longer than the regression on https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp04.png=200,000 lines.

So here we see that running 100 regressions on 2,000 lines is longer than running 1 regression on 200,000 lines… But maybe we are not comparing things that are actually comparable: what if it takes a bit longer, but we strongely improve the quality of our estimators ?

  • What about the quality of the output ?

Here, we consider only one dataset, with https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp04.png=100,000 lines (just to make it run a bit faster). And https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp05.png=20 subsets. Recall that the generated dataset is from

https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp01.png

and we fit

https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp02.png

Here, we plot here https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp07.png and a confidence interval, defined as

https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp08.png

The lightblue segment is the initial estimator, while the blue one is obtained from the stepwise procedure. The grey area represent the estimation on the overall sample, while the https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp05.png segments on the right are the https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp05.png estimators (each on samples of size https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp06.png).

We can see that we have much more volatility on those https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp05.png estimators, but the average (horizontal doted lines) are not so bad… The true value (i.e. the one used to generate the dataset is the dotter black horizontal line).
And if we repeat that on 1,000 simulated dataset, we obtaind the following distribution for https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp07.png (blue line), so we have an unbiased estimator of our parameter (the verticular line being here the true value), here including a stepwise procedure,

But if we add the the red curve is the average of the https://f-origin.hypotheses.org/wp-content/blogs.dir/253/files/2016/11/largesamp09.png the previous one being now the clear blue line in the back, we see that taking average of estimators on subsamples is not bad at all, on the contrary,

and for those who think that the stepwise procedure is a mistake, here is what we get without it,

So what we can see is that running 20 regressions can take (a little) more time (from what we’ve seen earlier) than running only one on the whole dataset…. but it provides better estimates. So the tradeoff is not that simple, and maybe running several regressions on huge datasets can be a proper alternative.