Les vacances d'hiver sont enfin là, l'occasion pour ce blog de revêtir ses habits de Noël. Il me fallait un sujet de saison, un sujet familial qui plaise à tous. C'est donc tout naturellement que je vais aujourd'hui parler de l'épineux problème du papier toilette. Ce n'est pas moi qui ai commencé, mais Donald Knuth (l'inventeur du TEX) dans son papier "The toilet paper problem" publié en 1984 dans l'American Mathematical Monthly ! Là, c'est vraiment Noël avant Noël !

Je sais pas où mettre mon 42, alors je le mets làLe PQ mathématique Renova, en vente dans tous les bons magasins. Le cadeau de Noël idéal.

Le Toilet Paper Problem
Vivons l'espace de quelques instants la vie d'un responsable petits coins d'une grande société. Pour éviter les manques, chaque cabinet possède deux rouleaux de papier toilette. Il existe cependant deux types d'usagers de toilettes : les grands-choisisseurs et les petits-choisisseurs.
Quand ils ont le choix, les grands-choisisseurs utilisent toujours le rouleau le plus plein, alors que les petits-choisisseurs se serviront de celui qui est le plus entamé. Quand les deux rouleaux sont de même taille, le plus proche sera utilisé. C'est quand les deux rouleaux sont vides qu'il faut commencer à s'inquiéter. A quel point faut-il redouter ce problème ? Quand un rouleau arrive à son terme, qu'en est-il de l'autre ? C'est ça, le Toilet Paper Problem !

Supposons qu'un utilisateur ait une probabilité p d'être un grand-choisisseur et une probabilité q=1-p d'être un petit-choisisseur. Au matin, les deux rouleaux sont de longueur n, et chaque usager ne se servira que d'une seule feuille (ou du moins, d'une seule unité de PQ) lors de son passage. On s'intéresse à Mn(p), le nombre moyen de portions de papier toilette restant quand l'un des deux rouleaux arrive à son terme.

On peut procéder à quelques calculs simples :

Mn(1) = 1. Si chaque usager est un grand-choisisseur, les deux rouleaux seront choisis alternativement. Après 2n-1 passages, il ne restera plus qu'une seule feuille.
Mn(0) = n. Si tous les utilisateurs sont des petits-choisisseurs, un seul rouleau sera utilisé à partir du moment où il sera entamé. Quand il sera vidé, l'autre sera toujours intact.
M1(p) = 1. Quelle que soit la personne qui rentre, si chaque rouleau n'a qu'une feuille, il n'en restera plus qu'une quand il resortira.

M2(p) = 2-p. Pour s'en convaincre, on peut se faire un petit arbre de probabilités

M2pM2(p) = 1×p + 2×(1-p) = 2-p

M3(p) = 3-2p-p2+p3 : de la même façon, on peut se faire un arbre de probabilités (bien qu'à ce niveau là, il faudrait plutôt envisager un graphe).

M3p


M3(p) = 1×p2 + 2×p.q + 1×p2.q + 2×p.q2 + 3×q2 
= 3-2p-p2+p3

Récursivité
Pour généraliser ces calculs, introduisons la notation Mm,n(p), le nombre moyen de feuilles restant quand l'un des rouleaux est vidé si l'on part d'un rouleau à m feuilles et d'un autre à n feuilles. On supposera n>m.

Par définition, on a :

Mn,n(p) = Mn(p)
M0,n(p) = n

Quand les deux rouleaux sont égaux (et non vides), on se sert sur le premier rouleau, ce qui donne :

Mn,n(p) = Mn-1,n(p) si n>0

Sinon, le premier rouleau est plus petit que le deuxième. Il y a alors une probabilité p de se servir sur le deuxième et une probabilité q sur le premier :

Mm,n(p) = p.Mm,n-1(p) + q.Mm-1,n(p) si n>0

On peut ainsi calculer que M4(p) = 4-3p-2p2+p3+4p4-2p5.

Cette formulation récursive permet de visualiser l'ensemble des chemins possibles par le graphe suivant:

graphe_PQSi un chemin commence sur la diagonale en (n;n), il part en (n-1;n). Il a alors deux choix : aller en (n-1;n-1) ou en (n-2;n).

La valeur de Mm,n(k) peut être alors vue comme la somme, pour k∈[1..n], de k fois la somme du poids des chemins de (m;n) à (0;k), le poids d'un chemin étant le produit de ses arcs.

Notons ck le nombre de chemins allant de (n;n) à (n-k;n-k) qui ne passent pas par la diagonale. Un tel chemin a pour poids pk.qk-1
On note également dn,k le nombre de chemins allant de (n;n) à (1;k) sans passer par la diagonale. Ces chemins ont pour poids pn-k.qn-1.
Du coup, si un chemin part de (n;n), soit il repasse par la diagonale en (n-k;n-k), soit il n'y repasse pas. On traduit ceci par :

Mnp(où la deuxième somme vaut 1 si n=1)

On peut reconnaître dans les ck les nombres de Catalan, et dans les dn,k les nombres qui apparaissent dans le problème du scrutin de Bertrand ("ballot problem").

Catalan

Finalement ?
En considérant la série génératrice de Mn(p) devenue calculable grâce à l'apparition de termes biens connus, il est possible d'observer le comportement de Mn(p) pour n grand. Le cas p=q est une simple marche aléatoire 1D. (Je vous renvoie à l'article de Knuth pour les détails).

ResultatsFormule valable pour n aussi grand que p est proche de q.

Supposons qu'il y ait un grand nombre (n) de feuilles dans les deux rouleaux du départ. S'il y a deux fois plus de grands-choisisseurs que de petits-choisisseurs (p=2/3), il restera environ 2 feuilles quand l'un des rouleaux arrivera à son terme. Dans le cas contraire (p=1/3), il en restera environ n/2+1.

Finalement, les résultats sont conformes à l'intuition : si les grand-choisisseurs sont majoritaires (p>q), il ne restera que très peu de feuilles disponibles quand l'un des rouleaux sera à sec. Dans le cas contraire, le papier toilette restant sera proportionnel à la taille des rouleaux !

courbePQCourbe du nombre moyen de feuilles de papier toilette restant dans le cas critique où un rouleau est terminé en fonction de la probabilité p de tomber sur un grand choisisseur. (Cas n=16)


Sources : 
The toilet paper problem, par Donald Knuth