Probabilité de personnes qui ne font pas face à leur partenaire lors d'une table ronde

Si les couples sont assis au hasard à une table ronde, quelle est la chance que personne ne soit assis en face de leur partenaire?

S'il y a quatre personnes, la réponse est 2/3.

S'il y en a six c'est 8/15, je pense.

Après cela, ma méthode étape par étape, remplissant toutes les possibilités et se terminant par une somme de diverses valeurs attendues, devient assez laborieuse. Curieusement, une approche intuitive obtient la bonne réponse pour 6 personnes sous la forme de (4/5) x (2/3), mais j'ai du mal à généraliser cela. Existe-t-il une méthode soignée conduisant à une formule pour le cas de 2n personnes (n couples)?

Une analyse

Supposons, puis améliorons systématiquement la supposition jusqu'à ce qu'elle soit correcte.

Commencez par deviner que la réponse est . Bien sûr, c'est faux. Pour voir à quel point, étiquetez un partenaire dans chaque paire "Rouge" et l'autre "Bleu". Du point de vue de tout individu rouge, il y a chance que son partenaire (bleu) s'assoie en face d'eux. Parce qu'il y a individus rouges, soustrayons de cette supposition initiale.$1$$1/(2n-1)$$n$$n\times 1/(2n-1)$

Mais attendez - ce n'est toujours pas tout à fait raison, car toutes les paires de couples ont été comptées deux fois. Si un couple est assis en face, il reste couples, places, et du point de vue de tout individu rouge, la chance qu'ils fassent partie d'un deuxième couple est de . Par conséquent, nous devons rajouter .$n-1$$2n-2$$1/(2n-3)$$\binom{n}{2}\times 1/(2n-1)\times 1/(2n-3)$

Mais maintenant, nous avons sous-estimé les contributions au résultat des triplets de couples, que nous devons corriger. Et il en va ainsi, jusqu'à ce que nous ayons finalement accueilli les couples dans la formule. (Ceci, bien sûr, n'est que le principe d'inclusion-exclusion en action.) $n$

La formule résultante est

Calcul

Pour les entiers positifs , la fonction hypergéométrique confluente de Kummer est un polynôme de degré en . De la transformation de Kummer$n$ ${_1}F_1\left(-n, -n+\frac{1}{2}, z\right)$$n$$z$

il est simple de déduire que la valeur limite de la probabilité lorsque grandit est . La convergence est lente: vous devez multiplier par pour atteindre un chiffre décimal supplémentaire. Néanmoins, des valeurs précises (double précision) peuvent être rapidement calculées pour tout en notant que les termes dans la somme de gauche croissent plus lentement que les puissances de . Ainsi, au moment où atteint , les nouvelles valeurs seront essentiellement nulles par rapport à (et en fait une analyse plus approfondie suggère que l'arrêt de la sommation par$n$$e^{-1/2} \approx 0.6065306597\ldots$$n$$10$$n$$(1)$$-1/2$$i$$52$$e^{-1/2}$$i=45$ marchera).

Cette formule se décomposera pour supérieur à 10 000 000 dans certains environnements informatiques en raison de l'imprécision de la fonction log Gamma. Le problème provient de l'annulation des différences survenant lors du calcul des termes dans la série. Une excellente approximation de ces différences lorsque est suffisamment grand peut être trouvée en termes de , où est la dérivée de (la fonction digamma ). Cela est implémenté dans le code ci-dessous, à un faible coût en temps de calcul.$n$$n$$\psi(n-1/4)$$\psi$$\log \Gamma$

la mise en oeuvre

Le Rcode suivant calcule environ 20 000 valeurs de double précision par seconde.

f <- function(n) {
  h <- function(n) {
    ifelse(n < 1e6, lfactorial(n) - lfactorial(n-1/2), digamma(n+3/4)/2)
  }
  m <- min(n, 46)
  k <- 0:m
  x <- exp(h(n) - h(n-k) - lfactorial(k) - k*log(2)) * (-1)^k
  sum(x)
}

À titre d'exemple, suivons à quel point log(f(n))sa valeur limite de est proche pour le grand . Comme revendiqué ci-dessus, chaque facteur de dans ajoute une décimale de précision limite. Examinons donc la décimale dans le logarithme du rapport de à , pour des puissances entières de de à :$-1/2$$n$$10$$n$$n^\text{th}$$f(n)$$e^{-1/2}$$10$$n=10^1$$n=10^{14}$

> round(sapply(1:14, function(n) 10^n * (log(f(10^n)) + 1/2)), 3)

[1] -0.255 -0.251 -0.250 ... -0.250 -0.249 -0.249 -0.400

(Sept valeurs ont été omises du milieu, toutes égales à -0.250.) Le motif constant est clair. À la fin, avec , il commence à se décomposer, indiquant une perte de précision. Améliorer cela nécessiterait probablement une arithmétique de haute précision.$n=10^{14}$

Pourquoi la méthode intuitive fonctionnerait-elle?

Considérez la table comme une collection de paires; c'est-à-dire qu'au lieu de la croix nord-ouest-est-sud traditionnelle d'une table de bridge, nous la regardons comme une table à deux rangées:

Nord Sud

Ouest Est

Si nous conditionnons que North soit le partenaire senior d'un couple, alors il y a 1 / 3ème chance que South soit le partenaire junior de ce couple, ce qui force alors West et East à être un couple, et 2 / 3ème chance que South sera un membre de l'autre couple, puis le dernier set n'est certainement pas un couple.

Lorsque nous étendons de à , nous ajoutons simplement une ligne au tableau:$n=2$$n=3$

Nord-ouest-sud-est

Nord Sud

Ouest Est

Si nous définissons Northwest comme étant toujours le partenaire principal du premier couple, il y a clairement une chance qu'il y ait un couple et nous pouvons nous arrêter, et une chance que il n'y a pas, et nous pouvons continuer, avec un problème plus petit .$\frac{1}{5}$$\frac{4}{5}$

Notez que le plus petit problème est différent , cependant, qui est «par coïncidence» le même. Au lieu d'avoir quatre personnes et deux couples dans le problème, nous devons avoir un couple et deux célibataires, et la chance que le couple soit jumelé est (pour les mêmes raisons qu'auparavant).$\frac{1}{3}$

Cela nous donne une approche récursive; nous pouvons parler d'un problème avec deux paramètres, , où réfère au nombre de personnes et réfère au nombre de couples. Donc nous donne (c'est-à-dire que quatre couples de 8 personnes nous donnent une chance d'échouer lors de l'attribution de la première paire, puis les chances d'échec pour 2 couples et 6 personnes dans le cas où nous survivons), puis pour nous devons étendre quatre cas:$(n,c)$$n$$c$$(8,4)$$\frac{6}{7}(6,2)$$\frac{1}{7}$$(6,2)$

1. Les deux couples suivants sont célibataires:$\frac{2*1}{6*5}(4,2)$

2. L'un était célibataire, l'autre était en couple:$\frac{4*2*2}{6*5}(4,1)$

3. Les deux étaient dans des couples différents: (Notez que , pour des raisons évidentes.)$\frac{4*2}{6*5}(4,0)$$(4,0)=1$

4. Les deux étaient dans le même couple: (Ceci est une condition de perte)$\frac{4*1}{6*5}$

Si vous passez à travers et faites tout le calcul, je pense que vous vous retrouvez avec pour le cas de 8 personnes, qui n'est pas . (Il est plus élevé en raison de la possibilité que nous rompions totalement les couples au début.)$\frac{20}{35}$ $\frac{6}{7}\frac{8}{15}$

Je ne connais pas d'astuce immédiate qui vous permette d'utiliser simplement une formule combinatoire pour obtenir une réponse sous forme fermée, mais il semble probable qu'il puisse y en avoir une. [modifier: Voir la réponse de whuber pour la solution.]