Probabilités d'élimination

Knockout est un jeu de basket-ball où les joueurs tirent à tour de rôle. Il se joue comme une séquence de compétitions à deux joueurs, chacune ayant la possibilité de "mettre KO" un de ces joueurs.

Supposons que les joueurs le soient A B C Det que leurs chances de tirer et de faire un panier soient 0.1 0.2 0.3 0.4respectivement, indépendamment de l'autre joueur du concours. Les deux joueurs en tête de file, Aet B, "se battent". Depuis Ale premier, il est le défenseur , en danger d'être éliminé, et Bl' attaquant , et non en danger d'élimination immédiate. Atire en premier. Si le Afait, Aa défendu avec succès et va au fond de la ligne. La ligne deviendrait B C D A. Si Ane le fait pas, Btire. Si le Bfait, alors Aest sorti et Bva à l'arrière de la ligne, donc la ligne devient C D B. Si ni l'un ni l'autreAni le Bfait, le processus se répète, avec la Aprise de vue à nouveau, jusqu'à ce que soit Aou Bfait un panier.

Supposons que la ligne soit devenue B C D A( Aavait réussi à se défendre). Maintenant, Bet C"combattez", en Bétant le défenseur et en Cétant l'attaquant. Ce processus se répète jusqu'à ce qu'il ne reste qu'une seule personne. Cette personne est la gagnante.

Votre tâche consiste à calculer les probabilités de chaque personne gagnante compte tenu de la chance qu'elle fera un panier.

Entrée :

Une liste des numéros, par exemple 0.1 0.2ou 0.5 0.5 0.5 0.5, où le n ième nombre est la chance que le n ième joueur fera un panier. Vous pouvez prendre cette entrée dans le format de votre choix, y compris comme paramètres d'une fonction.

Sortie :

Une liste des numéros, où le n ième nombre est la chance que le n ième joueur gagnera le match. Vos chiffres doivent être précis à au moins deux décimales au moins 90% du temps. Cela signifie que vous pouvez utiliser une approche basée sur la simulation. Cependant, si votre code n'est pas basé sur la simulation (il est garanti de retourner une réponse correcte à au moins 6 décimales), retirez 30% de votre score.

Exemple entre 0.5 0.5: Appelez les joueurs Aet B. Soit pla probabilité de gagner A. Aa une 2/3chance de défendre avec succès (car il y a une 1/2chance que les Ascores, une 1/4chance qui Amanque et Bmarque, et une 1/4chance que les deux manquent et que le processus se répète). S'il Ane parvient pas à se défendre, il est mis KO et Bgagne. Si Adéfend, alors la ligne devient B A. Puisque la situation est symétrique, la probabilité de Agagner est (1 - p). On a:

p = 2/3 * (1 - p) + 1/3 * 0. Résoudre, nous obtenons p = 2/5. La sortie doit être 2/5 3/5ou 0.4 0.6.

Je ne suis pas assez bon avec la probabilité de faire des exemples plus complexes.

Si vous avez besoin de plus de cas de test, en voici quelques-uns:

0.1 0.2 0.3 0.4 --> 0.01 0.12 0.25 0.62
0.99 0.99 --> 0.5 0.5 (it's not exact, but if you round to two decimal places, you get 0.5 and 0.5)

CJam ( 84 80 caractères * 0,7 = 56)

{_,({_,,{_2$m<(;(+Q0\)\++m>\}%)_(+.{X2$-*_@+/}1\{1$*\1$-}%)1\-f/.f*:.+}{,da}?}:Q

Démo en ligne . Il s'agit d'une fonction récursive qui prend un tableau de doubles et renvoie un tableau de doubles. La démo en ligne comprend une infime quantité d'échafaudages pour exécuter la fonction et formater la sortie pour l'affichage.

Dissection

Le principe de base est que s'il reste des n > 1joueurs, l'un d'eux doit être le prochain à être éliminé. De plus, l'ordre de la file d'attente après cela ne dépend que de l'ordre initial de la file d'attente et de qui est mis KO. Nous pouvons donc effectuer ndes appels récursifs, calculer les probabilités de gain pour chaque joueur dans chaque cas, puis il nous suffit de pondérer de manière appropriée et d'ajouter.

Je vais étiqueter les probabilités d'entrée comme [p_0 p_1 ... p_{n-1}]. Soit f(a,b)la probabilité de ane pas se défendre b. Dans un round donné, la probabilité de se adéfendre avec succès est p_a, la probabilité que le bKO asoit (1-p_a)*p_bet la probabilité qu'il passe à un autre round (1-p_a)*(1-p_b). On peut soit faire une somme explicite d'une progression géométrique, soit argumenter que les deux progressions géométriques sont proportionnelles l'une à l'autre pour raisonner f(a,b) = (1-p_a)*p_b / (p_a + (1-p_a)*p_b).

Ensuite, nous pouvons passer d'un niveau à des tours complets de la ligne. La probabilité que le premier joueur soit mis KO est f(0,1); la probabilité que le deuxième joueur soit mis KO est (1-f(0,1)) * f(1,2); le troisième joueur est (1-f(0,1)) * (1-f(1,2)) * f(2,3); etc jusqu'à ce que le dernier soit éliminé avec probabilité \prod_i (1-f(i,i+1)) * f(n-1,0). Le même argument sur les progressions géométriques nous permet d'utiliser ces probabilités comme poids, avec normalisation par un facteur de 1 / \prod_i f(i, i+1 mod n).

{                   e# Define a recursive function Q
  _,({              e# If we have more than one person left in the line...
    _,,{            e#   Map each i from 0 to n-1...
      _2$m<         e#     Rotate a copy of the probabilities left i times to get [p_i p_{i+1} ... p_{n-1} p_0 ... p_{i-1}]
      (;(+          e#     i fails to defend, leaving the line as [p_{i+2} ... p_{n-1} p_0 ... p_{i-1} p_{i+1}]
      Q             e#     Recursive call
      0\)\++        e#     Insert 0 for the probability of i winning and fix up the order
      m>\           e#     Rotate right i times and push under the list of probabilities
    }%
    )               e#   Stack: [probs if 0 knocked out, probs if 1 knocked out, ...] [p_0 p_1 ...]
    _(+.{           e#   Duplicate probs, rotate 1, and pointwise map block which calculates f(a,b)
      X2$-*_@+/     e#     f(a,b) = (1-p_a)*p_b / (p_a + (1-p_a)*p_b)  TODO is the d necessary?
    }
    1\{1$*\1$-}%    e#   Lift over the list of f(a,b) a cumulative product to get the weights  TODO is the d necessary?
    )1\-f/          e#   Normalise the weights
    .f*             e#   Pointwise map a multiplication of the probabilities for each case with the corresponding weight
    :.+             e#   Add the weights across the cases
  }{,da}?           e# ...else only one left, so return [1.0]
}:Q