mais mon blog est l’endroit rêvé pour exposer mes interrogations récurentes. Je ne sais pas si vous avez remarqué, mais au toilettes, au bureau, il y a (généralement) du papier toilette dans un distributeur, et souvent, un rouleau qui traîne à côté….  et régulièrement, je me demande quelle peut être la stratégie optimale: prendre la papier du distributeur ou le papier du rouleau qui traîne…? car mine de rien, la personne chargée du réapprovisionement ne semble intervenir que si l’un des deux est vide.. autrement dit, si les deux diminuent trop vite ensemble, on risque d’avoir un problème un jour. Bon, ce qui me rassure, c’est que Donald Knuth avait remarqué des choses similaires, et avait eu la prétention de publier ses observations dans le American Mathematical Monthly. En fait, pour formaliser le problème, on note  la probabilité que les gens utilisent du papier dans le rouleau le plus plein (on suppose connaître la quantité restant dans le distributeur qui dispose d’une fenêtre transparente), et  la probabilité de piocher dans le plus petit rouleau. Et quand les deux font la même taille, on choisit au hasard (avec probabilités 1/2). On suppose que les rouleaux sont valables pour  utilisateurs (je n’introduis pas de d’aléa, voire de dépendance en fonction du menu à la cantine). On parlera de portions. En gardant les notation de Knuth, on note  l’espérance du nombre de portions restant sur le rouleau restant dès que l’un est terminé. Le but du papier de Knuth était d’étudier le comportement de  quand . Mais comme ça n’a que peu d’intérêt, je trouve, on va regarder ce qui se passe à  fixé.
Knuth note que  et que . En fait, histoire d’épater les filles, Donald prétend que on peut obtenir facilement les résultats suivants

Pour le premier, c’est trivial, et pour le second, on peut faire un dessin (oui, je suis très dessin en ce moment),

A partir de la diagonale (points verts), il y a égalité entre les paquets, et donc on choisit avec probabilité 1/2. Pour calculer , on note qu’il y a deux issues possibles, soit il reste 1 portion sur le rouleau non vide (les points rouges) soit il reste 2 portions sur le rouleau non vide (les points bleus). Les probabilités de passer d’un point à l’autre sont indiquées sur le dessin. Bref, on a  chances d’atteindre un point bleu, et  chances d’atteindre un point rouge, dont l’espérance vaut ici

En continuant un peu, on obtient que

En effet, sur notre petit dession, on rajoute juste les points autours, les valeurs à l’intérieur restant inchangées, et pour faire simple, je m’éloigne de la diagonale avec probabilité , et je m’en rapproche avec probabilité .

Comme tout à l’heure, on compte les probas d’arriver sur les différents points. On a  chances d’atteindre un point violet,  chances d’atteindre un point bleu, et enfin  chances d’atteindre un point rouge (il suffit d’étudier toutes les trajectoires possibles). Au total, on arrive à

qui se simplifie en

Quant aux conditions de bord, on notera que  et que . En fait, on peut étudier un problème plus général, mais plus réaliste: les paquets dans les distributeurs sont souvent beaucoup plus gros que celui qui traîne. On peut donc noter  la même quantité, avec m le nombre de portions dans le distributeur et  dans le rouleau qui traîne. Si on a compris le dessin ci-dessus, on se doute que ça ne change pas grande, chose, ormis que l’on ne commence pas sur la diagonale…
En fait, on note que , avec les conditions de bord de la forme .
On peut aussi noter (il suffit de regarde sur le dessin en haut) que

La preuve plus propre est que

or comme  par une symmétrie du problème, on a l’égalité. En utilisant l’idée de la preuve du résultat précédant (et le dessin, comme toujours), si , alors

Bref, on est capable de faire tous les calculs de manière récursive et relativement simple (pour ceux qui compte le faire la prochaine fois qu’ils vont aux toilettes, il faudra peut être emmener quand même leur ordinateur). On note que

or  (comme on l’a montré) et

On a tout cette fois ci pour vérifier le calcul “facile” évoqué par Donald,

Bref, on retombe sur le résultat précédant. On peut alors faire le calcul en fonction des valeurs de  (que l’on fixera, puis de m et ),

> p=0.4
> q=1-p
> m=50
> n=50
> M=matrix(NA,m+1,n+1)
> M[,1]=seq(0,m)
> M[1,]=seq(0,n)
> M[2,2]=2-p
> for(i in 3:(m+1)){
+ for(j in 2:(i-1)){
+ M[i,j]=p*M[i-1,j]+q*M[i,j-1]
+ }
+ M[i,i]=M[i,i-1]
+ }
> for(i in 2:(m)){
+ for(j in (i+1):(n+1)){
+ M[i,j]=M[j,i]
+ }}
> colnames(M)=seq(0,n)
> rownames(M)=seq(0,m)
> image(seq(0,n),seq(0,n),M,)
> contour(seq(0,n),seq(0,n),M,add=TRUE,
+ levels=seq(0,50,by=5))

Voilà ce que l’on obtient si . le nombre de portions qui reste dès que l’un des rouleaux est fini peut se visualiser sur le graphique suivant, la couleur rouge correspond aux cas un peu dangereux où il reste peu de feuilles dans le rouleau, les zones jaunes indiquant au contraire des niveaux plus élevés,

Avec , on obtient

Autrement dit, il reste toujours du papier sur l’autre dès lors que les gens pensent à alterner suffisement (ici 95% des utilisateurs) alors que pour ,

autrement dit, on risque constament de se retrouver à court… Ce qui est marrant (?) c’est le cas où : s’il y autant de personnes qui piochent dans le gros paquet ou dans le petit, alors il y a de fortes chances pour que les deux rouleaux soient vides dès que l’un l’est…

[ce billet a été initialement posté sur freakonometrics.blog.free.fr/… en mai 2010]

---

---