Claude Elwood Shannon naît le 30 avril 1916 à Petoskey, dans le Michigan, et grandit dans la petite ville voisine de Gaylord. Enfant, il construit des modèles réduits d'avions, un bateau radiocommandé, et un télégraphe avec un ami en utilisant le fil de fer barbelé d'une clôture. Son héros est Thomas Edison, dont il apprendra plus tard qu'il est un lointain cousin. À l'université du Michigan, il obtient en 1936 deux diplômes à la fois, l'un en mathématiques, l'autre en génie électrique : toute sa carrière se fera à la frontière entre les deux.

Au MIT, Shannon s'occupe de l'analyseur différentiel de Vannevar Bush, une énorme machine à engrenages qui résout des équations différentielles, pilotée par des centaines de relais électriques (des interrupteurs commandés par un courant). Il remarque que ces circuits d'interrupteurs obéissent à la même logique que l'algèbre de George Boole (1854), une algèbre où les variables ne valent que $0$ ou $1$ :

• deux interrupteurs en série laissent passer le courant si le premier et le second sont fermés : c'est le « ET » logique, qui se calcule comme un produit $a \times b$ ;
• deux interrupteurs en parallèle laissent passer le courant si l'un ou l'autre est fermé : c'est le « OU » logique.

Son mémoire de 1937, A Symbolic Analysis of Relay and Switching Circuits, montre qu'on peut donc calculer avec des circuits, et simplifier un circuit en simplifiant une formule. Il montre même comment construire un additionneur en binaire. Tous les processeurs d'aujourd'hui reposent sur cette idée. On cite souvent le jugement du psychologue Howard Gardner, pour qui ce serait « probablement le mémoire de master le plus important du siècle ».

Sa thèse de doctorat (1940), elle, porte sur une algèbre pour la génétique des populations : Shannon passe d'un sujet à l'autre au gré de sa curiosité.

En 1941, il entre aux laboratoires Bell, le centre de recherche de la compagnie de téléphone américaine. Pendant la guerre, il travaille sur la conduite de tir et sur la cryptographie, en particulier le système chiffré qui permettait à Roosevelt et Churchill de se parler par téléphone. En 1943, Alan Turing, venu de Grande-Bretagne pour ce même projet, passe deux mois aux laboratoires Bell : les deux hommes déjeunent ensemble à la cafétéria et parlent de machines qui penseraient, sans pouvoir évoquer leurs travaux secrets.

Shannon rédige en 1945 un rapport confidentiel, publié en 1949, qui fonde la cryptographie comme une science : il y démontre que le masque jetable (une clé aléatoire aussi longue que le message, utilisée une seule fois) est incassable, et que c'est le seul type de chiffrement qui le soit.

En 1948 paraît A Mathematical Theory of Communication. Shannon y mesure l'information en bits (mot proposé par son collègue John Tukey), définit l'entropie d'une source, et démontre qu'on peut transmettre des messages sans erreur sur une ligne bruitée, à condition de ne pas dépasser une certaine capacité. La compression des fichiers, les codes correcteurs des QR codes, la téléphonie mobile et internet découlent de cet article. On y revient plus bas.

Shannon est aussi un joueur infatigable. On le voit traverser les couloirs des laboratoires Bell en monocycle, parfois en jonglant. Il établit une formule sur le jonglage, construit des machines à jongler, une calculatrice qui travaille en chiffres romains, un programme d'échecs théorique (son article de 1950 fonde la programmation des jeux par ordinateur) et la « machine ultime », une boîte dont le seul interrupteur, quand on l'actionne, fait sortir une main qui l'éteint.

Le labyrinthe de Thésée (1950), exposé au musée du MIT. Sous le plateau, des relais déplacent un aimant qui guide la souris. Elle explore le labyrinthe, mémorise les bons choix à chaque case, et retrouve ensuite directement le « fromage » : c'est l'une des premières machines capables d'apprendre. Photo Daderot, domaine public (CC0), Wikimedia Commons.

En 1956, il revient au MIT comme professeur. C'est là qu'en 1960 un jeune enseignant de mathématiques, Edward Thorp, vient lui demander de présenter un article sur le blackjack à l'Académie des sciences américaine, dont Shannon est membre. La conversation dérive vers la roulette.

On gagne $1$ euro si la bille tombe sur l'une des $18$ cases rouges, on perd sa mise sinon (18 noires et le zéro). Le gain $G$ est une variable aléatoire qui prend les valeurs $1$ et $-1$ :

En moyenne, le joueur perd environ $2{,}7$ centimes par euro misé. C'est le zéro qui fait la différence : sans lui, le jeu serait équitable.

Miser sur un seul numéro (un « plein ») rapporte $35$ fois la mise. Avec $1$ euro, le gain $G'$ vaut $35$ avec probabilité $\frac{1}{37}$, et $-1$ sinon :

C'est la même espérance. Plus généralement, si une mise couvre $k$ cases et paie $\dfrac{36}{k} - 1$ fois la mise (c'est la règle des casinos), alors

Aucune combinaison de mises ne change rien, puisque l'espérance d'une somme est la somme des espérances. Et la loi des grands nombres dit que plus on joue de parties, plus il est probable que le gain moyen par partie soit proche de $-\frac{1}{37}$ : à la longue, le casino gagne presque sûrement. La seule façon de renverser le signe, c'est de savoir quelque chose que le casino ne sait pas.

La plus célèbre recette, la martingale, consiste à doubler sa mise après chaque perte. Après $n$ pertes de suite, on a perdu $1 + 2 + \dots + 2^{n-1} = 2^n - 1$ euros (somme géométrique), et la mise suivante vaut $2^n$ euros. Un gain final ne rapporte qu'un euro, alors que dix pertes de suite (probabilité $\left(\frac{19}{37}\right)^{10} \approx 0{,}13\,\%$) obligent à miser $1\,024$ euros, souvent au-delà du plafond de la table. L'espérance de chaque coup restant $-\frac{1}{37}$ fois la mise, aucun système ne transforme un jeu perdant en jeu gagnant. Giacomo Casanova, qui pratiquait la martingale à Venise, raconte s'être retrouvé « sans le moindre sequin ».

Simplifions beaucoup. La bille tourne sur le bord avec une vitesse de rotation $\omega(t)$, en tours par seconde, qui diminue à cause des frottements. On suppose qu'elle diminue de façon affine :

où $\omega_0$ est la vitesse au départ et $\alpha$ un ralentissement constant (en tours par seconde, chaque seconde). La bille quitte le bord quand sa vitesse descend à une valeur $\omega_c$ fixée par la pente de la roue, à l'instant $T = \dfrac{\omega_0 - \omega_c}{\alpha}$.

Le nombre de tours parcourus est l'intégrale de la vitesse :

En remplaçant $T$ par sa valeur et en simplifiant, on obtient

Exemple à la main. Avec $\omega_0 = 2$ tours par seconde, $\alpha = 0{,}12$ et $\omega_c = 0{,}5$ : $\theta = \dfrac{4 - 0{,}25}{0{,}24} = 15{,}625$ tours. Ces valeurs sont choisies pour l'exemple ; ce ne sont pas des mesures de Thorp.

Pour connaître $\omega_0$, le joueur appuie avec l'orteil sur un interrupteur quand la bille passe devant un repère, puis quand elle y repasse un tour plus tard : la durée d'un tour donne la vitesse. Mais une mesure n'est jamais parfaite. Quelle erreur sur $\theta$ produit une petite erreur $\Delta\omega_0$ ? La dérivée répond :

et, pour une petite erreur, l'approximation par la tangente donne $\Delta\theta \approx \theta'(\omega_0) \times \Delta\omega_0$. Avec les valeurs précédentes, $\theta'(2) \approx 16{,}7$. Une erreur de $0{,}01$ tour par seconde (soit $0{,}5\,\%$) donne une erreur d'environ $0{,}17$ tour, c'est-à-dire environ $6$ cases sur $37$.

La prédiction est donc très sensible à la mesure : il faut chronométrer un tour à quelques millièmes de seconde près. C'est pourquoi l'ordinateur ne désignait pas un numéro, mais une zone de la roue.

L'appareil de Thorp et Shannon tenait dans un paquet de cigarettes. Le joueur actionnait avec l'orteil un interrupteur caché dans sa chaussure, à quatre moments, pour mesurer la vitesse du cylindre et celle de la bille. Un fil courait jusqu'à une oreillette minuscule qui jouait l'une de huit notes, une gamme d'une octave : chaque note désignait un huitième de la roue, soit cinq numéros voisins sur le cylindre (mais dispersés sur le tapis). Le joueur misait alors sur ces cinq numéros.

Ils ont estimé leur gain à environ $44\,\%$ de la somme misée. Combien de fois faut-il tomber juste pour cela ? Misons $1$ euro sur chacun des $5$ numéros annoncés, et notons $q$ la probabilité que la bille tombe dans l'un d'eux. Si c'est le cas, un plein rapporte $35$ euros et les quatre autres mises sont perdues : gain $35 - 4 = 31$. Sinon, on perd les $5$ euros. L'espérance vaut

• sans information, $q = \dfrac{5}{37} \approx 0{,}135$ et $E = -\dfrac{5}{37}$ : la perte habituelle ;
• le jeu devient favorable dès que $36q - 5 > 0$, c'est-à-dire $q > \dfrac{5}{36} \approx 0{,}139$ ;
• pour gagner $44\,\%$ des $5$ euros misés, soit $2{,}2$ euros, il faut $36q = 7{,}2$, donc $q = 0{,}2$.

Il suffit donc que la bille tombe dans la zone annoncée une fois sur cinq au lieu d'une fois sur sept et demie pour que l'avantage change de camp. Une information très imparfaite suffit.

Le programme suivant reprend le modèle. Pour chaque lancer, il tire une vitesse réelle, une mesure entachée d'une erreur relative au plus égale à erreur, et un rebond aléatoire de la bille dans les cases (au plus 8 cases de part et d'autre). Il compte la fréquence $q$ des lancers où la bille tombe dans les 5 cases annoncées, puis le gain moyen espéré $\frac{36q - 5}{5}$ par euro misé.

Avec une mesure parfaite, la fréquence $q$ est voisine de $0{,}3$ (les rebonds empêchent d'aller au-delà) et le jeu est très favorable. Quand l'erreur de mesure atteint quelques pour cent, $q$ retombe autour de $\frac{5}{37} \approx 0{,}135$ (ou même en dessous) et le gain redevient négatif : l'information a disparu. Tout se joue sur la précision du chronométrage.

Thorp et Shannon ont testé l'appareil à Las Vegas en 1961, avec leurs épouses. Il fonctionnait, mais les fils, très fins, cassaient souvent, et l'oreillette menaçait de tomber : ils ont misé de petites pièces et n'ont pas cherché à faire fortune. Thorp n'a révélé l'existence de l'appareil que plusieurs années plus tard. Depuis 1985, la loi du Nevada interdit d'utiliser au casino un appareil qui aide à prédire le résultat d'un jeu.

Une « main naturelle » (un blackjack) est formée de deux cartes : un as et une carte qui vaut $10$ (dix, valet, dame ou roi). Dans un paquet neuf de $52$ cartes, il y a $4$ as et $16$ cartes de valeur $10$. On tire deux cartes. Notons $A_1$ « la première carte est un as », $D_1$ « la première carte vaut 10 », et de même $A_2$, $D_2$ pour la seconde.

La branche « autre » du premier tirage ne peut pas donner de blackjack. D'après la formule des probabilités totales (les deux chemins qui mènent à un blackjack sont incompatibles) :

avec $P(A_1 \cap D_2) = P(A_1)\,P_{A_1}(D_2)$ et de même pour l'autre chemin. Donc

Environ une main sur vingt est un blackjack. Les nombres $\frac{16}{51}$ et $\frac{4}{51}$ sont des probabilités conditionnelles : une fois la première carte connue, il ne reste que $51$ cartes, et leur composition a changé.

Supposons qu'après plusieurs mains, il reste $26$ cartes, dont $3$ as et $10$ cartes de valeur $10$. Le même arbre donne maintenant

La probabilité a presque doublé. Or le joueur qui obtient un blackjack est payé une fois et demie sa mise, alors que le croupier qui en obtient un ne gagne que la mise : un paquet riche en as et en dix favorise le joueur. À l'inverse, un paquet riche en petites cartes favorise le croupier, qui doit tirer jusqu'à $17$ et « saute » moins souvent.

Avec l'un des premiers ordinateurs (un IBM 704), Thorp calcule l'avantage du joueur selon les cartes déjà sorties. Le constat est frappant : il suffit de compter les $5$ ; quand les quatre $5$ sont sortis, le jeu devient favorable au joueur. C'est la naissance du comptage des cartes. Le joueur mise peu quand le paquet est défavorable, et davantage quand il est favorable.

En janvier 1961, Thorp présente ses résultats à la réunion de l'American Mathematical Society, à Washington, sous le titre « Fortune's Formula : the Game of Blackjack ». La presse s'en empare. Un joueur fortuné, lié au milieu new-yorkais, lui propose de financer l'expérience : à Reno, avec $10\,000$ dollars, ils repartent avec environ $21\,000$ dollars. En 1962, Thorp publie Beat the Dealer, qui devient un succès de librairie. Les casinos réagissent : ils mélangent plus souvent, utilisent plusieurs paquets à la fois, et refusent les joueurs qui comptent. Compter de tête n'est pas illégal ; mais un casino peut refuser un client.

On joue $n$ fois de suite un pari qui paie à égalité (on gagne ce qu'on mise, ou on le perd), gagné avec une probabilité $p$ supérieure à $\frac{1}{2}$. On note $q = 1 - p$. À chaque coup, on mise une fraction fixe $f$ de son capital, avec $0 \leqslant f < 1$. Un gain multiplie le capital par $1 + f$, une perte par $1 - f$. Après $n$ coups dont $W$ gagnés, le capital vaut

Le nombre $W$ de coups gagnés suit la loi binomiale $\mathcal{B}(n\,;p)$.

L'espérance du capital après un coup est $C\,(p(1 + f) + q(1 - f))$ $= C\,(1 + f(p - q))$, et après $n$ coups indépendants $E(C_n) = C_0\,(1 + f(p - q))^n$. Elle est d'autant plus grande que $f$ est grand : elle est maximale pour $f = 1$, c'est-à-dire en misant tout, à chaque coup.

Mais avec $f = 1$, une seule perte ruine le joueur. Avec $p = 0{,}55$ et $500$ coups, la probabilité de ne jamais perdre est $0{,}55^{500} \approx 1{,}5 \times 10^{-130}$. L'espérance est énorme parce qu'elle est portée par ce cas presque impossible ; dans tous les autres, on a tout perdu. L'espérance n'est pas le bon critère.

Le capital est un produit ; le logarithme le transforme en somme. En notant $F = \dfrac{W}{n}$ la fréquence des coups gagnés :

D'après la loi des grands nombres, plus $n$ est grand, plus il est probable que la fréquence $F$ soit proche de $p$. Le membre de droite est alors proche de

Le capital se comporte donc à peu près comme $C_0\,\mathrm{e}^{n\,g(f)}$ : $g(f)$ est le taux de croissance par coup. C'est lui qu'il faut rendre maximal. On remarque que $g(f)$ est l'espérance de $\ln\frac{C_1}{C_0}$ : Kelly maximise l'espérance du logarithme du capital, et non l'espérance du capital.

Exemple à la main. Avec $p = 0{,}55$, on mise $f^* = 0{,}55 - 0{,}45 = 0{,}10$, soit $10\,\%$ du capital à chaque coup. Alors

Le capital croît d'environ $0{,}5\,\%$ par coup en moyenne géométrique. Après $500$ coups, il est multiplié par environ $\mathrm{e}^{500 \times 0{,}005} = \mathrm{e}^{2{,}5} \approx 12$.

Le paradoxe. Avec $f = 0{,}2$, le double de la fraction de Kelly, $g(0{,}2) = 0{,}55\ln 1{,}2 + 0{,}45\ln 0{,}8$ $\approx -0{,}0001$. Le taux est négatif : chaque pari est favorable, l'espérance du capital augmente, et pourtant le capital diminue presque sûrement à long terme. Miser trop est aussi dangereux que jouer à un jeu défavorable.

Le programme suivant simule $500$ paris gagnés avec une probabilité $p = 0{,}55$, pour plusieurs fractions $f$, et recommence $100$ fois. Il affiche le capital médian (celui du joueur « du milieu ») en partant de $1$ euro. On compare avec la prévision $\mathrm{e}^{500\,g(f)}$.

La fraction $0{,}1$ donne en général la meilleure médiane (le résultat varie d'une exécution à l'autre) ; avec $0{,}2$ le joueur médian ne gagne presque rien, et avec $0{,}4$ il est quasiment ruiné, alors que tous ces paris sont favorables.

Pour Shannon, une information est d'autant plus grande qu'elle est surprenante. Pour une expérience aléatoire à deux issues de probabilités $p$ et $1 - p$, il définit l'entropie, mesurée en bits :

où $\log_2 x = \dfrac{\ln x}{\ln 2}$ est le logarithme de base $2$. Exemples à la main :

• pièce équilibrée : $H\left(\frac{1}{2}\right) = -\frac{1}{2}\log_2\frac{1}{2} - \frac{1}{2}\log_2\frac{1}{2} = 1$ bit ; apprendre le résultat, c'est recevoir exactement un bit ;
• pièce truquée qui tombe sur pile neuf fois sur dix : $H(0{,}9) \approx 0{,}47$ bit : on est rarement surpris ;
• une étude de la fonction $H$ sur $]0 ; 1[$ (sa dérivée vaut $\log_2\frac{1 - p}{p}$) montre qu'elle est maximale en $p = \frac{1}{2}$ : c'est la situation la plus incertaine.

Pour un dé équilibré à six faces, l'entropie vaut $\log_2 6 \approx 2{,}58$ bits. Le texte sur la linguistique quantitative applique l'entropie aux lettres d'une langue.

Reprenons le pari à égalité gagné avec la probabilité $p$, et calculons le meilleur taux $g(f^*)$ avec $f^* = 2p - 1$. Alors $1 + f^* = 2p$ et $1 - f^* = 2q$, donc

(On a utilisé $p + q = 1$ et $\ln x = \ln 2 \times \log_2 x$.) Le meilleur taux de croissance est donc proportionnel à $1 - H(p)$ : l'information que l'on possède en plus du hasard pur. Si $p = \frac{1}{2}$, on ne sait rien, $H = 1$ et l'on ne peut pas s'enrichir. Avec $p = 0{,}55$, $1 - H(0{,}55) \approx 0{,}0072$ bit, et l'on retrouve $g(f^*) \approx 0{,}0050$. Gagner de l'argent avec un avantage, c'est exploiter une information ; la formule de Kelly dit exactement combien elle vaut.