David Madore's WebLog: 2021-06

Vous êtes sur le blog de David Madore, qui, comme le reste de ce site web, parle de tout et de n'importe quoi (surtout de n'importe quoi, en fait), des maths à la moto et ma vie quotidienne, en passant par les langues, la politique, la philo de comptoir, la géographie, et beaucoup de râleries sur le fait que les ordinateurs ne marchent pas, ainsi que d'occasionnels rappels du fait que je préfère les garçons, et des petites fictions volontairement fragmentaires que je publie sous le nom collectif de fragments littéraires gratuits. • Ce blog eut été bilingue à ses débuts (certaines entrées étaient en anglais, d'autres en français, et quelques unes traduites dans les deux langues) ; il est maintenant presque exclusivement en français, mais je ne m'interdis pas d'écrire en anglais à l'occasion. • Pour naviguer, sachez que les entrées sont listées par ordre chronologique inverse (i.e., la plus récente est en haut). Cette page-ci rassemble les entrées publiées en juin 2021 : il y a aussi un tableau par mois à la fin de cette page, et un index de toutes les entrées. Certaines de mes entrées sont rangées dans une ou plusieurs « catégories » (indiqués à la fin de l'entrée elle-même), mais ce système de rangement n'est pas très cohérent. Le permalien de chaque entrée est dans la date, et il est aussi rappelé avant et après le texte de l'entrée elle-même.

You are on David Madore's blog which, like the rest of this web site, is about everything and anything (mostly anything, really), from math to motorcycling and my daily life, but also languages, politics, amateur(ish) philosophy, geography, lots of ranting about the fact that computers don't work, occasional reminders of the fact that I prefer men, and some voluntarily fragmentary fictions that I publish under the collective name of gratuitous literary fragments. • This blog used to be bilingual at its beginning (some entries were in English, others in French, and a few translated in both languages); it is now almost exclusively in French, but I'm not ruling out writing English blog entries in the future. • To navigate, note that the entries are listed in reverse chronological order (i.e., the most recent is on top). This page lists the entries published in June 2021: there is also a table of months at the end of this page, and an index of all entries. Some entries are classified into one or more “categories” (indicated at the end of the entry itself), but this organization isn't very coherent. The permalink of each entry is in its date, and it is also reproduced before and after the text of the entry itself.

[Index of all entries / Index de toutes les entréesLatest entries / Dernières entréesXML (RSS 1.0) • Recent comments / Commentaires récents]

Entries published in June 2021 / Entrées publiées en juin 2021:

↓Entry #2688 [older| permalink|newer] / ↓Entrée #2688 [précédente| permalien|suivante] ↓

(mercredi)

L'histoire des histoires que j'écrivis jadis

J'ai déjà publié un certain nombre d'éléments autobiographiques par ici : outre cette autobiographie couvrant les années 1976–1996, j'avais écrit ce billet de blog sur mon rapport à mon orientation sexuelle, celui-ci sur ma découverte des ordinateurs, et d'autres choses çà et là, comme (ce qui a un rapport avec ce que je veux évoquer ci-dessous) ici sur ma lecture de Tolkien ou bien sur celle d'Asimov. Je voudrais dire ici quelques mots sur les histoires que j'ai moi-même écrites quand j'étais ado, sur ce qu'elles racontent et sur ce qu'elles disent sur moi (même si je les ai déjà évoquées en passant comme ici ou , et plus récemment ). Au minimum, je voudrais raconter un peu quelle est leur intrigue et comment elle m'est venue, et, pour que vous n'ayez pas à les lire vous-mêmes — comment j'ai pu produire des choses aussi mauvaises ou, en tout cas, bizarres. Et ce que j'ai appris à travers elles.

Mon papa m'avait un jour fait la remarque, que je trouve très juste, que quand on enseigne la littérature à l'école, on sélectionne ce qu'il y a de mieux, les meilleures œuvres des plus grands auteurs, et sans doute montrer aux enfants pourquoi c'est si bien écrit, mais peut-être que la médiocrité a en fait autant à nous apprendre que le génie (ne dit-on pas, après tout, qu'il faut apprendre par les erreurs des autres, parce qu'on ne peut pas vivre assez longtemps pour les commettre toutes soi-même ?), ou encore la comparaison entre les deux (peut-on vraiment se rendre compte que Shakespeare est un dramaturge de génie sans le comparer à un autre qui n'en est pas un ? ou d'ailleurs simplement à des moments où il ne l'est pas vraiment — quandoque bonus dormitat Homerus — mais c'est assez tabou de montrer un passage de Shakespeare pour dire là ce n'est franchement pas terrible, alors qu'on osera plus facilement avec un auteur qui a moins marqué toute la civilisation). Et un texte médiocre reflétera en outre peut-être mieux le contexte historique et social dans lequel il a été écrit que celui d'un auteur que sa stature même rend singulier, et qui nécessite sans doute pour être décodé correctement de traverser plusieurs couches d'interprétation et de réinterprétation plaquées par les époques intermédiaires.

Je ne sais pas si mes œuvres forment même un bon exemple de médiocrité, ou même si je peux me mettre en avant comme exemple typique (whatever this means) d'ado qui, nourri d'une pop-culture « tolkienisante » en France dans les années '80–'90, s'est mis à produire son propre sous-Tolkien ou sous-Asimov, mais je peux toujours essayer. Il n'y a pas que le cadre (fantastique ou science-fiction) qui mérite un mot, parce que mes romans disent aussi autre chose sur moi, comme mon obsession pour le mysticisme et la symétrie, et derrière le sous-Tolkien il y a du sous-Oulipo, ou quelque chose comme ça.

Pour redonner un peu de contexte, même si j'ai déjà raconté ça plusieurs fois, j'ai grandi « un pied dedans, un pied dehors » par rapport à une pop-culture que je qualifie ci-dessus de tolkienisante : je n'ai lu The Lord of the Rings qu'à 15 ans (encore une fois, cf. ici ; j'avais lu The Hobbit bien avant), mais j'avais des amis qui l'avaient lu bien avant, et qui m'en avaient parlé, et je m'étais formé une certaine idée de l'œuvre, et surtout, j'avais été exposé à un certain nombre de — comment dire — produits dérivés du Seigneur des Anneaux. Je n'ai pas joué à Dungeons & Dragons (ou peut-être juste une ou deux fois, pour des parties très courtes), mais j'ai côtoyé des gens qui y jouaient beaucoup (ou à d'autres jeux de ce genre), et j'ai assisté à de telles parties, ça m'intéressait plus de m'asseoir à côté du DM et de tout observer que de participer personnellement à l'action ; de même s'agissant des Livres dont Vous Êtes le Héros, je n'y jouais guère (je n'avais pas la patience de prendre les dés pour les combats, suivre les règles, et subir la frustration d'être tué et de recommencer), mais j'aimais quand même les lire, quasi linéairement, en explorant des choix un peu au pif, d'où il résultait d'ailleurs une idée assez confuse de la trame générale de l'intrigue que je découvrais finalement dans un désordre à peu près total ; parfois (surtout en fin d'école primaire, donc vers 10 ans), des amis et moi nous construisions mutuellement des aventures, dans un cadre informel, sans dés ni plateau ni règles précises, nous proposant juste oralement situations et nous invitant à dire ce que nous voulions faire, et ces aventures étaient pleines de magie. Et une autre chose qui m'a beaucoup marqué, ce sont certains jeux d'aventure sur ordinateur : je ne redis pas ce que j'ai déjà écrit ici (ainsi que et ), mais j'ai beaucoup été influencé par la série King's Quest et surtout Ultima.

Je viens de lister quelques uns des ingrédients des mondes de mon imagination, mais il y a autre chose que je devrais surtout essayer de dire c'est : pourquoi la heroic fantasy ? Ce n'est pas uniquement une influence extérieure qui m'a poussé vers ce genre. Il y a bien sûr l'aspect d'avoir besoin de rêver un peu de magie dans un monde qui n'en a pas (et peut-être d'autant plus fortement que, fasciné par les sciences, je devais reléguer le surnaturel à mes rêves et fictions). Mais il y a un autre aspect auquel on pense peut-être moins évidemment que « l'envie de rêver » :

  • Écrire une histoire se déroulant dans le monde réel demande soit une expérience de celui-ci, soit un effort de documentation, qui sont difficilement accessibles quand on est ado, surtout à une époque où Wikipédia n'existait pas et même le Web quasiment pas. (Ou alors on va se limiter à des récits qui se déroulent dans un collège/lycée français, ce qui présente certes des possibilités assez considérables d'exploration psychologique, mais limite sérieusement l'intrigue elle-même. En tout cas, je n'ai jamais eu envie de reproduire dans ce que j'écrivais ce que je vivais déjà chaque jour. Mais en même temps j'étais trop maniaque de la précision pour accepter de simplement ignorer mon ignorance, inventer ce que je ne savais pas, et admettre que je ferais forcément plein d'erreurs.)
  • A contrario, le cadre « médiéval-fanastique tolkienisant standard » offre à la fois suffisamment de références partagées pour pouvoir commencer à écrire une histoire sans perdre une éternité en exposition si on ne le souhaite pas (si je dis elfe, mon lecteur s'imagine quelque chose de vaguement conforme au standard ISO de l'elfe), mais suffisamment de flexibilité pour permettre d'y insérer à peu près n'importe quoi comme intrigue. C'est un cadre générique, peu envahissant, mais hautement paramétrable (à commencer par le réglage critique « niveau et type de magie disponible »), dont on peut faire absolument ce qu'on veut, et où on n'a à se soucier que de cohérence interne sans que qui que ce soit vienne vous reprocher, par exemple, que la rue Servandoni n'existait pas à l'époque où se situe votre roman.

Alors oui, on peut considérer que le cadre médiéval-fantastique tolkienisant standard est un peu cheap, qu'il s'agit du plastique à tout faire d'un million de mondes interchangeables. (J'ai moi-même souvent ressenti l'agacement extrêmement bien décrit ici par Boulet et qui pourrait directement attaquer beaucoup des histoires que j'ai écrites.) Mais on doit savoir gré à Tolkien d'avoir créé ce cadre standard qui ouvre les portes du royaume de l'imagination à mille adolescents qui ne deviendront jamais écrivains mais qui ont besoin de rêver, et peut-être à un qui deviendra écrivain, quitte à rester dans ce cadre mais en en faisant quelque chose de créatif car il est bien sûr possible de dépasser le cliché. (Pour être bien clair, je ne prétends absolument pas que je fantastique soit un genre réservé aux adolescents ou jeunes adultes : je dis juste qu'il est plus facile de se mettre à écrire dans ce cadre quand on est adolescent ou jeune adulte.)

C'est intéressant, parce qu'il semble qu'il (Tolkien) ait voulu créer une mythologie de l'Angleterre, mais ce qu'il a créé est à la fois plus large (dépassant largement l'Angleterre) mais aussi différent. La distinction entre un cadre imaginaire et une mythologie cohérente est assez subtile : il est plus facile d'écrire une histoire dans un monde basé le cadre médiéval-fantastique tolkienisant que sur les mythes grecs, par exemple, ou bien sur le cycle Arthur-Lancelot-Merlin-Graal, parce que ces derniers renvoient à des histoires assez précises avec lesquelles le lecteur s'attendrait à trouver une articulation (qu'il s'agisse de Thésée ou de Perceval, on leur associe plus que des caractéristiques générales, mais des événements bien définis), alors qu'il est beaucoup plus facile d'importer quelques idées des mondes à la Tolkien sans importer toutes les histoires de la Terre du Milieu. Allez savoir pourquoi : peut-être est-ce grâce à Dungeons & Dragons que se sont répandues non seulement l'idée de ce cadre générique mais aussi l'idée encore plus importante que chacun est libre de s'en emparer et d'en faire ce qu'il veut.

L'autre type de cadre dont on peut facilement imaginer s'emparer, c'est la science-fiction (et on peut peut-être croire que, pour moi qui avais une certaine culture scientifique déjà à quinze ans, ç'eût été plus naturel). J'ai certainement été beaucoup influencé par la trilogie originale des films Star Wars (j'ai vu l'épisode VI à sa sortie) et par la lecture du cycle Foundation d'Asimov (je ne vais pas redire ce que j'ai déjà écrit ici), et sans doute aussi, à un certain niveau, par le livre de vulgarisation scientifique Cosmos de Carl Sagan : quelle que soit la part de ces différences influences, je rêvais de civilisations galactiques, mais en même temps je voyais bien qu'il était très difficile d'écrire des histoires scientifiquement sensées dans un tel cadre. Car quels que soient les mécanismes imaginés pour contourner les obstacles évidents que présentent la finitude de la vitesse de la lumière, l'immensité des échelles d'espace et de temps impliquées, la rareté des planètes habitables et l'imagination des formes de vie extra-terrestres (ou l'explication de leur absence !), pour arriver à quelque chose de ne serait-ce que plausible scientifiquement, non seulement on devra faire d'immenses efforts d'exposition, mais en outre on arrivera certainement à un univers tellement étranger à l'expérience familière de l'auteur et du lecteur qu'il sera difficile de rentrer dedans. L'autre solution était de jeter résolument la science à la poubelle et de traiter le space opera comme on traite le médiéval-fantastique, comme un décor en plastique où on peut insérer n'importe quelle manière d'histoire, mais j'étais plus hostile à suspendre mon incrédulité scientifique de cette manière qu'en imaginant des elfes, des nains et des gnomes.

↑Entry #2688 [older| permalink|newer] / ↑Entrée #2688 [précédente| permalien|suivante] ↑

↓Entry #2687 [older| permalink|newer] / ↓Entrée #2687 [précédente| permalien|suivante] ↓

(vendredi)

Comment manœuvrer une voiture dans un tunnel : un peu de géométrie

Mon poussinet s'est acheté une nouvelle voiture. Ou plus exactement, a remplacé un joujou, rouge de chez Honda, thermique et bruyant, par un autre joujou, blanc de chez Tesla, électrique et beaucoup moins bruyant et beaucoup plus Internet of Shit ; mais ce n'est pas mon propos ici d'en parler : le point de départ de ce que je veux dire ici, c'est que le nouveau joujou est assez long et large, et que la descente du parking de notre immeuble est compliquée.

Nous avons trois véhicules et trois places de parking (une achetée avec l'appartement et deux louées à des voisins). Ma moto, bizarrement, ne pose aucun problème pour monter et descendre au parking. Pour la Tuture préférée (qui fait censément 1.74m de large, et 4.15m de long dont 2.51m entre les essieux), le poussinet s'en sort bien (le plus souvent sans marche arrière), mais moi je n'ose pas trop essayer, et c'est d'ailleurs mon principal obstacle à circuler en voiture. Et pour le nouveau joujou (qui fait censément 1.85m de large, et 4.69m de long dont 2.83m entre les essieux), c'est beaucoup plus compliqué : à ce stade, à chaque fois que nous voulons entrer ou sortir du parking, je descends de la voiture, je passe devant, et j'indique au poussinet par des signes de main la distance à gauche et à droite (certes, le joujou a plein de capteurs, mais ils sont essentiellement inutiles dans ces circonstances, parce qu'ils passent juste leur temps à faire bip, et ne détectent pas forcément la « bonne » distance) : il arrive à sortir en une seule fois, mais pour rentrer dans le parking il faut trois ou quatre marches arrière (et la question de pourquoi ce n'est pas symétrique est une de celles que je veux discuter ici).

Pourtant, la descente du parking n'est pas si étroite : elle fait 2.67m de large au point le plus resserré que j'aie mesuré ; cette largeur est un peu stupidement grignotée par le fait qu'il y a des garde-corps (je ne sais pas comment les appeler : une sorte de marche ou de micro trottoirs de part et d'autre de la descente, au niveau du sol, large d'environ 15cm et haute d'environ autant), qui réduit l'espace disponible au niveau des roues à 2.38m au point le plus étroit. Mais bien sûr, la descente est courbe : entre la porte côté rue et la base de la rampe, il y a un changement de cap de 90° (on entre perpendiculairement à la rue Simonet, et on finit parallèlement à elle).

Géométriquement, si j'en crois les plans d'architecte de l'immeuble que j'ai récupérés je ne sais plus comment, la forme est très simple (cf. figure ci-contre) : prenez un quart de cercle de rayon 6.50m et un autre de rayon 5.50m dont les centres sont décalés de 1.75m selon chacun des axes du quart de cercle (donc à distance 1.75m×√2 ≈ 2.47m l'un de l'autre), le centre du petit cercle étant évidemment plus éloigné des arcs eux-mêmes que celui du grand cercle, et ensuite prolongez tangentiellement chacune des deux extrémités de chacun des deux arcs. (En notation SVG et en exprimant les distances en mètres : M 0.00 0.00 L 9.37 0.00 A 6.50 6.50 0 0 1 15.87 6.50 L 15.87 18.38 pour le bord extérieur et M 0.00 2.75 L 7.62 2.75 A 5.50 5.50 0 0 1 13.12 8.25 L 13.12 18.38 pour le bord intérieur.) Ceci fait donc une rampe dont la largeur est de (6.50m−5.50m)+1.75m = 2.75m dans ses parties rectilignes, et de (6.50m−5.50m)+1.75m×√2 ≈ 3.47m dans sa partie courbe, à quoi il faut retirer environ 15cm de garde-corps de part et d'autre comme je l'ai expliqué ci-dessus. J'ai fait apparaître sur la figure des rectangles à l'échelle du joujou du poussinet, mais il n'est pas évident de le placer comme je viens de le montrer (cf. plus loin). L'épaisseur des traits sur la figure est de 30cm (le milieu du trait est au niveau du mur lui-même, le bord intérieur correspond à peu près au bord du garde-corps).

Bon, en plus, la rampe est bien sûr en pente (de 14.38% selon le plan d'architecte, l'hélice étant orientée à main gauche : sur le schéma ci-contre, la sortie côté rue est en bas de la figure, la base de la rampe côté parking est à gauche), mais je ne pense pas que ça joue énormément sur le problème géométrique que je vais évoquer. Par ailleurs, la construction de l'immeuble n'a pas respecté précisément les plans d'architecte et les arcs de cercle ont été approchés par des polygones, donc il y a trois ou quatre points anguleux sur le mur extérieur : je ne sais pas bien si ça joue dans l'explication de l'asymétrie ressentie entre montée et descente, je vais y revenir ; la largeur de la rampe, comme je l'ai dit plus haut, n'est, d'après mes mesures, pas tout à fait égale aux 2.75m contractuels de mur à mur, je l'ai déjà noté.

Mes lecteurs savent que j'aime faire des typologies, alors allons-y. Je peux distinguer trois niveaux au problème d'entrer ou sortir la voiture :

  1. La question purement géométrique (entrer ou sortir la voiture, en supposant une connaissance parfaite de ses dimensions, sa position, la forme de la rampe, etc., donc toutes les distances impliquées), que je vais elle-même ci-dessous subdiviser en trois.
  2. La complication supplémentaire que, assis à la place du conducteur, on voit mal ce qu'on fait, on évalue mal les distances, malgré les rétroviseurs et les diverses caméras de la Tesla, en tout cas, plus mal que quelqu'un qui se tient à distance et qui regarde la voiture de l'extérieur.
  3. La complication supplémentaire qu'une voiture n'avance pas exactement comme on veut (je parle du point de vue de la traction : je mets la question du rayon de braquage sur le chapeau géométrique) : ceci ne concerne pas la Tesla, dont le moteur électrique permet d'avancer aussi lentement qu'on veut, presque millimètre par millimètre, aussi bien en montée qu'en descente, mais le problème se pose avec une voiture thermique si on ne veut pas vitrifier l'embrayage en patinant trop longtemps.

Je veux surtout parler ici du (A), même si (B) et (C) sont aussi problématiques en pratique. Maintenant, même si je le simplifie à outrance en traitant la voiture comme un simple rectangle et en ramenant tout le problème dans le plan, ce que je vais faire, le (A) se subdivise lui-même en trois niveaux de difficulté :

↑Entry #2687 [older| permalink|newer] / ↑Entrée #2687 [précédente| permalien|suivante] ↑

↓Entry #2686 [older| permalink|newer] / ↓Entrée #2686 [précédente| permalien|suivante] ↓

(mercredi)

Trucs et astuces pour tirer au hasard diverses choses

Je rassemble dans cette entrée quelques faits algorithmiques et informatiques qui sont généralement « bien connus » (et franchement assez basiques) mais souvent utiles, et qu'il est possiblement difficile de trouver rassemblés en un seul endroit. Le problème général est de tirer algorithmiquement des variables aléatoires selon différentes distributions, typiquement à partir d'un générateur aléatoire qui produit soit des bits aléatoires (indépendants et non biaisés) soit des variables aléatoires réelles (indépendantes) uniformément réparties sur [0;1]. Je parle d'algorithmique, mais ce n'est pas uniquement sur un ordinateur : ça peut être utile même dans la vie réelle, par exemple si on a une pièce avec laquelle on peut tirer à pile ou face et qu'on veut s'en servir pour jouer à un jeu qui réclame des dés à 6 faces, ou si on a des dés à 6 faces et qu'on veut jouer à un jeu d'aventure qui réclame des dés à 20 faces.

Comment tirer des nombres aléatoires en conditions adversariales ? Je commence par ce problème-ci qui n'a pas de rapport direct avec la suite, mais que je trouve quand même opportun de regrouper avec : Alice et Bob veulent jouer à pile ou face, ou plus généralement tirer un dé à n faces, mais ils n'ont pas de pièce ou de dé en lequel ils fassent tous les deux confiance. Par exemple, Alice a sa pièce fétiche que Bob soupçonne d'être truquée et symétriquement (ou peut-être même que chacun est persuadé de pouvoir tirer des nombres aléatoires dans sa tête mais ne fait évidemment pas confiance à l'autre). La solution est la suivante : chacun fait un tirage avec son propre moyen de son côté, sans connaître le résultat de l'autre, et on combine ensuite les résultats selon n'importe quelle opération (choisie à l'avance !) qui donne tous les n résultats possibles pour chaque valeur fixée d'une quelconque des entrées (un carré latin, par exemple une loi de groupe) ; par exemple, s'il s'agit de tirer à pile ou face, on peut décider (à l'avance !) que le résultat sera pile (0) si les deux pièces ont donné le même résultat et face (1) si elles ont donné un résultat différent ; s'il s'agit de dés à n faces donnant un résultat entre 0 et n−1, on fait la somme modulo n (c'est-à-dire qu'on fait la somme et qu'on soustrait n si elle vaut au moins n, pour se ramener à un résultat entre 0 et n−1). Bien sûr, il faut un protocole pratique pour faire en sorte que chacun fasse son tirage sans connaître le résultat de l'autre (sinon, s'il a moyen de tricher, il pourra adapter le résultat en conséquence) : physiquement, chacun peut faire son tirage en secret et écrire le résultat secrètement sur un papier placé dans une enveloppe scellée, qu'on ouvrira une fois les deux tirages effectués (en fait, il n'y a que le premier tirage qui a besoin d'être fait de la sorte) ; cryptographiquement, on procède à une mise en gage (typiquement au moyen d'une fonction de hachage, mais je ne veux pas entrer dans ces questions-là). On peut bien sûr généraliser à plus que deux joueurs (en faisant la somme modulo n de nombres tirés par chacun des participants). Le protocole garantit que le résultat sera un tirage uniforme honnête si l'un au moins des participants désire qu'il le soit (et a les moyens de réaliser un tirage honnête) : bien sûr, si aucun des participants ne le souhaite, c'est leur problème, donc on s'en fout. Même si on abandonne toute prétention à ce que les participants tirent leur valeur aléatoirement et qu'on s'imagine qu'ils la choisissent, tant qu'il s'agit d'un jeu à somme nulle, la stratégie optimale est bien de tirer au hasard (et encore une fois, s'ils veulent coopérer pour un autre résultat, tant qu'il n'y a pas d'autre partie impliquée, c'est leur problème, de même s'ils s'imaginent pouvoir faire mieux que le hasard en utilisant, par exemple, une prédiction psychologique).

Je ne sais plus où j'avais lu que ce protocole a été découvert (il l'a certainement été de nombreuses fois !) à la renaissance. Dans mon souvenir, le découvreur proposait même que, pour une question de la plus haute importance, on demande au pape de faire un des tirages en plus de tous les autres participants. Je ne sais d'ailleurs pas si ce protocole a un nom standard.

Comment tirer une variable de Bernoulli de paramètre p à partir de bits aléatoires ? Autrement dit, ici, on a fixé p, et on veut faire un tirage aléatoire qui renvoie oui avec probabilité p et non avec probabilité 1−p, et pour ça, on dispose simplement d'une pièce qui renvoie des bits aléatoires en tirant à pile (0) ou face (1), et on souhaite effectuer les tirages de façon économique. Par exemple, combien de tirages de pièce faut-il, en moyenne, pour générer un événement de probabilité 1/3 ? Il s'avère, en fait, que quel que soit p on peut s'en tirer avec deux (2) tirages en moyenne (je veux dire en espérance). Pour cela, on peut procéder ainsi : on effectue des tirages répétés et on interprète les bits aléatoires ainsi produits comme l'écriture binaire d'un nombre réel x uniformément réparti entre 0 et 1 : on compare x à 1−p en binaire, c'est-à-dire qu'on s'arrête dès qu'on dispose d'assez de bits pour pouvoir décider si x < 1−p ou x > 1−p (on peut considérer le cas x = 1−p comme s'il était impossible vu qu'il est de probabilité 0), en notant qu'on va avoir x < 1−p lorsque le k-ième bit tiré est 0 et que le k-ième bit de l'écriture binaire de p vaut 0, et x > 1−p lorsque le k-ième bit tiré est 1 et que le k-ième bit de p vaut 1 ; et si x < 1−p on renvoie non, sinon oui. Concrètement, donc, faire des tirages aléatoires jusqu'à ce que le k-ième bit tiré soit égal au k-ième bit de l'écriture de p, et alors s'arrêter et renvoyer ce bit-là. Il est clair que cet algorithme fonctionne, mais pour qu'il soit encore plus évident qu'il conduit à faire deux tirages en moyenne, on peut le reformuler de la façon encore plus élégante suivante (il suffit d'échanger les résultats 0 et 1 pour x, qui sont complètement symétriques, lorsque le bit correspondant de p vaut 0) : tirer des bits aléatoires jusqu'à tomber sur 1, et lorsque c'est le cas, s'arrêter et renvoyer le k-ième bit de p (où k est le nombre de bits aléatoires qui ont été tirés). Je trouve ça incroyablement élégant et astucieux (même si c'est très facile), et je ne sais pas d'où sort ce truc. (Cela revient encore à tirer une variable aléatoire k distribuée selon une loi géométrique d'espérance 1, comme je l'explique plus bas, c'est-à-dire valant k avec probabilité (½)k+1, et renvoyer le (k+1)-ième bit bk+1 de p, ce qui, quand on écrit p = ∑k=0+∞ bk+1·(½)k+1, est finalement assez évident.)

Comment tirer un entier aléatoire entre 0 et n−1 à partir de bits aléatoires ? (Ma première réaction en entendant ce problème a été de dire : considérer x uniforme dont l'écriture binaire est donnée par la suite des bits tirés, générer suffisamment de bits pour calculer la valeur de ⌊n·x⌋, où ⌊—⌋ désigne la partie entière, et renvoyer celle-ci. Ceci fonctionne, mais ce n'est pas le plus efficace. Un autre algorithme avec rejet consiste à générer r := ⌈log(n)/log(2)⌉ bits, qui, lus en binaire, donnent un entier aléatoire c entre 0 et 2r−1, renvoyer c s'il est <n, et sinon tout recommencer. Mais ce n'est pas très efficace non plus, quoique dans des cas un peu différents.) Je décris ce problème plus en détails dans ce fil Twitter, mais donnons juste l'algorithme : on utilise deux variables internes à l'algorithme, notées v et c, qu'on initialise par v←1 et c←0 (il s'agit d'un réservoir d'entropie, et la garantie est que c est aléatoire uniformément réparti entre 0 et v−1) ; puis on effectue une boucle : à chaque étape, on génère un bit aléatoire b (valant 0 ou 1 avec probabilité ½ pour chacun, et indépendant de tous les autres, donc) et on remplace v ← 2v et c ← 2c+b ; puis on compare v avec n et c avec n : si v<n (ce qui implique forcément c<n) on continue simplement la boucle (il n'y a pas assez d'entropie) ; si vn et c<n, on termine l'algorithme en renvoyant la valeur c ; enfin, si cn, on effectue v ← vn et c ← cn et on continue la boucle. Le calcul du nombre moyen de tirages effectués est fastidieux (voir cette référence citée dans le fil Twitter référencée ci-dessus), mais c'est optimal.

L'algorithme que je viens de décrire s'adapte assez bien pour tirer un entier uniforme entre 0 et n−1 à partir d'une source de entiers uniformes entre 0 et m−1 (le cas que je viens de décrire est le cas m=2), autrement dit : comment fabriquer un dé à n faces à partir d'un dé à m faces ? Je n'ai pas vraiment envie de réfléchir à si c'est optimal (mise à jour : on l'a fait pour moi), mais c'est en tout cas assez élégant : on utilise deux variables internes à l'algorithme, notées v et c, qu'on initialise par v←1 et c←0 ; puis on effectue une boucle : à chaque étape, on génère un tirage aléatoire b entre 0 et m−1 à partir de la source dont on dispose et on remplace v ← m·v et c ← m·c+b ; puis on effectue la division euclidienne de v et de c par n : si les deux quotients calculés sont différents (⌊c/n⌋ < ⌊v/n⌋), on termine l'algorithme en renvoyant le reste c%n := cn·⌊c/n⌋ de la division de c par n, tandis que si les deux quotients sont égaux, on remplace chacun par son reste, c'est-à-dire v ← v%n et c ← c%n et on continue la boucle.

Introduisons maintenant aussi des tirages continus.

↑Entry #2686 [older| permalink|newer] / ↑Entrée #2686 [précédente| permalien|suivante] ↑

Continue to older entries. / Continuer à lire les entrées plus anciennes.


Entries by month / Entrées par mois:

2021 Jan 2021 Feb 2021 Mar 2021 Apr 2021 May 2021 Jun 2021 Jul 2021 Aug 2021 Sep 2021 Oct 2021 Nov 2021
2020 Jan 2020 Feb 2020 Mar 2020 Apr 2020 May 2020 Jun 2020 Jul 2020 Aug 2020 Sep 2020 Oct 2020 Nov 2020 Dec 2020
2019 Jan 2019 Feb 2019 Mar 2019 Apr 2019 May 2019 Jun 2019 Jul 2019 Aug 2019 Sep 2019 Oct 2019 Nov 2019 Dec 2019
2018 Jan 2018 Feb 2018 Mar 2018 Apr 2018 May 2018 Jun 2018 Jul 2018 Aug 2018 Sep 2018 Oct 2018 Nov 2018 Dec 2018
2017 Jan 2017 Feb 2017 Mar 2017 Apr 2017 May 2017 Jun 2017 Jul 2017 Aug 2017 Sep 2017 Oct 2017 Nov 2017 Dec 2017
2016 Jan 2016 Feb 2016 Mar 2016 Apr 2016 May 2016 Jun 2016 Jul 2016 Aug 2016 Sep 2016 Oct 2016 Nov 2016 Dec 2016
2015 Jan 2015 Feb 2015 Mar 2015 Apr 2015 May 2015 Jun 2015 Jul 2015 Aug 2015 Sep 2015 Oct 2015 Nov 2015 Dec 2015
2014 Jan 2014 Feb 2014 Mar 2014 Apr 2014 May 2014 Jun 2014 Jul 2014 Aug 2014 Sep 2014 Oct 2014 Nov 2014 Dec 2014
2013 Jan 2013 Feb 2013 Mar 2013 Apr 2013 May 2013 Jun 2013 Jul 2013 Aug 2013 Sep 2013 Oct 2013 Nov 2013 Dec 2013
2012 Jan 2012 Feb 2012 Mar 2012 Apr 2012 May 2012 Jun 2012 Jul 2012 Aug 2012 Sep 2012 Oct 2012 Nov 2012 Dec 2012
2011 Jan 2011 Feb 2011 Mar 2011 Apr 2011 May 2011 Jun 2011 Jul 2011 Aug 2011 Sep 2011 Oct 2011 Nov 2011 Dec 2011
2010 Jan 2010 Feb 2010 Mar 2010 Apr 2010 May 2010 Jun 2010 Jul 2010 Aug 2010 Sep 2010 Oct 2010 Nov 2010 Dec 2010
2009 Jan 2009 Feb 2009 Mar 2009 Apr 2009 May 2009 Jun 2009 Jul 2009 Aug 2009 Sep 2009 Oct 2009 Nov 2009 Dec 2009
2008 Jan 2008 Feb 2008 Mar 2008 Apr 2008 May 2008 Jun 2008 Jul 2008 Aug 2008 Sep 2008 Oct 2008 Nov 2008 Dec 2008
2007 Jan 2007 Feb 2007 Mar 2007 Apr 2007 May 2007 Jun 2007 Jul 2007 Aug 2007 Sep 2007 Oct 2007 Nov 2007 Dec 2007
2006 Jan 2006 Feb 2006 Mar 2006 Apr 2006 May 2006 Jun 2006 Jul 2006 Aug 2006 Sep 2006 Oct 2006 Nov 2006 Dec 2006
2005 Jan 2005 Feb 2005 Mar 2005 Apr 2005 May 2005 Jun 2005 Jul 2005 Aug 2005 Sep 2005 Oct 2005 Nov 2005 Dec 2005
2004 Jan 2004 Feb 2004 Mar 2004 Apr 2004 May 2004 Jun 2004 Jul 2004 Aug 2004 Sep 2004 Oct 2004 Nov 2004 Dec 2004
2003 May 2003 Jun 2003 Jul 2003 Aug 2003 Sep 2003 Oct 2003 Nov 2003 Dec 2003

[Index of all entries / Index de toutes les entréesLatest entries / Dernières entréesXML (RSS 1.0) • Recent comments / Commentaires récents]