De là à en faire un papier…

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 https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ02.png 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 https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ04.png 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 https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ60.png 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 https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ01.png 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 https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ01.png quand https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ61.png. Mais comme ça n’a que peu d’intérêt, je trouve, on va regarder ce qui se passe à https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ60.png fixé.
Knuth note que https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ05.png et que https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ06.png. 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 https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ62.png, 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 https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ03.png chances d’atteindre un point bleu, et https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ02.png chances d’atteindre un point rouge, dont l’espérance vaut ici

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

En continuant un peu, on obtient que

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

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é https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ03.png, et je m’en rapproche avec probabilité https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ02.png.

Comme tout à l’heure, on compte les probas d’arriver sur les différents points. On a https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ09.png chances d’atteindre un point violet, https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ10.png chances d’atteindre un point bleu, et enfin https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ11.png chances d’atteindre un point rouge (il suffit d’étudier toutes les trajectoires possibles). Au total, on arrive à

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

qui se simplifie en

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

Quant aux conditions de bord, on notera que https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ14.png et que https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ1.png. 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 https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ16.png la même quantité, avec m le nombre de portions dans le distributeur et https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ60.png 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 https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ17.png, avec les conditions de bord de la forme https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ18.png.
On peut aussi noter (il suffit de regarde sur le dessin en haut) que

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

La preuve plus propre est que

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

or comme https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ21.png 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 https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ22.png, alors

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

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

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

or https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ25.png (comme on l’a montré) et

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

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

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

Bref, on retombe sur le résultat précédant. On peut alors faire le calcul en fonction des valeurs de https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ02.png (que l’on fixera, puis de m et https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ60.png),

> 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 https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ28.png. 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 https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ29.png, 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 https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ30.png,

autrement dit, on risque constament de se retrouver à court… Ce qui est marrant (?) c’est le cas où https://perso.univ-rennes1.fr/arthur.charpentier/latex/PQ31.png: 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]


Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.