Fléchettes, dés et pièces: algorithmes de distribution discrets

J'ai posé une fois à Stack Overflow une question sur la structure des données pour tricher aux dés . En particulier, je suis intéressé par la réponse à cette question: «Si nous avons un os à n facettes, dont la face i a une probabilité de tomber p _i . Quelle est la structure de données la plus efficace pour simuler les rouleaux d'un tel os? »

Cette structure de données peut être utilisée pour de nombreuses tâches. Par exemple, vous pouvez l'utiliser pour simuler des jets hexagonaux honnêtes, en attribuant une probabilité $$$\ frac {1} {6}$ de chaque côté de l'os, ou pour simuler une pièce de monnaie équitable par imitation d'un os bilatéral, dont la probabilité de tomber de chaque côté est égale à $$$\ frac {1} {2}$ . Vous pouvez également utiliser cette structure de données pour simuler directement la somme de deux os hexagonaux honnêtes en créant un os à 11 faces (avec les faces 2, 3, 4, ..., 12), dont chaque face a un poids de probabilité correspondant aux rouleaux de deux os honnêtes. Cependant, vous pouvez également utiliser cette structure de données pour simuler des tricheurs. Par exemple, si vous jouez au craps avec un os, ce qui, comme vous le savez, n'est pas parfaitement honnête, vous pouvez utiliser cette structure de données pour simuler un grand nombre de rouleaux d'os et analyser la stratégie optimale. Vous pouvez également essayer de simuler une roue de roulette tout aussi imparfaite.

Si vous allez au-delà des jeux, vous pouvez appliquer cette structure de données dans la simulation de robots dont les capteurs ont des niveaux de défaillance connus. Par exemple, si un capteur de plage a une probabilité de 95% de renvoyer la valeur correcte, une probabilité de 4% d'une valeur trop petite et une probabilité de 1% d'une valeur trop élevée, vous pouvez utiliser cette structure de données pour simuler la lecture des lectures du capteur en générant un résultat aléatoire et simuler la lecture du capteur résultat.

La réponse que j'ai reçue sur Stack Overflow m'a impressionné pour deux raisons. Tout d'abord, dans la solution, il m'a été conseillé d'utiliser une technique puissante appelée la méthode alias , qui, avec certaines hypothèses raisonnables sur le modèle de la machine, est capable, après une simple étape de préparation préliminaire, de simuler des roulements osseux dans le temps $$$O (1)$ . Deuxièmement, j'ai été encore plus surpris que cet algorithme soit connu depuis des décennies, mais je ne l'ai jamais rencontré! Étant donné le temps de calcul consacré à la simulation, on pourrait s'attendre à ce que cette technique soit beaucoup plus connue. Quelques requêtes sur Google m'ont donné beaucoup d'informations sur cette technique, mais je n'ai pas pu trouver un seul site où une compréhension et une explication intuitives de cette technique se sont réunies.

Cet article est ma tentative de donner un bref aperçu des différentes approches pour simuler la triche osseuse, des techniques simples et très peu pratiques à une méthode d'alias très optimisée et efficace. J'espère que je serai en mesure de transmettre différentes façons de comprendre intuitivement la tâche et comment chacun d'entre eux met l'accent sur un nouvel aspect de la simulation d'un tricheur. Mon objectif pour chaque approche est d'étudier une idée motivante, un algorithme de base, une preuve de fidélité et une analyse de l'exécution (en termes de temps requis, de mémoire et d'aléatoire).

Entrée

Avant de passer aux détails spécifiques des différentes techniques, normalisons d'abord la terminologie et la notation.

Dans l'introduction de l'article, j'ai utilisé le terme «os tricheur» pour décrire un scénario généralisé dans lequel il existe un ensemble fini de résultats, chacun ayant une probabilité. Formellement, cela s'appelle une distribution de probabilité discrète , et la tâche de simuler un os tricheur est appelée échantillonnage à partir d'une distribution discrète .

Pour décrire notre distribution de probabilité discrète (os tricheur), nous supposerons que nous avons un ensemble de n probabilités $$$p_0, p_1, ..., p_ {n - 1}$ lié aux résultats $$ . Bien que les résultats puissent être quelconques (aigle / queues, nombres sur les os, couleurs, etc.), pour simplifier, je considérerai le résultat comme une sorte de nombre réel positif correspondant à un indice donné.

Travailler avec des nombres réels sur un ordinateur est la «zone grise» de l'informatique. Il existe de nombreux algorithmes rapides, dont la vitesse est fournie uniquement par la capacité de calculer la fonction de plancher d'un nombre réel arbitraire en un temps constant, et des inexactitudes numériques dans la représentation des nombres à virgule flottante peuvent détruire complètement certains algorithmes. Par conséquent, avant de commencer toute discussion sur les algorithmes qui fonctionnent avec des probabilités, c'est-à-dire entrer dans le monde sombre des nombres réels, je dois clarifier ce qu'un ordinateur peut et ne peut pas faire.

Ci-après, je suppose que toutes les opérations suivantes peuvent être effectuées en temps constant:

• Addition. soustraction, multiplication, division et comparaison de nombres réels arbitraires . Nous devrons le faire pour manipuler les probabilités. Cela peut sembler une hypothèse audacieuse, mais si nous supposons que la précision d'un nombre réel est limitée par un polynôme de la taille du mot machine (par exemple, un double 64 bits sur une machine 32 bits), mais je ne pense pas que ce soit trop déraisonnable.
• Génération d'un nombre réel uniforme dans l'intervalle [0, 1). Pour simuler le caractère aléatoire, nous avons besoin d'une source de valeurs aléatoires. Je suppose que nous pouvons générer un nombre réel de précision arbitraire en temps constant. Cela dépasse de loin les capacités d'un véritable ordinateur, mais il me semble que pour les besoins de cette discussion, cela est acceptable. Si nous acceptons de sacrifier une fraction de la précision en disant qu'un double arbitraire IEEE-754 est dans l'intervalle [0, 1], alors nous perdrons en fait la précision, mais le résultat sera probablement suffisamment précis pour la plupart des applications.
• Calcul du plancher entier (arrondi vers le bas) d'un nombre réel. Ceci est acceptable si nous supposons que nous travaillons avec le double IEEE-754, mais en général, une telle exigence pour un ordinateur n'est pas faisable.

Il vaut la peine de se poser la question - est-il raisonnable de supposer que nous pouvons mener à bien toutes ces opérations? Dans la pratique, nous utilisons rarement les probabilités indiquées à un tel niveau de précision auquel l'erreur d'arrondi inhérente au double IEEE-754 peut causer de graves problèmes, nous pouvons donc remplir toutes les exigences ci-dessus simplement en travaillant exclusivement avec le double IEEE. Cependant, si nous nous trouvons dans un environnement où les probabilités sont indiquées exactement comme des nombres rationnels de haute précision, alors de telles restrictions peuvent être déraisonnables.

Simulation osseuse honnête

Avant de passer au cas plus général de lancer un os de triche arbitraire, commençons par un algorithme plus simple qui servira de bloc de construction pour les algorithmes suivants: simuler un os honnête à face n. Par exemple, des dés hexagonaux honnêtes peuvent être utilisés pour jouer au Monopoly ou Risk, ou lancer une pièce honnête (dés à double face), etc.

Pour ce cas particulier, il existe un algorithme simple, élégant et efficace pour simuler le résultat. L'algorithme est basé sur l'idée suivante: supposons que nous pouvons générer des nombres réels vraiment aléatoires et uniformément répartis dans l'intervalle $$$[0, 1)$ . Cet intervalle peut être illustré comme suit:


Maintenant, si nous voulons quitter $$$n$ os à facettes, alors une façon est de diviser l'intervalle $$$[0, 1)$ sur $$$n$ zones de taille égale, chacune ayant une longueur $$$\ frac {1} {n}$ . Cela ressemble à ceci:


Ensuite, nous générons un nombre réel choisi au hasard dans l'intervalle $$$[0, 1)$ cela tombe sûrement dans l'un de ces petits domaines. À partir de cela, nous pouvons calculer le résultat du roulement de l'os en regardant la zone dans laquelle le nombre est tombé. Par exemple, si notre valeur sélectionnée au hasard tombe à cet endroit:


on peut alors dire que 2 sont tombés sur l'os (si l'on suppose que les bords de l'os sont indexés à partir de zéro).

Il est graphiquement facile de voir quelle région a une valeur aléatoire, mais comment codons-nous cela dans un algorithme? Et ici, nous profitons du fait que c'est un os honnête. Étant donné que tous les intervalles sont de taille égale, à savoir $$$\ frac {1} {n}$ , alors nous pouvons voir quelle est la plus grande valeur $$$i$ est telle que $$$\ frac {i} {n}$ pas plus qu'une valeur générée aléatoirement (appelons cette valeur x). Vous remarquerez peut-être que si nous voulons trouver la valeur maximale, telle que $$$\ frac {i} {n} \ le x$ , cela revient à trouver la valeur maximale $$$n$ tel que $$$i \ le xn$ . Mais cela signifie par définition que $$$i = \ lfloor xn \ rfloor$ , le plus grand entier positif n'est pas supérieur à xn. Par conséquent, cela nous conduit à cet algorithme de simulation osseuse à facettes n honnête (très simple):

Algorithme: simulation osseuse honnête

1. Générer une valeur aléatoire uniformément distribuée $$$x$ dans la gamme $$$[0, 1)$ .
2. Retour $$$\ lfloor xn \ rfloor$ .

Compte tenu de nos hypothèses ci-dessus sur les calculs, cet algorithme fonctionne dans le temps $$$O (1)$ .

Deux conclusions peuvent être tirées de cette section. Tout d'abord, nous pouvons diviser l'intervalle $$$[0, 1)$ en partie de sorte qu'un nombre réel aléatoire uniformément réparti dans cet intervalle se réduit naturellement à l'une des nombreuses options discrètes à notre disposition. Dans la suite de cet article, nous exploiterons activement cette technique. Deuxièmement, il peut être difficile de déterminer à quel intervalle spécifique appartient une valeur aléatoire, mais si nous savons quelque chose sur les parties (dans ce cas, elles sont toutes de la même taille), alors nous pouvons mathématiquement simplement déterminer quelle partie se réfère à un particulier point.

Simulation d'os de triche avec os honnête

Avec un algorithme de simulation osseuse honnête, pouvons-nous l'adapter pour simuler un os tricheur? Fait intéressant, la réponse est oui, mais une solution nécessitera plus d'espace.

De la section précédente, il est intuitivement clair que pour simuler un lancer d'os de triche, il suffit de diviser l'intervalle $$$[0, 1)$ en morceaux, puis déterminez quelle partie nous frappons. Cependant, dans le cas général, cela peut être beaucoup plus compliqué qu'il n'y paraît. Disons que nous avons un tétraèdre avec des probabilités de face $$$\ frac {1} {2}$ , $$$\ frac {1} {3}$ , $$$\ frac {1} {12}$ et $$$\ frac {1} {12}$ (nous pouvons nous assurer que c'est la distribution de probabilité correcte, car $$$\ frac {1} {2} + \ frac {1} {3} + \ frac {1} {12} + \ frac {1} {12} = \ frac {6} {12} + \ frac {4 } {12} + \ frac {1} {12} + \ frac {1} {12} = \ frac {12} {12}$ ) Si nous divisons l'intervalle $$$[0, 1)$ en quatre parties de ces tailles, nous obtenons alors les éléments suivants:


Malheureusement, à ce stade, nous sommes bloqués. Même si nous connaissions un nombre aléatoire dans l'intervalle $$$[0, 1)$ , il n'y a pas d'astuces mathématiques simples pour déterminer automatiquement dans quelle partie ce nombre est tombé. Je ne veux pas dire que cela est impossible - comme vous le verrez, nous pouvons utiliser de nombreux excellents trucs - mais aucun d'eux n'a la simplicité mathématique de l'algorithme honnête de projection d'os.

Cependant, nous pouvons également adapter la technique utilisée pour un os honnête. Prenons l'exemple de l'os discuté ci-dessus. La probabilité de fronts descendants est $$$\ frac {1} {2}$ , $$$\ frac {1} {3}$ , $$$\ frac {1} {12}$ et $$$\ frac {1} {12}$ . Si nous réécrivons ceci pour que tous les membres aient un diviseur commun, nous obtenons les valeurs $$$\ frac {6} {12}$ , $$$\ frac {4} {12}$ , $$$\ frac {1} {12}$ et $$$\ frac {1} {12}$ . Par conséquent, nous pouvons percevoir cette tâche comme suit: au lieu de jeter un os tétraédrique avec des probabilités pondérées, pourquoi ne pas jeter un os honnête à 12 côtés, sur les bords duquel il y a des valeurs en double? Puisque nous savons simuler un os honnête, cela sera analogue à la séparation par intervalles $$$[0, 1)$ en morceaux de cette façon:


Ensuite, nous les affectons à différents résultats comme suit:


Maintenant, il sera très simple de simuler un lancer d'os - nous jetons simplement ce nouvel os honnête, puis nous regardons quel visage est tombé et lisons sa valeur. Cette première étape peut être effectuée par l'algorithme présenté ci-dessus, qui nous donnera un nombre entier de nombres dans l'intervalle $$ . Afin de lier cet entier à l'une des faces de l'os du tricheur d'origine, nous allons stocker un tableau auxiliaire de douze éléments reliant chacun de ces nombres au résultat d'origine. Cela peut être représenté graphiquement comme suit:


Pour formaliser cela sous la forme d'un algorithme, nous décrivons à la fois l'étape d'initialisation (obtention de la table) et l'étape de génération (simulation d'un lancer osseux aléatoire). Ces deux étapes sont importantes à considérer dans cet algorithme et les suivants, car le temps de préparation doit être excellent.

Au stade de l'initialisation, nous commençons par chercher le multiple le moins commun de toutes les probabilités données pour les bords de l'os (dans notre exemple, la LCL est 12). NOC est utile ici car il correspond au plus petit diviseur commun que nous pouvons utiliser pour toutes les fractions, et donc le nombre de faces du nouvel os honnête que nous roulerons. Après avoir reçu ce CNO (nous le désignons par L), nous devons déterminer combien de faces du nouvel os seront réparties sur chacune des faces de l'os tricheur d'origine. Dans notre exemple, le visage avec probabilité $$$\ frac {1} {2}$ obtient six côtés du nouvel os depuis $$$\ frac {1} {2} \ fois 12 = 6$ . De même, la partie avec probabilité $$$\ frac {1} {3}$ obtient 4 visages depuis $$$\ frac {1} {3} \ fois 12 = 4$ . Dans une forme plus généralisée, si L est une LCL de probabilités, et $$$p_i$ est la probabilité d'un visage $$$i$ les os, puis nous mettons en évidence les visages $$$i$ os de Sharpie d'origine $$$L \ cdot p_i$ facettes de l'os honnête.

Voici le pseudocode de l'algorithme ci-dessus:

Algorithme: simuler l'os de triche avec de l'os honnête

• Initialisation :
  
  1. Trouver le CNO des dénominateurs de probabilité $$$p_0, p_1, ..., p_ {n-1}$ ; le dénoter $$$L$
  2. Sélectionnez un tableau $$$A$ la taille $$$L$ pour comparer les résultats de rouleaux d'os honnêtes avec les rouleaux de l'os d'origine.
  3. Pour chaque visage $$$i$ de l'os initial, nous effectuons les opérations suivantes dans n'importe quel ordre:
     
     1. Nous attribuons comme suit $$$L \ cdot p_i$ des éléments $$$A$ valeur $$$i$ .
• Génération :
  
  1. Nous générons un lancer d'os honnête pour $$$L$ -os osseux; appeler le visage $$$S$ .
  2. Retour $$$A [S]$ .

Cet algorithme peut être simple, mais quelle est son efficacité? La génération de rouleaux osseux est assez rapide - chaque rouleau osseux nécessite $$$O (1)$ runtime pour générer un jet de dés aléatoire en utilisant l'algorithme précédent, et plus encore $$$O (1)$ heures de travail pour rechercher la table. Cela nous donne le temps de travail total. $$$O (1)$ .

Cependant, l'étape d'initialisation peut être extrêmement coûteuse. Pour que cet algorithme fonctionne, nous devons allouer de l'espace à un tableau de la taille du NLC des dénominateurs de toutes les fractions d'entrée. Dans notre exemple ( $$$\ frac {1} {2}$ , $$$\ frac {1} {3}$ , $$$\ frac {1} {12}$ , $$$\ frac {1} {12}$ ), il est de 12, pour d'autres valeurs d'entrée, les valeurs peuvent être pathologiquement mauvaises. Par exemple, regardons les fractions $$$\ frac {999999} {1 000 000}$ et $$$\ frac {1} {1000000}$ . Le CNO des dénominateurs est égal à un million, donc il devrait y avoir un million d'éléments dans notre tableau!

Malheureusement, les choses pourraient être encore pires. Dans l'exemple précédent, on peut au moins «s'attendre» à ce que l'algorithme occupe beaucoup de mémoire, car les deux dénominateurs des fractions sont égaux à un million. Cependant, nous pouvons avoir de nombreuses probabilités pour lesquelles la CNP est nettement supérieure à chaque dénominateur individuel. Par exemple, regardons les probabilités $$$\ frac {1} {15}$ , $$$\ frac {1} {10}$ , $$$\ frac {5} {6}$ . Ici, le NOC des dénominateurs est de 30, ce qui est plus que n'importe lequel des dénominateurs. Le design fonctionne ici parce que $$ , $$ et $$ ; en d'autres termes, chaque dénominateur est un produit de deux nombres premiers sélectionnés dans un pool de trois valeurs. Par conséquent, leur NOC est le produit de tous ces nombres premiers, car chaque dénominateur doit être un diviseur du NOC. Si nous généralisons cette construction et considérons tout ensemble de $$$k$ nombres premiers et prendre une fraction pour chacun des produits par paires de ces nombres premiers, alors le NOC sera beaucoup plus que chaque dénominateur individuel. En fait, l'une des meilleures limites supérieures que nous pouvons obtenir pour le CNO sera $$$O (\ prod_ {i = 0} ^ n {d_i})$ où $$$d_i$ Est le dénominateur $$$i$ cette probabilité. Cela ne permet pas d'utiliser un tel algorithme en conditions réelles, lorsque les probabilités sont inconnues à l'avance, car la mémoire nécessaire pour stocker la table de taille $$$O (\ prod_ {i = 0} ^ n {d_i})$ , Il peut facilement s'avérer supérieur au volume pouvant tenir dans la RAM.

En d'autres termes, dans de nombreux cas, cet algorithme se comporte bien. Si toutes les probabilités sont les mêmes, alors toutes les probabilités obtenues à l'entrée sont égales $$$\ frac {1} {n}$ pour certains $$$n$ . Ensuite, les dénominateurs des CNO sont égaux $$$n$ , c'est-à-dire qu'en conséquence, l'os honnête jeté aura $$$n$ faces, et chaque facette de l'os d'origine correspondra à une facette de l'os honnête. Par conséquent, le temps d'initialisation est $$$O (n)$ . Cela peut être représenté graphiquement comme suit:


Cela nous donne les informations suivantes sur l'algorithme:

Algorithme	Temps d'initialisation		Temps de génération		Mémoire occupée
	Le meilleur	Le pire	Le meilleur	Le pire	Le meilleur	Le pire
Honnêteté os sharler bone	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Thêta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$

Autre détail important sur cet algorithme: il suppose que nous recevrons des probabilités pratiques sous forme de fractions avec de bons dénominateurs. Si les probabilités sont spécifiées comme IEEE-754 double, cette approche risque d'être désastreuse en raison de petites erreurs d'arrondi; Imaginez que nous ayons les probabilités 0,25 et 0,250000000001! Par conséquent, cette approche est probablement préférable de ne pas utiliser, sauf dans des cas particuliers où les probabilités se comportent bien et sont spécifiées dans un format correspondant aux opérations avec des nombres rationnels.

Simulation de pièces asymétriques

Notre explication d'une simple primitive aléatoire (os honnête) a conduit à un algorithme de simulation d'os de triche simple mais potentiellement terriblement inefficace. L'étude d'autres primitives aléatoires simples éclairera peut-être d'autres approches pour résoudre ce problème.

Une tâche simple mais étonnamment utile consiste à simuler une pièce asymétrique à l'aide d'un générateur de nombres aléatoires. Si nous avons une pièce avec la probabilité d'un aigle $$$p_ {têtes}$ , alors comment simuler le lancer d'une telle pièce asymétrique?

Plus tôt, nous avons développé une approche intuitive: le partitionnement par intervalles $$$[0, 1)$ sur une séquence de telles régions que lors du choix d'une valeur aléatoire dans l'intervalle, elle apparaît dans certaines régions avec une probabilité égale à la taille de la région. Pour simuler une pièce asymétrique en utilisant une valeur aléatoire uniformément distribuée dans l'intervalle $$$[0, 1)$ il faut rompre l'intervalle $$$[0, 1)$ comme suit:


Et puis générer une valeur aléatoire uniformément distribuée dans l'intervalle $$$[0, 1)$ pour voir dans quelle zone il se trouve. Heureusement, nous n'avons qu'un seul point de partage, il est donc très facile de déterminer dans quelle zone il se trouve; si la valeur est inférieure $$$p_ {têtes}$ , puis l'aigle est tombé sur la pièce, sinon - queues. Pseudocode:

Algorithme: simuler une pièce asymétrique

1. Générer une valeur aléatoire uniformément distribuée dans l'intervalle $$$[0, 1)$ .
2. Si $$$x <p_ {têtes}$ , retournez "l'aigle".
3. Si $$$x \ ge p_ {têtes}$ , renvoyez la queue.

Puisque nous pouvons générer une valeur aléatoire uniformément distribuée dans l'intervalle $$$[0, 1)$ à temps $$$O (1)$ , et nous pouvons également comparer des nombres réels pour $$$O (1)$ , alors cet algorithme s'exécute dans le temps $$$O (1)$ .

Simuler des os honnêtes à l'aide de pièces asymétriques

De la discussion précédente, nous savons que nous pouvons simuler un os de triche en utilisant de l'os honnête, si nous supposons que nous sommes prêts à dépenser plus d'espace mémoire. Étant donné que nous pouvons percevoir une pièce asymétrique comme un os bilatéral tricheur, cela signifie que nous pouvons simuler une pièce asymétrique à l'aide d'un os honnête. Il est intéressant de voir que l'inverse peut également être fait - pour simuler un os honnête à l'aide d'une pièce asymétrique.Le design est simple, élégant et peut être facilement généralisé pour simuler un os tricheur en utilisant une variété de pièces asymétriques.

Conception pour simuler une pièce asymétrique divise l'intervalle$$$[0, 1)$ en deux zones - la zone «aigles» et la zone «queues» en fonction de la probabilité que les aigles tombent sur les os. Nous avons déjà vu une astuce similaire utilisée pour simuler honnête$$$n$ os à facettes: intervalle$$$[0, 1)$ était divisé en$$$n$ zones égales. Par exemple, lors du lancement d'un os tétraédrique, nous avons obtenu la séparation suivante:


Supposons maintenant que nous soyons intéressés à simuler un rouleau de cet os honnête en utilisant un ensemble de pièces asymétriques. Une solution est la suivante: imaginez que nous contournons ces zones de gauche à droite, en nous demandant à chaque fois si nous voulons nous arrêter dans la zone actuelle, ou si nous allons continuer. Par exemple, disons que nous voulons sélectionner au hasard l'une de ces zones. En partant de la zone la plus à gauche, nous lancerons une pièce asymétrique, qui nous dira si nous devons nous arrêter dans cette zone ou continuer à avancer. Puisque nous devons choisir parmi toutes ces zones uniformément avec probabilité$$$\frac{1}{4}$ , alors nous pouvons le faire en lançant une pièce asymétrique, les aigles sur lesquels tomber avec probabilité$$$\frac{1}{4}$ .Si un aigle tombe, nous nous arrêtons dans la zone actuelle. Sinon, nous passons à la zone suivante.

Si les pièces tombent, nous nous retrouvons dans la deuxième zone et nous demandons à nouveau si nous devons sélectionner à nouveau cette zone ou continuer à bouger. Vous pourriez penser que pour cela, nous devons lancer une autre pièce avec la probabilité d'un aigle$$$\frac{1}{4}$ , mais en réalité ce n'est pas vrai! Pour voir la faille de ce raisonnement, nous devons arriver à une situation extrême - si dans chaque zone nous lançons une pièce sur laquelle l'aigle tombe avec probabilité$$$\frac{1}{4}$ , c'est-à-dire qu'il y a une petite chance que dans chaque zone la pièce tombe en queue, c'est-à-dire que nous devrons abandonner toutes les zones. Lorsque nous traversons des régions, nous devons en quelque sorte continuer d'augmenter la probabilité qu'un aigle tombe sur une pièce. Dans une situation extrême, si nous nous trouvons dans la dernière zone, la pièce doit avoir un aigle avec probabilité$$$1$ , parce que si nous rejetions tous les domaines précédents, la bonne décision serait d'arrêter dans le dernier domaine.

Pour déterminer la probabilité avec laquelle notre pièce asymétrique devrait lancer un aigle après avoir sauté la première zone, nous devons noter qu'après avoir sauté la première zone, il n'en reste que trois. Alors que nous roulons un os honnête, nous avons besoin que chacune de ces trois zones soit sélectionnée avec probabilité$$$\frac{1}{3}$ . Par conséquent, intuitivement, il semble que nous devrions avoir un deuxième os sur lequel l'aigle tombe avec probabilité $$$\frac{1}{3}$ . En utilisant un raisonnement similaire, on peut comprendre que lorsqu'une queue apparaît dans la deuxième région du réseau dans la troisième région, la pièce doit être lâchée par l'aigle avec probabilité $$$\frac{1}{2}$ , et dans la dernière zone - avec probabilité$$$1$ .

Cette compréhension intuitive nous conduit à l'algorithme suivant. Notez que nous n'avons pas discuté de l'exactitude ou de l'erreur de cet algorithme; nous le ferons bientôt.

Algorithme: simuler des os honnêtes à l'aide de pièces asymétriques

1. Pour $$$i = 0$ à$$$n - 1$ :
   
   1. Lancez une pièce asymétrique avec la probabilité d'un aigle $$$\frac{1}{n - i}$ .
   2. Si l'aigle tombe, revenez $$$i$ .

Cet algorithme est simple et, dans le pire des cas, s'exécute dans le temps. $$$O (n)$ .Mais comment vérifier si c'est correct? Pour le savoir, nous avons besoin du théorème suivant:

Théorème: l' algorithme ci - dessus renvoie le côté$$$i$ avec probabilité$$$\frac{1}{n}$ pour tout sélectionné$$$i$ .

Preuve: considérer toute constante$$$n \ge 0$ . En utilisant une forte induction, nous prouvons que chacun des $$$n$ faces a une probabilité de choix$$$\frac{1}{n}$ .

Pour notre exemple, nous montrons que le visage $$$0$ dés a une probabilité de choix$$$\frac{1}{n}$ . Mais cela découle directement de l'algorithme lui-même - nous choisissons la face 0 si sur une pièce asymétrique avec la probabilité d'un aigle $$$\frac{1}{n}$ , $$$\frac{1}{n}$ .

$$$0, 1, 2, ..., k - 1$ , $$$\frac{1}{n}$ $$$k$ . $$$k$ , $$$k$ , $$$\frac{1}{n - k}$ . $$$k$ $$$\frac{1}{n}$ , , $$$k$ est donné comme$$$\frac{k}{n}$ . Cela signifie que la probabilité que l'algorithme ne sélectionne pas l'un des premiers $$$k$ faces est égal à$$$1 - \frac{k}{n} = \frac{n}{n} - \frac{k}{n} = \frac{n - k}{n}$ . Autrement dit, la probabilité de choisir un visage $$$k$ est donné comme$$$\frac{n - k}{n} \frac{1}{n - k} = \frac{1}{n}$ , qui doit être montré. Ainsi, chaque face de l'os est sélectionnée de manière uniforme et aléatoire.

Bien sûr, l'algorithme est assez inefficace - en utilisant la première technique, nous pouvons simuler un lancer de dés honnêtes dans le temps $$$O(1)$ ! Mais cet algorithme peut être utilisé comme tremplin vers un algorithme suffisamment efficace pour simuler un os tricheur à l'aide de pièces asymétriques.

Simulation de l'os de Shuler à l'aide de pièces asymétriques

L'algorithme présenté ci-dessus est intéressant en ce qu'il nous donne un cadre simple pour simuler un os à l'aide d'un ensemble de pièces. Nous commençons par lancer une pièce pour déterminer s'il faut sélectionner la première facette de l'os ou passer au reste. Dans ce processus, nous devons gérer soigneusement l'échelle des probabilités restantes.

Voyons comment vous pouvez utiliser cette technique pour simuler un lancer d'os infidèle. Nous utilisons notre exemple avec probabilités$$$\frac{1}{2}$ , $$$\frac{1}{3}$ , $$$\frac{1}{12}$ , $$$\frac{1}{12}$ . Lui, si vous ne vous en souvenez pas, divise l'intervalle $$$[0, 1)$ comme suit:


Voyons maintenant comment simuler un tel os de triche à l'aide de pièces asymétriques. On peut commencer par lancer une pièce avec la probabilité d'un aigle$$$\frac{1}{2}$ pour déterminer si nous devons retourner face 0. Si un aigle tombe sur cette pièce, alors très bien! Nous avons terminé. Sinon, nous devons lancer une autre pièce pour décider de sélectionner la prochaine facette. Comme précédemment, malgré le fait que la prochaine facette a une probabilité de choix$$$\frac{1}{3}$ , nous ne voulons pas lancer une pièce sur laquelle l'aigle tombe avec probabilité$$$\frac{1}{3}$ , car la moitié de la «masse» des probabilités a été rejetée lorsque nous n'avons pas sélectionné de ligne avec$$$\frac{1}{2}$ . En fait, puisque la moitié de la masse des probabilités a disparu, alors si nous normalisons les probabilités restantes, nous obtiendrons des probabilités mises à jour: $$$\frac{2}{3}$ , $$$\frac{1}{6}$ , $$$\frac{1}{6}$ . Par conséquent, la deuxième pièce doit être lancée avec probabilité $$$\frac{2}{3}$ . Si cette pièce est également à queue, nous devons choisir entre deux faces $$$\frac{1}{12}$ . Puisqu'à ce stade nous allons nous débarrasser de $$$\frac{5}{6}$ masses de probabilités, alors nous pouvons normaliser à nouveau les probabilités des parties$$$\frac{1}{12}$ pour que chacun ait sa chance$$$\frac{1}{2}$ gouttes d'aigle, c'est-à-dire que la troisième pièce aura une probabilité$$$\frac{1}{2}$ . La dernière pièce, si jamais elle lui vient, devrait jeter l'aigle avec probabilité $$$1$ puisqu'il s'agit du domaine le plus récent.

Pour résumer, les probabilités des pièces seront les suivantes:

1. Premier lancer: $$$\frac{1}{2}$
2. Deuxième rouleau: $$$\frac{2}{3}$
3. Troisième rouleau: $$$\frac{1}{2}$
4. Quatrième rouleau: $$$1$

Il peut être intuitif d'où viennent ces nombres, mais pour transformer la sélection en algorithme, nous devons créer une construction formelle du choix des probabilités. L'idée sera la suivante - à chaque étape, nous nous souvenons du reste de la masse des probabilités. Au début, avant que la première pièce ne soit lancée, elle est égale à$$$1$ . Après avoir lancé la première pièce $$$1 - p_0$ . Après avoir lancé une deuxième pièce $$$1 - p_0 - p_1$ . Plus généralement après le lancer $$$k$ reste de la masse de probabilité est$$$1 - \sum_{i = 0}^{k - 1}{p_i}$ . Chaque fois que nous lançons une pièce pour déterminer s'il faut ou non sélectionner une zone $$$k$ , par conséquent, nous jetons une pièce, la probabilité qu'un aigle tombe sur laquelle est égale à la fraction de la probabilité restante occupée par la probabilité$$$p_k$ , qui est défini comme$$$\frac{p_k}{1 - \sum_{i = 0}^{k - 1}{p_i}}$ . Cela nous donne l'algorithme suivant pour tricher la simulation osseuse avec un ensemble de pièces asymétriques (nous prouverons son exactitude et sa durée d'exécution juste ci-dessous):

Algorithme: os Schuler de pièces asymétriques

• Initialisation :
  
  1. Nous gardons des probabilités $$$p_i$ pour une utilisation future.
• Génération :
  ensemble$$$mass = 1$
  Pour$$$i = 0$ à$$$n - 1$ :
  
  1. Lancez une pièce asymétrique avec la probabilité d'un aigle $$$\frac{p_i}{mass}$ .
  2. Si l'aigle tombe, revenez $$$i$ .
  3. Sinon, nous définissons $$$mass = mass - p_i$

D'un point de vue intuitif, c'est logique, mais est-ce mathématiquement vrai? Heureusement, la réponse est oui grâce à une généralisation de la preuve ci-dessus:

Théorème: l'algorithme montré ci-dessus renvoie un visage$$$i$ avec probabilité$$$p_i$ pour tout sélectionné$$$i$ .

Preuve: considérer toute constante$$$n \ge 0$ . , $$$n$ $$$p_i$ .

, $$$0$ $$$p_0$ . $$$0$ , , $$$\frac{p_0}{mass}$ . $$$mass$ $$$1$ , $$$\frac{p_0}{1} = p_0$ , 0 $$$p_0$ , .

, $$$0, 1, ..., k - 1$ $$$p_0, p_1, ..., p_{k-1}$ $$$k$ . $$$k$ , $$$k$ , $$$\frac{p_k}{mass}$ . $$$k$ , , $$$k$ $$$\sum_{i = 0}^{k - 1}{p_i}$ . , $$$k$ $$$1 - \sum_{i = 0}^{k - 1}{p_i}$ . , $$$k$ , $$$\frac{p_k}{mass}$ $$$k$ , $$$mass = 1 - \sum_{i = 0}^{k - 1}{p_i}$ . Cela signifie que la probabilité globale de choisir un visage $$$k$ est donné comme$$$(1 - \sum_{i = 0}^{k - 1}{p_i})\frac{p_k}{1 - \sum_{i = 0}^{k - 1}{p_i}} = p_k$, selon les besoins.

Évaluons maintenant la complexité temporelle de cet algorithme. Nous savons que le temps d'initialisation peut être$$$\Theta(1)$ si nous conservons une copie de surface du tableau de probabilité d'entrée, mais il peut y avoir$$$\Theta(n)$ afin que nous puissions enregistrer notre propre version du tableau (au cas où la fonction appelante voudrait la changer plus tard). La génération même d'un résultat de projection osseuse peut nécessiter dans le pire des cas$$$\Theta(n)$ lancers, et un seul lancer au mieux.

Cependant, après réflexion, il devient clair que le nombre de lancers de pièces nécessaires est fortement influencé par la distribution entrante. Dans le meilleur des cas, nous aurons une distribution de probabilité dans laquelle toute la masse des probabilités est concentrée sur le premier bord de l'os, et toutes les autres probabilités sont nulles. Dans ce cas, un tirage au sort nous suffit. Dans le pire des cas, la masse entière des probabilités est concentrée dans la toute dernière facette de l'os, et sur toutes les autres faces, elle est égale à zéro. Dans ce cas, nous devons jeter$$$n$ .

. $$$X$ , . $$$\mathbb{P}[X = 1]$ , , $$$\mathbb{P}[X = 2]$ — , , .. $$$X$ , $$$\mathbb{E}[X]$ . ,

$$ $$\mathbb{E}[X] = \sum_{i = 1}^n{i \cdot \mathbb{P}[X = i]}$$

$$$\mathbb{P}[X = i]$ ? - . $$$0$ , . $$$1$ , — , $$$0$ , , $$$1$ . , $$$i$ , $$$i + 1$ : $$$i$ , , $$$i - 1$ , , , $$$i$ . , $$$i$ $$$p_i$ , ,

$$ $$\mathbb{E}[X] = \sum_{i = 1}^n{i \cdot \mathbb{P}[X = i]} = \sum_{i = 1}^n{i \cdot p_{i - 1}} = \sum_{i = 1}^n{((i - 1) p_{i - 1} + p_{i - 1})} = \sum_{i = 1}^n{((i - 1) p_{i - 1})} + \sum_{i = 1}^n{p_{i - 1}}$$

Notez que dans la dernière simplification, le premier terme est équivalent $$$\ sum_ {i = 0} ^ {n-1} {i \ cdot p_i}$ ce qui est équivalent $$$\ mathbb {E} [p]$ , le résultat attendu d'un lancer de dés! De plus, le deuxième terme est égal à $$$1$ car c'est la somme de toutes les probabilités. Cela signifie que $$$\ mathbb {E} [X] = \ mathbb {E} [p] + 1$ . Autrement dit, le nombre attendu de lancers de pièces est égal à un plus l'attente mathématique d'un lancer de dé!

Algorithme	Temps d'initialisation		Temps de génération		Mémoire occupée
	Le meilleur	Le pire	Le meilleur	Le pire	Le meilleur	Le pire
Honnêteté os sharler bone	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Thêta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
Os Schuler de pièces asymétriques	$$$\ Theta (n)$		$$$\ Thêta (1)$	$$$\ Theta (n)$	$$$\ Theta (n)$

Généraliser les pièces asymétriques: simuler un os tricheur

Dans l'exemple ci-dessus, nous avons pu simuler efficacement une pièce asymétrique, car nous n'avions à prendre en compte qu'un seul point de partage. Comment généraliser efficacement cette idée à un os de triche dans lequel le nombre de visages peut être arbitraire?

Comme vous pouvez le voir, une pièce asymétrique est un os de triche, avec seulement deux faces. Par conséquent, nous pouvons percevoir une pièce asymétrique simplement comme un cas particulier d'un problème plus général que nous voulons résoudre. Lors de la résolution du problème des pièces asymétriques, nous divisons l'intervalle $$$[0, 1)$ en deux zones - une pour l'aigle, la seconde pour la queue - puis pour trouver la zone, nous utilisons le fait qu'il n'y a qu'un seul point de partage. Si nous avons un os à n faces, alors il y aura plus de zones, et donc plusieurs points de division. Supposons, par exemple, que nous ayons un os à sept côtés avec des probabilités $$$\ frac {1} {4}$ , $$$\ frac {1} {5}$ , $$$\ frac {1} {8}$ , $$$\ frac {1} {8}$ , $$$\ frac {1} {10}$ , $$$\ frac {1} {10}$ , $$$\ frac {1} {10}$ . Si nous voulons diviser l'intervalle $$$[0, 1)$ en sept parties, nous procédons comme suit:


Remarquez où se trouvent ces zones. Le premier domaine commence par $$$0$ et se termine $$$\ frac {1} {4}$ . Le deuxième domaine commence par $$$\ frac {1} {4}$ et se termine par $$$\ frac {1} {4} + \ frac {1} {5} = \ frac {9} {20}$ . Plus généralement, si les probabilités sont égales $$$p_0, p_1, ..., p_ {n - 1}$ , alors les zones seront des intervalles $$$[0, p_0)$ , $$$[p_0, p_0 + p_1)$ , $$$[p_0 + p_1, p_0 + p_1 + p_2)$ etc. C'est le domaine $$$i$ limité par intervalle

$$ $$[\ sum_ {j = 0} ^ {i - 1} {p_j}, \ sum_ {j = 0} ^ {i} {p_j})$$

Notez que la différence entre ces deux valeurs est $$$p_i$ c'est-à-dire que la superficie totale de la région est $$$p_i$ au besoin.

Maintenant, nous savons où se trouvent les zones. Si nous voulons choisir une valeur aléatoire uniformément distribuée $$$x$ dans la gamme $$$[0, 1)$ , alors comment déterminer dans quel intervalle tombe-t-il? Si nous utilisons l'algorithme de pièce asymétrique comme point de départ, l'idée sera la suivante: en partant du point final de la première région, remontez constamment dans toutes les zones jusqu'à ce que nous trouvions un point final dont la valeur est supérieure à la valeur $$$x$ . Si nous faisons cela, nous trouverons la première région contenant le point $$$x$ , et donc notre valeur. Par exemple, si nous avons choisi une valeur aléatoire $$$x = \ frac {27} {40}$ , puis effectuez la recherche suivante:


D'où nous pouvons conclure que la facette 3 est tombée sur des dés avec indexation à partir de zéro.

Un tel algorithme de balayage linéaire nous donnera un algorithme de temps $$$O (n)$ pour trouver le bord éjecté de l'os. Cependant, nous pouvons améliorer considérablement son temps d'exécution en utilisant l'observation suivante: une série de points d'extrémité de régions forme une séquence croissante (puisque nous ajoutons toujours de plus en plus de probabilités, dont aucune ne peut être inférieure à zéro). Par conséquent, nous voulons répondre à la question suivante: ayant une séquence croissante de valeurs et un certain point de contrôle, nous devons trouver la première valeur de l'intervalle strictement supérieure au point de contrôle. C'est le moment idéal pour utiliser la recherche binaire ! Par exemple, voici une recherche binaire sur le tableau ci-dessus pour trouver la zone à laquelle il appartient $$$x = \ frac {39} {40}$ :


Cela nous donne un algorithme au fil du temps. $$$\ Theta (\ log n)$ pour lier une valeur aléatoire uniformément distribuée dans l'intervalle $$$[0, 1)$ au bord d'un os abandonné. De plus, le temps de prétraitement est suffisant pour construire la table des points de terminaison $$$\ Theta (n)$ ; nous calculons simplement des sommes partielles de probabilités à mesure que nous progressons.

Cet algorithme est parfois appelé algorithme de sélection de la roulette car il sélectionne une zone aléatoire en utilisant une technique similaire à une roulette - lancer une balle dans un intervalle et observer où elle s'arrête. En pseudo-code, l'algorithme ressemble à ceci:

Algorithme: sélection de la roulette

• Initialisation :
  
  1. Sélectionnez un tableau $$$A$ la taille $$$n$
  2. Nous mettons $$$A [0] = p_0$ .
  3. Pour chaque probabilité $$$i$ de $$$1$ avant $$$n - 1$ :
     
     1. Nous mettons $$$A [i] = A [i - 1] + p_i$
  
  
• Génération :
  
  1. Générer une valeur aléatoire uniformément distribuée $$$x$ dans la gamme $$$[0, 1)$
  2. En utilisant une recherche binaire, nous trouvons l'index $$$i$ le plus petit élément $$$A$ ce qui est moins $$$x$ .
  3. Retour $$$i$ .

La comparaison entre cet algorithme et celui donné précédemment semble assez impressionnante:

Algorithme	Temps d'initialisation		Temps de génération		Mémoire occupée
	Le meilleur	Le pire	Le meilleur	Le pire	Le meilleur	Le pire
Honnêteté os sharler bone	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Thêta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
Os Schuler de pièces asymétriques	$$$\ Theta (n)$		$$$\ Thêta (1)$	$$$\ Theta (n)$	$$$\ Theta (n)$
Sélection de roue de roulette	$$$\ Theta (n)$		$$$\ Theta (\ log n)$		$$$\ Theta (n)$

De toute évidence, nous avons maintenant un algorithme bien meilleur que celui d'origine. La discrétion de la probabilité ne semblait que prometteuse au début, mais cette nouvelle approche, basée sur la valeur continue et la recherche binaire, semble bien meilleure. Cependant, il est toujours possible d'améliorer ces indicateurs grâce à l'utilisation intelligente d'un ensemble de techniques hybrides, dont nous parlerons ci-dessous.

Un détail intéressant de cet algorithme est que, bien que l'utilisation de la recherche binaire garantisse le pire des cas pour générer des nombres aléatoires $$$O (\ log n)$ , il ne permet pas non plus une recherche plus rapide; c'est-à-dire que le temps de génération sera également égal $$$\ Omega (\ log n)$ . Peut-il être amélioré? Il s'avère que vous le pouvez.

Supposons que nous passions d'une recherche binaire sur une liste de probabilités cumulatives à l'utilisation d'un arbre de recherche binaire . Par exemple, ayant l'ensemble de probabilités donné ci-dessus, nous pouvons construire l'arbre de recherche binaire suivant pour leur distribution cumulative:


Maintenant, si nous voulons simuler un roulement d'os, nous pouvons générer un nombre uniformément distribué dans l'intervalle $$$[0, 1)$ puis regardez à quel intervalle il se trouve dans cet arbre de recherche binaire (BST). Puisqu'il s'agit d'un arbre de recherche binaire équilibré, le meilleur temps de recherche est $$$O (1)$ et le pire $$$O (\ log n)$ .

Cependant, en supposant que nous en savons plus sur la distribution de probabilité, nous pouvons faire beaucoup mieux. Par exemple, supposons que nos probabilités soient égales $$$\ frac {99} {100}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ . Autrement dit, la distribution de probabilité est extrêmement asymétrique et presque toute la masse des probabilités est concentrée sur une seule face. Nous pouvons construire une BST équilibrée pour ces probabilités:


Bien que cet arbre de recherche binaire soit parfaitement équilibré, il n'est pas très adapté à nos tâches. Comme nous savons que dans 99 cas sur 100, la valeur aléatoire sera dans la plage $$$[0, \ frac {99} {100})$ , alors il est inutile de stocker le nœud pour cet intervalle où il se trouve maintenant. En fait, cela signifie que presque tout le temps, nous ferons deux comparaisons inutiles avec les zones bleues et jaunes. Étant donné qu'avec une probabilité très élevée, nous devrions être les premiers à vérifier le plus grand intervalle, il serait logique de déséquilibrer l'arbre afin de rendre le cas moyen bien meilleur en raison des autres. Ceci est montré ici:


Maintenant, nous allons probablement terminer la recherche en trouvant immédiatement la zone souhaitée après la première tentative. Dans le cas très improbable où la zone souhaitée se trouve dans le reste $$$(\ frac {99} {100}, 1]$ on descend calmement jusqu'au bout de l'arbre qui est en fait bien équilibré.

Dans une forme généralisée, nous voulons résoudre le problème suivant:

Étant donné un ensemble donné de probabilités, trouvez un arbre de recherche binaire pour ces probabilités qui minimise le temps de recherche attendu.

Heureusement, ce problème est très bien étudié et est appelé le problème d'arbre de recherche binaire optimal . Il existe de nombreux algorithmes pour résoudre ce problème; on sait que la solution exacte peut être trouvée à temps $$$O (n ^ 2)$ en utilisant la programmation dynamique , et qu'il existe de bons algorithmes de temps linéaire qui peuvent trouver des solutions approximatives. De plus, pour obtenir un facteur constant de la solution optimale, vous pouvez utiliser la structure de données de l' arbre d'affichage (arbre en expansion) (arbre de recherche binaire à équilibrage automatique).

Il est intéressant de noter que le meilleur cas pour le comportement de ces arbres de recherche binaires optimisés se produit lorsque les distributions de probabilité sont extrêmement asymétriques, car nous pouvons simplement déplacer les nœuds contenant la grande majorité de la masse de probabilité vers la racine de l'arbre, et le pire est lorsque la distribution est équilibrée, car alors l'arbre doit être large et peu profond. C'est l'opposé du comportement de l'algorithme précédent, dans lequel un honnête algorithme a été utilisé pour simuler un tricheur!

Dans le meilleur des cas, nous avons un tricheur dans lequel une face tombe toujours (c'est-à-dire qu'elle a une probabilité de 1 et toutes les autres faces ont une probabilité de 0). C'est une exagération extrême de notre exemple précédent, mais dans ce cas, la recherche se terminera toujours après la première tentative. Dans le pire des cas, toutes les probabilités sont égales et nous obtenons une recherche BST standard. Nous arrivons à ce qui suit:

Algorithme	Temps d'initialisation		Temps de génération		Mémoire occupée
	Le meilleur	Le pire	Le meilleur	Le pire	Le meilleur	Le pire
Honnêteté os sharler bone	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Thêta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
Os Schuler de pièces asymétriques	$$$\ Theta (n)$		$$$\ Thêta (1)$	$$$\ Theta (n)$	$$$\ Theta (n)$
Sélection de roue de roulette	$$$\ Theta (n)$		$$$\ Theta (\ log n)$		$$$\ Theta (n)$
Sélection optimale des roues de roulette	$$$O (n ^ 2)$		$$$\ Thêta (1)$	$$$O (\ log n)$	$$$\ Theta (n)$

Lancer de fléchettes

Jusqu'à présent, nous avons envisagé deux primitives qui nous ont aidés à construire des algorithmes pour simuler un os tricheur: l'os honnête et la pièce asymétrique. En utilisant uniquement de l'os honnête, nous arrivons à un algorithme (hélas, peu pratique) pour tricher l'os, et à partir de pièces asymétriques, nous avons pu inventer un algorithme rapide pour tricher l'os. Ces deux approches peuvent-elles être combinées pour créer un algorithme basé sur des os honnêtes et des pièces asymétriques? Il s'avère que oui, et en fait, l'algorithme résultant est meilleur que ces deux approches.

Jusqu'à ce moment, nous avons visualisé l'intervalle $$$[0, 1)$ et les probabilités des faces osseuses comme intervalle unidimensionnel. Ces deux algorithmes sélectionnent un point dans l'intervalle $$$[0, 1)$ et posez-le sur un segment de ligne droite, dont la longueur correspond à une sorte de probabilité. Plus les segments que nous créons sont longs, plus la probabilité de choisir ce segment est grande. Mais que faire si vous essayez de penser non pas en une, mais en deux dimensions? Et si nous prenons la probabilité $$$p_i$ pas la longueur d'un segment de ligne droite, mais l'aire d'un rectangle?

Commençons par revenir à notre exemple précédent avec probabilités $$$\ frac {1} {2}$ , $$$\ frac {1} {3}$ , $$$\ frac {1} {12}$ , $$$\ frac {1} {12}$ . Nous représentons ces probabilités sous forme de rectangles de largeur $$$w$ (avec quelques arbitraires $$$w> 0$ ) et hauteur $$$p_i$ (ainsi, l'aire du rectangle sera égale à $$$w \ cdot p_i$ ):


Notez que l'aire totale de ces rectangles est $$$w$ depuis la zone

$$ $$\ sum_ {i = 0} ^ {n - 1} {w p_i} = w \ sum_ {i = 0} ^ {n - 1} {p_i} = w$$

Supposons maintenant que nous dessinons un rectangle englobant autour de ces rectangles dont la largeur est $$$4w$ (car il y a quatre quadrangles), et la hauteur est $$$\ frac {1} {2}$ (puisque le rectangle le plus haut a une hauteur $$$\ frac {1} {2}$ ):


Nous pouvons imaginer que ce rectangle est divisé en cinq zones - quatre zones correspondent à des probabilités différentes et une zone indique un espace inutilisé. En prenant cette pause, nous pouvons considérer l'algorithme de simulation de lancer de dés aléatoire comme un jeu de fléchettes. Supposons que nous lançons une fléchette (parfaitement uniformément répartie) sur cette cible. Si elle tombe dans l'espace inutilisé, nous sortons la fléchette et la jetons à nouveau, en répétant le processus jusqu'à ce que nous entrions dans l'un des rectangles. Étant donné que plus la probabilité est grande, plus le rectangle est grand, plus la probabilité de lancer le bord de l'os est grande, plus la probabilité de tomber dans son rectangle est élevée. En fait, si nous fixons la condition que nous sommes déjà tombés dans une sorte de rectangle, nous obtenons ce qui suit:

$$ $$\ mathbb {P} [\ mbox {a frappé le rectangle pour le côté i} | \ mbox {frapper un rectangle}] = \ frac {\ mbox {aire de rectangle pour i}} {\ mbox {aire totale de rectangle}} = \ frac {w p_i} {w} = p_i$$

En d'autres termes, lorsque nous tombons finalement dans une sorte de rectangle avec notre fléchette uniformément répartie, nous sélectionnons le rectangle de face $$$i$ os tricheur avec probabilité $$$p_i$ , c'est-à-dire avec la probabilité dont nous avons besoin! Autrement dit, si nous pouvons trouver un moyen efficace de simuler le lancement de fléchettes aléatoires sur ce rectangle, alors nous aurons un moyen efficace de simuler le lancement d'un dé aléatoire.

Une façon de simuler des lancers de fléchettes sur ce rectangle consiste à sélectionner deux valeurs uniformément réparties dans l'intervalle $$$[0, 1)$ les mettre à l'échelle à la largeur et à la hauteur appropriées, puis vérifier la zone sous la fléchette. Cependant, cela pose le même problème que nous avions lorsque nous avons essayé de déterminer la région unidimensionnelle dans laquelle se trouve la valeur aléatoire. Cependant, il existe une série d'observations vraiment merveilleuses, grâce à laquelle déterminer le lieu de l'impact peut être une tâche simple, sinon triviale.

Première observation: nous avons montré que la largeur de ces rectangles peut être choisie arbitrairement, car tous ont une largeur égale. Les hauteurs, bien sûr, dépendent des probabilités des faces des os. Cependant, si nous mettons à l'échelle uniformément toutes les hauteurs par un certain nombre réel positif $$$h$ , alors les zones relatives de tous les rectangles seront les mêmes. En fait, pour tout nombre réel positif $$$h$ surface totale de tous les rectangles après avoir mis leur hauteur à l'échelle $$$h$ calculé comme

$$ $$\ sum_ {i = 0} ^ {n - 1} {w h p_i} = w h \ sum_ {i = 0} ^ {n - 1} {p_i} = w h$$

Nous allons maintenant considérer la probabilité de choisir un rectangle individuel, en nous limitant à la condition que nous frappions définitivement une sorte de rectangle. En utilisant les mêmes calculs, nous obtenons ce qui suit:

$$ $$\ mathbb {P} [\ mbox {a frappé le rectangle pour le côté i} | \ mbox {frapper un rectangle}] = \ frac {\ mbox {aire de rectangle pour i}} {\ mbox {aire totale de rectangle}} = \ frac {w h p_i} {w h} = p_i$$

Autrement dit, la probabilité de choisir un seul rectangle ne change pas si nous les mettons à l'échelle de façon linéaire et uniforme.

Puisque nous pouvons choisir n'importe quel facteur d'échelle approprié, pourquoi ne pas mettre à l'échelle ces rectangles de sorte que la hauteur du cadre de sélection soit toujours 1? Étant donné que la hauteur du cadre de sélection est déterminée par la valeur maximale $$$p_i$ probabilités d'entrée, alors nous pouvons commencer par mettre à l'échelle chacun des rectangles par un facteur $$$\ frac {1} {p_ {max}}$ où $$$p_ {max}$ Est la probabilité maximale de toutes les probabilités d'entrée. Grâce à cela, nous obtenons la hauteur du rectangle 1. De même, comme nous pouvons choisir n'importe quelle largeur arbitraire pour les rectangles, prenons la largeur 1. Cela signifie que pour $$$n$ les probabilités de la largeur totale du cadre de délimitation sont $$$n$ , et la hauteur totale est 1. Ceci est illustré dans la figure:


Nous sommes maintenant prêts à réfléchir à la façon de lancer une fléchette aléatoire dans un rectangle et de déterminer dans quoi elle est tombée. La chose la plus importante est que nous pouvons diviser le rectangle afin qu'il ne soit pas composé de plusieurs petits rectangles et d'un espace vide d'une forme étrange. Au lieu de cela, la zone est découpée en un ensemble de $$$2n$ rectangles, deux sur chacun $$$n$ probabilités d'entrée. Ceci est montré ici:


Remarquez comment ce rectangle se forme. Pour chaque face de l'os du tricheur, nous avons une colonne d'une largeur de 1 et d'une hauteur de 1, divisée en deux espaces - un demi-espace "oui" correspondant à un rectangle de cette taille et un demi-espace "non" correspondant à la partie restante de la colonne.

Voyons maintenant comment lancer une fléchette. Une fléchette parfaitement uniforme jetée dans ce rectangle aura des composants $$$x$ et $$$y$ . Ici le composant $$$x$ qui devrait être dans l'intervalle $$$[0, 1)$ , correspond à la colonne que la fléchette frappe. Composant $$$y$ qui devrait être dans l'intervalle $$$[0, 1)$ , correspond à la hauteur de notre colonne. Sélection des composants $$$x$ affecte la face de l'os tricheur que nous considérons et le choix du composant $$$y$ correspond à savoir si nous avons choisi cette facette ou non. Mais attendez - nous connaissons déjà ces deux idées! Sélection de coordonnées $$$x$ correspondant à la colonne, semblable à jeter un os honnête pour décider du choix de la colonne. Sélection de coordonnées $$$y$ correspond au lancer d'une pièce asymétrique pour déterminer s'il faut sélectionner un visage ou lancer à nouveau! Cette observation est si importante que nous la rendons absolument compréhensible:

Le choix d'un point aléatoire dans cet intervalle revient à lancer un os honnête et à lancer une pièce asymétrique.

En fait, ce résultat peut être perçu comme une opportunité beaucoup plus puissante. Pour simuler un os tricheur, nous construisons un ensemble de pièces asymétriques, une pour chaque face de l'os, puis roulons un os honnête pour déterminer quelle pièce lancer. Sur la base du roulement de l'os, si un aigle tombe sur la pièce correspondante, nous sélectionnons la face correspondante, et si les queues tombent, jetons à nouveau l'os et répétons le processus.

. -, — «» $$$\frac{p_i}{p_{max}}$ , «» $$$\frac{p_{max} - p_i}{p_{max}}$ . , 1. -, $$$1$ , . , : - , , ( , ). . , , . .

: /

• :
  
  1. $$$p_i$ ; $$$p_{max}$ .
  2. $$$Coins$ $$$n$ , «» .
  3. $$$i$ de $$$0$ avant $$$n - 1$ :
     
     1. $$$Coins[i] = \frac{p_i}{p_{max}}$
  
  
• :
  
  1. :
     
     1. n- $$$i$ $$$[0, n)$ .
     2. , $$$Coins[i]$ .
     3. , $$$i$ .

. $$$O (n)$ , $$$O (n)$ $$$Coins$ , $$$O (n)$ . , $$$O(1)$ . ? , , - . , . , ( $$$\frac{1}{n}$ ), . , , , , - , . , $$$i$ $$$\frac{p_i}{p_{max}}$ , -

$$ $$\sum_{i = 0}^{n - 1}{(\frac{1}{n} \frac{p_i}{p_{max}})} = \frac{1}{n}\sum_{i = 0}^{n - 1}{\frac{p_i}{p_{max}}} = \frac{1}{n \cdot p_{max}}\sum_{i = 0}^{n - 1}{p_i} = \frac{1}{n \cdot p_{max}}$$

- , , , , , $$$n \cdot p_{max}$ . ? $$$p_{max}$ . $$$p_{max}$ $$$1$ ( ). $$$n$ , $$$n$ . , , , , . , $$$p_{max}$ $$$\frac{1}{n}$ , , . Si $$$p_{max} = \frac{1}{n}$ , 1. . Si $$$p_{max} = \frac{1}{n}$ , ( $$$\frac{1}{n}$ ), 1, , 1. , , .

, $$$p_{max}$ , , , . , , $$$n$ , , 1. , , «» $$$\frac{1}{p_{max}}$ , 1, $$$\frac{1}{p_{max}}$ . , «» $$$\frac{1}{n \cdot p_{max}}$ . , , «», $$$p_{max}$ . , , .

:

Algorithme
	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$ ()	$$$\Theta(n)$

, . . ?

Alias-

, . , . , , «» , . , , , . - , , - , .

, , , . . $$$\frac{1}{2}$ , $$$\frac{1}{3}$ , $$$\frac{1}{12}$ , $$$\frac{1}{12}$ . , $$$\frac{1}{4}$ . , $$$\frac{1}{4}$ , $$$\frac{1}{2}$ ? , . $$$1$ , :


, $$$\frac{1}{4}$ 1. , , :


$$$1 \times 4$ . , :


, , $$$\frac{1}{2}$ et $$$\frac{1}{3}$ . ? , $$$\frac{1}{2}$ $$$\frac{1}{12}$ ? , - , :


, , . , $$$\frac{1}{2}$ et $$$\frac{1}{3}$ , . $$$\frac{1}{2}$ , . , :


, , :


. -, . , ; . , , . -, , , - , , . , . — , . , — , , . , . , , , - ( ).

alias- . -, , . , , . , , , .

, , ? , , . , , , , , . , . , - , , , ( ) , - . (alias) , «» - . - «alias» «alias-».

, , . - ( !), () , , alias- : $$$Prob$ alias $$$Alias$ . $$$n$ . , alias , ( ). , . - - $$$i$ . $$$Prob[i]$ . , , $$$i$ , , $$$Alias[i]$ . alias :

Alias

, $$$Alias$ et $$$Prob$ . , , :

• $$$(n \cdot p_i) \times 1$ $$$p_i$ ,
• $$$n$
  
  • , $$$1$ ,
  • , $$$i$ , $$$i$ .

, , . , $$$\frac{1}{2}$ , $$$\frac{1}{3}$ , $$$\frac{1}{12}$ , $$$\frac{1}{12}$ . ( $$$k = n = 4$ ), $$$1 = \frac{4}{4}$ . , alias, , . , 4, :


, , ( $$$\frac{1}{3}$ , $$$\frac{1}{3}$ ) 1. , - . ( ) :


- . , , , 1 ( $$$2$ et $$$\frac{4}{3}$ ). ; $$$\frac{4}{3}$ . $$$\frac{4}{3}$ , ; $$$\frac{2}{3}$ de $$$\frac{4}{3}$ , :


, . , $$$3$ , , , . , . , , $$$1$ , (, $$$\frac{2}{3}$ ) :


, - , 1, . ( $$$2$ ), $$$\frac{1}{3}$ de $$$2$ :


, . , - , 1 ( $$$\frac{1}{3}$ ), :


- $$$1$ , . — $$$\frac{5}{3}$ :


, 1. , :


! .

, :

• - , 1, , $$$Prob$ .
• - , 1, , $$$Alias$ , .

, ? «», ? , . : , 1 ( $$$\frac{1}{n}$ , $$$n$ ). , , , , 1 ( ) 1 ( ). , . , ? , . , , . , .

:

: $$$k$ $$$h_0$ , $$$h_1$ , ..., $$$h_{k-1}$ , , $$$\sum_{i=0}^{k-1}{h_i} = k$ , $$$k$ , 1, , , $$$i$ - $$$i$ - .

: . , $$$k = 1$ , 1. $$$0$ - . , 1, , $$$0$ - $$$0$ - .

, - $$$k$$$$k + 1$$$$1$$$$h_0$, $$$h_1$, ..., $$$h_{k}$, , $$$\sum_{i = 0}^{k}{h_i} = k + 1$. , $$$h_l$, , $$$h_l \le 1$, - $$$h_g$(, $$$l \ne g$), , $$$h_g \ge 1$. , , $$$h_l$avec $$$h_l \le 1$; , $$$h_i > 1$$$$i$$$$0 \le i \le k$. , $$$k + 1 = \sum_{i = 0}^k{h_i} > \sum_{i=0}^k{1} = k + 1$, . , - $$$l$, , $$$h_l \le 1$. , $$$h_g$( $$$l \ne g$), , $$$h_g \ge 1$. , $$$h_g < 1$, ( ) $$$\sum_{i=0}^{k}{h_i} < k + 1$. , $$$h_l \le 1$et $$$h_g \ge 1$.

. $$$h_l$$$$l$$$$1 - h_l$dans $$$l$- $$$h_g$( , $$$0 \le 1 - h_l \le 1$et $$$h_g \ge 1$). . $$$k$, $$$k$, $$$1$, $$$k + 1$. , $$$l$, . , , $$$k$dans $$$k$, . , $$$l$, , , . .

, , alias, , . alias.

Alias

, alias-. 1 1, :

: Alias-

• :
  
  1. $$$p_i$sur $$$n$.
  2. $$$Alias$et $$$Prob$, $$$n$.
  3. For $$$j = 1 \mbox{ to } n - 1$:
     
     1. $$$p_l$, $$$p_l \le 1$.
     2. $$$p_g$( $$$l \ne g$), $$$p_g \ge 1$
     3. $$$Prob[l] = p_l$.
     4. $$$Alias[l] = g$.
     5. $$$p_l$.
     6. $$$p_g := p_g - (1 - p_l)$.
     
     
  4. $$$i$, 1.
  5. $$$Prob[i] = 1$.
  
  
• :
  
  1. $$$n$- ; $$$i$.
  2. , $$$Prob[i]$.
  3. , $$$i$.
  4. $$$Alias[i]$.

, , $$$\Theta(1)$. . -, $$$\Theta(n)$$$$n$, $$$O (n)$. $$$\Theta(n)$, $$$O (n)$, . $$$O(n^2)$. , :

Algorithme
	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$()	$$$\Theta(n)$
Alias-	$$$O(n^2)$		$$$\Theta(1)$		$$$\Theta(n)$

alias- , . - (, $$$O (n)$), .

. , $$$O (n)$. . $$$p_g$et $$$p_l$$$$O(\log n)$, . $$$p_l$$$$O(\log n)$, $$$p_g$$$$O(\log n)$. :

: Alias-

• :
  
  1. $$$Alias$et $$$Prob$, $$$n$.
  2. $$$T$.
  3. $$$n \cdot p_i$dans $$$T$$$$i$.
  4. For $$$j = 1 \mbox{ to } n - 1$:
     
     1. $$$T$; $$$p_l$.
     2. $$$T$; $$$p_g$.
     3. $$$Prob[l] = p_l$.
     4. $$$Alias[l] = g$.
     5. $$$p_g := p_g - (1 - p_l)$.
     6. $$$p_g$à $$$T$.
     
     
  5. $$$i$, 1.
  6. $$$Prob[i] = 1$.
  
  
• :
  
  1. $$$n$- ; $$$i$.
  2. , $$$Prob[i]$.
  3. , $$$i$.
  4. $$$Alias[i]$.

. $$$Alias$et $$$Prob$- $$$O (n)$, BST $$$T$$$$\Theta(n \log n)$. $$$\Theta(n)$, $$$O(\log n)$. $$$O(n \log n)$:

Algorithme
	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$()	$$$\Theta(n)$
Alias-	$$$O(n^2)$		$$$\Theta(1)$		$$$\Theta(n)$
Alias-	$$$O(n \log n)$		$$$\Theta(1)$		$$$\Theta(n)$

, . , , , alias-. «A Linear Algorithm For Generating Random Numbers With a Given Distribution» , alias-.

: 1, 1. . «» , «» «». :

• «» 1.
• «» 1.
• .

, , , . , :

: () Alias-

: . .

• :
  
  1. $$$Alias$et $$$Prob$, $$$n$.
  2. , $$$Small$et $$$Large$.
  3. $$$n$.
  4. $$$p_i$:
     
     1. Si $$$p_i < 1$, $$$i$à $$$Small$.
     2. ( $$$p_i \ge 1$) $$$i$à $$$Large$.
     
     
  5. $$$Small$:
     
     1. $$$Small$; $$$l$.
     2. $$$Large$; $$$g$.
     3. $$$Prob[l] = p_l$.
     4. $$$Alias[l] = g$.
     5. $$$p_g := p_g - (1 - p_l)$.
     6. Si $$$p_g < 1$, $$$g$dans $$$Small$.
     7. ($p_g \ge 1$) $$$g$dans $$$Large$.
     
     
  6. $$$Large$:
     
     1. $$$Large$; $$$g$.
     2. $$$Prob[g] = 1$.
     
     
  
  
• :
  
  1. $$$n$- ; $$$i$.
  2. , $$$Prob[i]$.
  3. , $$$i$.
  4. $$$Alias[i]$.

(, ) : - $$$Small$$$$Large$, . . $$$Small$$$$Large$( $$$Small$, , ). $$$Large$1, $$$k$$$$Large$$$$k$, $$$Large$1, . 1, , , 1.

. , , , . .

, . $$$\frac{1}{4}$, $$$\frac{1}{5}$, $$$\frac{1}{8}$, $$$\frac{1}{8}$, $$$\frac{1}{10}$, $$$\frac{1}{10}$, $$$\frac{1}{10}$. , , $$$\frac{1}{8}$, $$$\frac{1}{5}$, $$$\frac{1}{10}$, $$$\frac{1}{4}$, $$$\frac{1}{10}$, $$$\frac{1}{10}$, $$$\frac{1}{8}$. :


$$$Small$, :


$$$Large$( ) . $$$\frac{7}{4} - \frac{1}{8} = \frac{13}{8} \ge 1$, $$$Large$:


. $$$Small$, $$$Large$:


:


, , , . , :


$$$Small$, :


$$$Small$, , :


, $$$Small$, .


alias .

, . , , IEEE-754 double, . , , :

1. , $$$Small$$$$Large$, . , , $$$n$, , $$$\frac{1}{n}$, $$$1$( $$$Small$, $$$Large$).
2. , , . , , $$$Large$, $$$Small$.

, $$$Small$$$$Large$. , , $$$Small$, $$$Large$.

, . , , , $$$Large$. -, , $$$1$, , $$$1$. , . :

: Alias-

• :
  
  1. $$$Alias$et $$$Prob$, $$$n$.
  2. , $$$Small$et $$$Large$.
  3. $$$n$.
  4. $$$p_i$:
     
     1. Si $$$p_i < 1$, $$$i$dans $$$Small$.
     2. ( $$$p_i \ge 1$) $$$i$dans $$$Large$.
     
     
  5. $$$Small$et $$$Large$: ( $$$Large$)
     
     1. $$$Small$; $$$l$.
     2. $$$Large$; $$$g$.
     3. $$$Prob[l] = p_l$.
     4. $$$Alias[l] = g$.
     5. $$$p_g := (p_g + p_l) - 1$. ( . )
     6. Si $$$p_g < 1$, $$$g$dans $$$Small$.
     7. ( $$$p_g \ge 1$) $$$g$dans $$$Large$.
     
     
  6. $$$Large$:
     
     1. $$$Large$; $$$g$.
     2. $$$Prob[g] = 1$.
     
     
  7. $$$Small$: - .
     
     1. $$$Small$; $$$l$.
     2. $$$Prob[l] = 1$.
     
     
  
  
• :
  
  1. $$$n$- ; $$$i$.
  2. , $$$Prob[i]$.
  3. , $$$i$.
  4. $$$Alias[i]$.

, — . $$$\Theta(n)$, . $$$\Theta(1)$, , . $$$O (n)$, () , . $$$O (n)$, $$$Large$et $$$Small$$$$O (n)$. $$$\Theta(n)$, ( ) :

Algorithme
	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$()	$$$\Theta(n)$
Alias-	$$$O(n^2)$		$$$\Theta(1)$		$$$\Theta(n)$
Alias-	$$$O(n \log n)$		$$$\Theta(1)$		$$$\Theta(n)$
Alias-	$$$\Theta(n)$		$$$\Theta(1)$		$$$\Theta(n)$

Ouah! ! , . , (alias- ) , - .

alias- , , - , alias- Java , .

, !