¿Qué tan probable es que no seas el mejor amigo de nadie?

Question

Un conocido adolescente mío lamentó:

Cada uno de mis amigos es mejor amigo de otra persona.

Gracias a mi conocimiento de matemáticas pude informarle que no está sola y $e^{-1}\approx 37\%$ de todas las personas podrían encontrarse en la misma situación, lo cual seguramente la alegró inmensamente.

Este número asume que las amistades se distribuyen al azar, de modo que cada persona en una población de $n$ elige un mejor amigo al azar. Entonces, la probabilidad de que cualquier persona dada no sea el mejor amigo de nadie es $(1-\frac{1}{n-1})^{n-1}$, lo cual tiende a $e^{-1}$ para grandes $n$.

Después no estoy seguro de que esta sea realmente la mejor manera de analizar la afirmación. Tal vez en lugar de eso deberíamos imaginar asignar una "fortaleza de amistad" aleatoria a cada arista en el grafo completo en $n$ vértices, en cuyo caso el lamento de mi amiga sería "cada vértice al que estoy conectado tiene una arista con un peso mayor que mi arista hacia él". Esto no es lo mismo que "todos eligen un mejor amigo al azar", porque garantiza que existe al menos un par de personas que son mutuamente mejores amigos, a saber, los extremos de la arista con el mayor peso.

(Por supuesto, algunas personas no son amigos en absoluto; podemos manejar eso asignando bajos pesos a sus aristas mutuas. Siempre y cuando todos tengan al menos un amigo real, esto no cambiará quiénes son los mejores amigos de quién).

(No importa qué distribución se elijan los pesos de amistad, siempre y cuando sea continua, porque lo único que importa es el orden relativo entre los pesos. De manera equivalente, uno puede simplemente elegir un orden total aleatorio en las $n(n-1)/2$ aristas en el grafo completo).

En este modelo, ¿cuál es la probabilidad de que una persona dada no sea el mejor amigo de nadie?

Por linealidad de las expectativas, la probabilidad de ser mutuamente mejor amigo de alguien es $\frac{n-1}{2n-3}\approx\frac 12$ (mucho mejor que en el modelo anterior), pero eso no tiene en cuenta la posibilidad de que algún pobre alma me tenga a mí como su mejor amigo mientras que yo tengo otros amigos mejores. La linealidad de la expectativa no parece ayudar aquí: me dice que el número esperado de personas cuyo mejor amigo soy es $1$, pero no la probabilidad de que este número sea $0.

---

(Edición: Varios párrafos de resultados numéricos ahora se trasladan a una respuesta significativamente ampliada)

Answer 1

La probabilidad de que un gran $n$ $e^{-1}$ en la amistad-la fuerza del modelo. Ni siquiera puedo empezar a explicar por qué es, pero tengo una fuerte evidencia numérica. Más precisamente, si $p(n)$ es la probabilidad de que alguien, en una población de $n$ no es de nadie, mejor amigo, luego se ve fuertemente como

$$ p(n) = \Bigl(1-\frac{1}{2n-7/3}\Bigr)^{2n-7/3} + O(n^{-3})$$ como $n$ tiende a infinito.

El factor de $2$ puede ser un indicio en algunos asintótica de conexión entre los dos modelos, pero tiene que ser sutil, porque el mejor amigo de la relación, sin duda, no parece el mismo en los dos modelos: como se señaló en la pregunta, en la amistad-la fuerza del modelo hemos de esperar que la mitad de todas las personas a ser mutuamente mejores amigos con alguien, mientras que en el modelo en el que cada uno elige su mejor amigo de forma independiente, el total de número esperado de amistad mutua es sólo $\frac12$.

El desplazamiento de $7/3$ se encontró experimentalmente, pero hay buena evidencia de que es exacta. Si es que significa algo, es un misterio para mí qué.

Cómo calcular la probabilidad. Considere el grafo completo en $n$ vértices, y asignar al azar amistad pesos a cada borde. Imaginar el procesamiento de los bordes en la orden de la amistad más fuerte hacia el más débil. Para cada vértice/persona, la primera vez que vemos un borde final no va a decirle a esa persona que su mejor amigo es.

Los gráficos construimos puede llegar a ser muy complejo, pero para los propósitos de la cuenta sólo tenemos que distinguir tres tipos de nodos:

• W - a la Espera de las personas que aún no conocen a ninguno de sus amigos. (Es decir, los vértices que no son un punto final de cualquier borde procesado todavía).
• F - Amigos, la gente que son amigos con alguien, pero no son de nadie, mejor amigo todavía. Quizás una de las personas que Esperan que va a tener como su mejor amigo.
• B - los Mejores amigos, que saben que tienen a alguien mejor amigo.

En cada paso en el procesamiento de la gráfica, que puede ser descrito como una triple $(w,f,b)$ indicando el número de cada tipo de nodo. Tenemos $w+f+b=n$, y el estado inicial es $(n,0,0)$ con todo el mundo sigue esperando.

• Si vemos a un WW borde, dos personas que esperan reforzarse mejores amigos, y nos movemos hacia el estado de $(w-2,f,b+2)$. Hay $w(w-1)/2$ dichos bordes.
• Si vemos un WF borde, el F nodo es ahora alguien mejor amigo y se convierte en B, y la W nodo se convierte en F. El efecto neto es que nos mueven a estado $(w-1,f,b+1)$. Hay $wf$ dichos bordes.
• Si vemos un WB borde, tne W nodo se convierte en F, pero la B queda un B -- no nos importa cómo muchas personas mejores amigos, uno es, siempre hay alguien. Nos movemos a $(w-1,f+1,b)$, y $wb$ bordes de este tipo.
• Si vemos un FF o FB o BB borde, representa una amistad donde tanto a personas que ya tienen mejores amigos, por lo que el estado no cambia.

Por lo tanto, para cada estado, el siguiente WW o WF o WB borde vemos determinar en qué estado nos movemos, y desde todos los bordes son igualmente probables, la probabilidad de pasar a los diferentes estados sucesores se $\frac{w-1}{2n-w-1}$$\frac{2f}{2n-w-1}$$\frac{2b}{2n-w-1}$, respectivamente.

Desde $w$ disminuye en cada movimiento entre los estados, podemos llenar una tabla de las probabilidades de que cada estado se han visitado alguna vez, simplemente, considerando todos los posibles estados en orden decreciente de $w$. Cuando todos los bordes se han visto estamos en un estado $(0,f,n-f)$, y sumando sobre todos estos podemos encontrar la esperada $f$ para un peso aleatorio de asignación.

Por la linealidad de la espera, la probabilidad de que un determinado nodo es F al final debe entonces ser $\langle f\rangle/n$.

Desde allí se $O(n^2)$ estados con $w+f+b=n$ y una cantidad constante de trabajo para cada estado, este algoritmo se ejecuta en el tiempo $O(n^2)$.

Los resultados numéricos. Aquí están los resultados exactos para $n$ hasta las 18:

 n approx                 exact
--------------------------------------------------
 1  100%                   1/1
 2  0.00%                  0/1
 3 33.33%                  1/3
 4 33.33%                  1/3
 5 34.29%                 12/35
 6 34.81%                 47/135
 7 35.16%                731/2079
 8 35.40%               1772/5005
 9 35.58%              20609/57915
10 35.72%            1119109/3132675
11 35.83%             511144/1426425
12 35.92%           75988111/211527855
13 36.00%         1478400533/4106936925
14 36.06%        63352450072/175685635125
15 36.11%      5929774129117/16419849744375
16 36.16%     18809879890171/52019187845625
17 36.20%    514568399840884/1421472473796375
18 36.24% 120770557736740451/333297887934886875

Después de este punto, exacta racional de la aritmética con 64 bits denominadores empezar a rebosar. Se vería $p(n)$ tiende a $e^{-1}$. (Por otro lado, la secuencia de los numeradores y denominadores son desconocidos para OEIS).

Para obtener más, cambié de máquina nativo de punto flotante (Intel 80 bits) y consiguió el $p(n)$ columna de esta tabla:

   n     p(n)    A      B      C      D      E      F      G      H
---------------------------------------------------------------------
   10 .3572375 1.97+  4.65-  4.65-  4.65-  2.84+  3.74+  3.64+  4.82-
   20 .3629434 2.31+  5.68-  5.68-  5.68-  3.47+  4.67+  4.28+  5.87-
   40 .3654985 2.62+  6.65-  6.64-  6.64-  4.09+  5.59+  4.90+  6.84-
   80 .3667097 2.93+  7.59-  7.57-  7.57-  4.70+  6.49+  5.51+  7.77-
  100 .3669469 3.03+  7.89-  7.87-  7.86-  4.89+  6.79+  5.71+  8.07-
  200 .3674164 3.33+  8.83-  8.79-  8.77-  5.50+  7.69+  6.32+  8.99-
  400 .3676487 3.64+  9.79-  9.69-  9.65-  6.10+  8.60+  6.92+  9.90-
  800 .3677642 3.94+ 10.81- 10.60- 10.52-  6.70+  9.50+  7.52+ 10.80-
 1000 .3677873 4.04+ 11.17- 10.89- 10.80-  6.90+  9.79+  7.72+ 11.10-
 2000 .3678334 4.34+ 13.18- 11.80- 11.63-  7.50+ 10.69+  8.32+ 12.00-
 4000 .3678564 4.64+ 12.74+ 12.70- 12.41-  8.10+ 11.60+  8.92+ 12.90-
 8000 .3678679 4.94+ 13.15+ 13.60- 13.14-  8.70+ 12.50+  9.52+ 13.81-
10000 .3678702 5.04+ 13.31+ 13.89- 13.36-  8.90+ 12.79+  9.72+ 14.10-
20000 .3678748 5.34+ 13.86+ 14.80- 14.03-  9.50+ 13.69+ 10.32+ 15.00-
40000 .3678771 5.64+ 14.44+ 15.70- 14.67- 10.10+ 14.60+ 10.92+ 15.91-

Los otros 8 columnas a mostrar lo bien $p(n)$ coincide con varios intentos de modelo. En cada columna muestro $-\log_{10}|p(n)-f_i(n)|$ para algunos la función de prueba de $f_i$ (es decir, cuántos dígitos de acuerdo hay entre el$p(n)$$f_i(n)$), y el signo de la diferencia entre el$p$$f_i$.

• $f_{\tt A}(n)=e^{-1}$

En la primera columna se compara a la constante $e^{-1}$. Es principalmente como evidencia de que $p(n)\to e^{-1}$. Más precisamente, se parece a $p(n) = e^{-1} + O(n^{-1})$ -- siempre que $n$ recibe 10 veces más grande, otro de los dígitos de $e^{-1}$ es producido.

• $f_{\tt C}(n)=\Bigl(1-\frac{1}{2n-7/3}\Bigr)^{2n-7.3}$

Me encontré con esta función mediante la comparación de $p(n)$ $(1-\frac{1}{n-1})^{n-1}$(la probabilidad de que el elegido-mejores-amigos-independientemente del modelo) y darse cuenta de que casi iguala entre $n$$2n$. El desplazamiento de $7/3$ fue encontrado por ensayo y error. Con este valor se parece a $f_{\tt C}(n)$ aproxima $p(n)$ a $O(n^{-3})$, dado que la $n$ 10 veces más grande da tres dígitos adicionales de acuerdo.

• $ f_{\tt B}=\Bigl(1-\frac{1}{2n-2.332}\Bigr)^{2n-2.332}$ $f_{\tt D}=\Bigl(1-\frac{1}{2n-2.334}\Bigr)^{2n-2.334} $

Estas columnas proporcionan evidencia de que la $7/3$ $f_{\tt C}$ es probable para ser exactos, ya que varían sólo ligeramente en cada dirección da claramente peor aproximación a $p(n)$. Estas columnas no llegan a alcanzar más de tres dígitos de precisión para cada década de $n$.

• $ f_{\tt E}(n)=e^{-1}\bigl(1-\frac14 n^{-1}\bigr)$ $f_{\tt F}(n)=e^{-1}\bigl(1-\frac14 n^{-1} - \frac{11}{32} n^{-2}\bigr)$

Dos y tres términos de la expansión asintótica de $f_{\tt C}$ en $n$. $f_{\tt F}$ también mejora la cubically, pero con un mucho mayor error de $f_{\tt C}$. Esto parece indicar que la estructura específica de $f_{\tt C}$ es importante para el ajuste, en lugar de sólo los primeros términos en su expansión.

• $ f_{\tt G}(n)=e^{-1}\bigl(1-\frac12 (2n-7/3)^{-1}\bigr)$ $f_{\tt H}(n)=e^{-1}\bigl(1-\frac12 (2n-7/3)^{-1}-\frac{5}{24} (2n-7/3)^{-2}\bigr) $

He aquí una sorpresa! La expansión de $f_{\tt C}$ en potencias de $2n-7/3$ en lugar de potencias de $n$ no sólo da mejores aproximaciones de $f_{\tt E}$$f_{\tt F}$, pero también se aproxima a $p(n)$ mejor que el $f_{\tt C}$ sí no, por un factor de alrededor de $10^{0.2}\approx 1.6$. Esto parece ser aún más misterioso que el hecho de que $f_{\tt C}$ partidos.

En $n=40000$ el cálculo de $p(n)$ toma alrededor de un minuto, y las comparaciones de comenzar a empujar el límite de equipo de punto flotante. El 15-16 dígitos de precisión en algunas de las columnas son apenas representable en doble precisión. Curiosamente, el cálculo de $p(n)$ sí parece ser bastante robusto en comparación con las aproximaciones.

Answer 2

Aquí hay otra forma de abordar este interesante problema. Considere un grupo de $n+1$ personas $x_0,\dots,x_n$ con $x_0$ siendo yo mismo. Defina la probabilidad $$ P_{n+1}(i)=P(\textrm{cada uno de $x_1,\dots,x_i$ me tiene como su mejor amigo}). $$ Entonces podemos calcular la probabilidad deseada usando la fórmula de inclusión-exclusión de la siguiente manera: \begin{eqnarray} P_{n+1} &=& P(\textrm{No soy el mejor amigo de nadie}) \\ &=& 1-P(\textrm{Soy el mejor amigo de alguien}) \\ &=& \sum_{i=0}^n (-1)^i\binom{n}{i}P_{n+1}(i). \tag{$*$} \end{eqnarray>

Para calcular $P_{n+1}(i)$, note que para que se cumpla la condición, es necesario que de todas las amistades entre uno de $x_1,\dots,x_i$ y cualquier persona, la que tiene el mayor peso sea una amistad conmigo. La probabilidad de que eso sea cierto es $$ \frac{i}{in-i(i-1)/2}=\frac{2}{2n-i+1}. $$ Suponga, entonces, que eso es cierto y que esta amistad sea $(x_0, x_i)$. Entonces, yo soy ciertamente el mejor amigo de $x_i$. La probabilidad de que también sea el mejor amigo de cada uno de $x_1,\dots,x_{i-1}$ no cambia. Por lo tanto, podemos repetir el argumento y obtener $$ P_{n+1}(i) =\frac{2}{2n}\cdot\frac{2}{2n-1}\cdots\frac{2}{2n-i+1} =\frac{2^i(2n-i)!}{(2n)!}. $$ Sustituyendo esto en $(*)$ obtenemos una fórmula para $P_{n+1}$ que coincide con los resultados de Henning.

Para demostrar que $P_{n+1}\to e^{-1}$ cuando $n\to\infty$, use que el $i$-ésimo término de $(*)$ converge a, pero es numéricamente menor que, el $i$-ésimo término de $$ e^{-1}=\sum_{i=0}^\infty\frac{(-1)^i}{i!}. $$

Por cierto, en el modelo alternativo donde cada persona elige un mejor amigo al azar, en lugar de eso tendríamos $P_{n+1}(i)=1/n^i$ y $P_{n+1}=(1-1/n)^n$.

Answer 3

Esta respuesta es bastante similar a la respuesta de Lancel, pero creo que aborda con éxito el sutil problema de la dependencia entre amistades (si soy el mejor amigo de $x_1$, entonces es un poco más probable que también sea el mejor amigo de $x_2$, porque ser el mejor amigo de $x_1 sugiere que la fuerza de la amistad entre $x_1$ y $x_2$ es "baja", lo que hace más probable que mi fuerza hacia $x_2$ supere todas las demás fuerzas de amistad para $x_2). Esta respuesta también evita la necesidad de preocuparse por la convergencia de la serie de potencias.

Usamos Brun's Sieve, que es esencialmente una reorganización del método de inclusión-exclusión. Supongamos que hay $n$ personas además de mí en el grafo, y sean $x_1, \ldots, x_r$ cualquier conjunto de $r$ personas. Sea $B_i$ el evento de que soy el mejor amigo de la persona $i$. Necesitamos mostrar que, para cada $r$ fijo, a medida que $n \to \infty$ tenemos ${n \choose r}P(B_1 \wedge \cdots \wedge B_r) \to \frac{1}{r!}$. Para hacer esto, mostraremos que $P(B_1 \wedge \cdots \wedge B_r) \to \frac{1}{n^r}$.

Ahora $P(B_1) = 1/n$: de las $n$ personas que ve $x_1$, debo tener la mayor fuerza. Para $i$ más alto necesitamos obtener probabilidades condicionales, y solo obtenemos estimaciones superiores e inferiores, pero estas estimaciones se aproximarán asintóticamente entre sí a medida que $n \to \infty$. Para $P(B_2 | B_1)$, tenemos el límite inferior $P(B_2 | B_1) \geq P(B_2) \geq 1/n$, ya que la condición en $B_1$ solo "reduce" el valor de la arista $x_1x_2$ (es un poco más fácil ver esto al invertir la situación: si consideramos controlar el valor de $x_1x_2$ y elegir aleatoriamente todos los demás pesos de las aristas, la probabilidad de $B_1$ y la probabilidad de $B_2$ disminuyen a medida que el peso de $x_1x_2$ aumenta). Por otro lado, $P(B_2 | B_1) \leq 1/(n-1)$, ya que mi peso hacia $x_2$ debe superar cada uno de los pesos de $x_2$ hacia vértices que no son $x_1$, y la condición en $B_1$ no brinda información sobre esos pesos.

Continuando de esta manera, vemos que $1/n \leq P(B_i | B_1, \ldots, B_{i-1}) \leq 1/(n-i+1)$ para cada $i$. Cuando $r$ está fijo y $n \to \infty$, esto produce $P(B_i | B_1, \ldots, b_{i-1}) \to 1/n$, de modo que $P(B_1 \wedge \cdots \wedge B_r) \to 1/n^r

.

Así, por el Cernido de Brun, tenemos que $P\left(\bigwedge\overline{B_i}\right) \to e^{-1}$, y, además, el número de personas cuyo mejor amigo eres es (asintóticamente) distribuido de manera Poisson con media $1$.