<foo> simply produces <foo>in the text).
<URL: http://somewhere.tld/ >,
and it will be automatically made into a link.
(Do not try any other way or it might count as an attempt to spam.)mailto: URI,
e.g. mailto:my.email@somewhere.tld,
if you do not have a genuine Web site).
Ahmad (2021-07-23T12:26:01Z)
Bonjour David,
A quand un article qui traite de la théorie des catégories?
JML (2021-06-13T15:51:16Z)
« faire un tirage aléatoire qui renvoie "oui" avec probabilité p et "non" avec probabilité 1−p […] si x < 1−p on renvoie "oui", sinon "non". »
Je crois que tu t'es embrouillé dans la description de cet algorithme :) dont la version finale est effectivement époustouflante, merci pour ce moment ah-ha.
PS "empty nickname" perd le message, j'aurais été agacé si j'avais dû retaper un long commentaire… Suggestion : donner le message après le message d'erreur en suggérant de copier-coller.
Guillaume Aubrun (2021-06-10T11:09:55Z)
Jolie liste!
On peut y rajouter le problème suivant, un peu dans l'esprit des deux premiers: comment débiaiser un bit ?
Avec uniquement une vieille pièce de monnaie qui n'a pas l'air du tout équilibrée, comment puis-je produire un résultat valant 0 ou 1 avec probabilité 1/2 ?
Posée ainsi, l'énigme a une solution simple. Le problème de produire des bits uniformes à un taux optimal est plus complexes et a été résolu magistralement dans cet article : <URL:https://projecteuclid.org/journals/annals-of-statistics/volume-20/issue-1/Iterating-Von-Neumanns-Procedure-for-Extracting-Random-Bits/10.1214/aos/1176348543.full>
Nick (2021-06-05T15:25:00Z)
Voici pour tirer uniformément dans la boule unité de norme N de dimension d (classées suivant leur norme):
norme 2: Déjà décrite dans ton post: Tirer sur la sphère et tirer le rayon par: tirer uniformément u entre 0 et 1 et prendre r=u^(1/d)
norme 1: récursivement
Tirer_l1(R,d)
Si d=1 renvoyer renvoyer une variable uniforme entre -R et R.
sinon
Tirer x0= R*(1-u^(1/d)) où u est uniforme entre 0 et 1.
renvoyer (x0, Tirer_l1(R-|x0|,d-1) (concaténation)
norme infini: tirer toutes les composantes uniformément entre -1 et 1…
norme p: Pour généraliser ce qui est fait pour la norme 1 il faudrait tirer x0 suivant la loi:
K (R^p-x0^p)^(1/p*(d-1)) (K normalisation): ceci est le volume de la tranche autour de x0 de la boule de norme p.
ce qui doit être faisable de manière approchée…
Benoit (2021-06-04T19:30:45Z)
Pour le tirage sur une sphère de dimension d, tu mentionnes le cas particulier d=1 où il existe la "forme fermée" (cos x, sin x).
Est-ce une question intéressante de demander dans quelles autres dimensions il existe une telle forme fermée (peut-on donner un sens précis à cette question, ou bien à défaut se contenter de trouver quelques exemples) ?
Je me lance:
Pour d=3 on peut écrire S^3 comme la sphère unité dans C^2, les (z, w) avec |z|^2 + |w|^2 = 1, il suffit alors de tirer un |z| aléatoire avec la bonne distribution, ce qui détermine |w| et on est ramené à tirer deux points sur S^1 (w/|w| et z/|z|).
Pour d=2 on pourrait peut-être utiliser la projection de Hopf S^3->S^2 qui envoie (z, w) sur (z : w) dans P1(C)=S^2, mais il y a une difficulté à ne pas perdre de vue la métrique de S^2 quand on passe au point de vue P1(C)…
Ceci devrait se généraliser au moins à S^7 et sa projection sur S^4…
Arnaud Spiwack (2021-06-04T06:57:06Z)
Pour rajouter à cette impressionnante liste, tu aimeras peut-être cette méthode (pas super pragmatique parce que pas stable numériquement, si je me souviens bien) pour tirer un événement dans un univers fini arbitraire https://www.keithschwarz.com/darts-dice-coins/ .
mouton (2021-06-03T20:31:48Z)
Je reviens ici plutôt que sur twitter pour ajouter que ton truc pour transformer un élément du simplexe discret de dimension d et de taille n en élément de (d parmi n+d) s'appelle la méthode "stars and bars" https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
jonas (2021-06-03T13:51:20Z)
Is “vistochastique” a deliberate term or just a typo for “bistochastique”?
> on va plutôt tirer d entiers distincts entre 1 et N+d (il y a toutes sortes de manières de faire ça, ce n'est pas compliqué et je ne rentre pas dans les détails, le plus évident est simplement de tirer chaque nombre en recommençant tant qu'on tombe sur un nombre déjà tiré),
That's a pity, because that is one of the more interesting questions here. There are at least three significantly different algorithms known for that task for large N.
> pour tirer uniformément une matrice orthogonale de taille m×m, le plus simple est de tirer m² variables gaussiennes indépendantes centrées de même espérance, qu'on considérera comme m vecteurs de taille m, et de leur appliquer l'algorithme de Gram-Schmidt pour les transformer en une base orthonormée
Yes, but there's a subtlety that you have to pay attention to. The QR decomposition performed here has a freedom of choice in the plus or minus sign of each column of Q and corresponding row of R. Most library functions that perform QR decomposition actually use that freedom, so the matrix Q that you get will not be uniform. Luckily you can restore that after the fact by normalizing the signs such that the diagonal elements of R are all positive (or have a positive real part).
Ruxor (2021-06-03T13:22:33Z)
@Laurent: Essayons de dire plus clairement ce que j'ai dit de façon confuse dans le commentaire précédent.
Procédure « répartir un ensemble de n personnes en un ensemble A de k personnes et un ensemble B de n−k personnes » :=
‣ tout le monde tire une pièce donnant un résultat 0 ou 1 (de façon indépendante et équiprobable),
‣ s'il y a k personnes ayant tiré 0 et n−k personnes ayant tiré 1, ce sont les ensembles A et B respectivement,
‣ s'il y a ℓ>k personnes ayant tiré 0, alors les n−ℓ < n−k personnes ayant tiré 1 sont mises dans un ensemble B₁, on applique récursivement la même procédure pour répartir les ℓ personnes ayant tiré 0 en un ensemble A de cardinal k et un ensemble B₀ de cardinal ℓ−k, et on pose B := B₀ ∪ B₁ (de cardinal n−k),
‣ s'il y a ℓ<k personnes ayant tiré 0, c'est le contraire : on met ces ℓ personnes dans un ensemble A₀, on applique récursivement la même procédure pour répartir les n−ℓ > n−k personnes ayant tiré 1 en un ensemble A₁ de cardinal k−ℓ et un ensemble B de cardinal n−k, et on pose A := A₀ ∪ A₁ (de cardinal k).
C'est facile à faire (en pratique on va avoir un tas de gens « encore à trier », un tas de gens déjà dans l'équipe A et un tas déjà dans l'équipe B, on fait tirer le tas de gens encore à trier et on en envoie dans l'équipe A ou B selon les cas que je viens de dire, les autres étant encore à trier et de moins en moins nombreux), et c'est clairement efficace (peut-être même bien optimal).
Ruxor (2021-06-03T13:10:56Z)
@Typhon: Je me rappelle avoir joué avec un enfant à une forme itérée de ce jeu (je crois qu'il choisissait une carte dans un paquet de 52 et je devais dire rouge ou noir), et en pratique j'arrivais à prédire ses choix avec un taux de succès tournant autour de 80%, c'est assez impressionnant à quel point les enfants sont prévisibles.
@Laurent: Je proposerais quelque chose comme ça : chaque élève tire une première fois à pile ou face, disons pile=0 et face=1, on fait deux groupes, évidemment ils ont toutes les chances d'être inégaux ; disons que le groupe le plus gros soit celui de 0 : tous les élèves de ce groupe retirent, maintenant on a trois groupes, 00, 01 et 1, qu'on range dans cet ordre : on regarde dans quel paquet tombe la moitié, et on fait retirer aux élèves de ce groupe (par exemple ça va subdiviser 01 en 010 et 011, qu'on range de nouveau dans l'ordre), et on répète jusqu'à avoir 15+15. Autrement dit, chaque élève va tirer une suite de 0 et 1 de façon paresseuse jusqu'à ce qu'on ait juste assez d'information dans le tri pour décider où est la coupure médiane. (Je ne sais pas si c'est super clair, il y a sans doute moyen de le dire mieux.)
Laurent (2021-06-02T22:10:14Z)
Excellent.
Je m'étais souvent posé la situation suivante : un prof de gym a 30 élèves et doit les répartir aléatoirement en deux équipes de 15 avec seulement une pièce.
En théorie, la partie "Comment tirer un entier aléatoire entre 0 et n−1 à partir de bits aléatoires ?" répond à la question…
Mais ça semble difficile à faire en pratique en temps limité et mentalement.
En ce qui concerne la partie "en conditions adversariales", une implémentation pratique à faire avec des enfants est de demander à chacun de choisir "pair ou impair". Ensuite, ils mettent les mains derrière le dos et présentent en même temps une main donnant avec les doigts un nombre entre 0 et 5.
On fait la somme. Si c'est pair, l'enfant qui a choisi pair gagne.
C'est plus efficace que pierre-papier-ciseaux parce que ça demande plus de "calculs" pour tricher. Présenter la main une seconde après l'adversaire suffit pour tricher à pierre-papier-ciseaux, mais pas à "pair-impair".
Typhon (2021-06-02T21:47:29Z)
« 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 »
Je pense qu'une grande faille du premier protocole donné est que le cerveau humain est un très mauvais générateur de hasard en toute généralité et notamment que certains nombres paraissent psychologiquement "plus aléatoires" que d'autres, ce qui les rend notablement plus probables.
(plein de gens l'ont constaté empiriquement sur Twitter en faisant des sondages à 4 options identiques qui garantissent virtuellement la victoire de l'option n°3, mais je pense qu'il y a aussi des études plus sérieuses). Et c'est encore pire avec des tirages répétés.
C'est sans doute du pseudo-aléatoire passable pour trancher un choix de fast-food entre burgers, pizzas et sushis, mais je pense qu'on n'en voudrait pas même dans un jeu de société (qui me paraît le seul cas pratique où on pourrait en vouloir sinon).