Número esperado de personas para no recibir un disparo?

Question

Supongamos $n$ gangsters están colocados aleatoriamente en una sala cuadrada tal que las posiciones de cualquiera de los tres mafiosos no forman un triángulo isósceles.

A la medianoche, cada gangster dispara con la persona más cercana a él. (Una persona puede recibir un disparo más de una vez, pero cada persona sólo puede disparar a una persona)

¿Cuántas personas se espera que para sobrevivir? (I. e. ¿cuál es el valor esperado del número de personas que no te disparen?)

E. g. Para una persona, el valor esperado es de 1. Para dos personas, es cero, ya que tanto recibir un disparo. Para los tres, el valor es 1, ya que forman los vértices de un triángulo escaleno. Estoy interesado en lo que sucede como $n \rightarrow \infty$.

Gracias por su ayuda!

Answer 1

Resumen:

El número esperado de sobrevivientes después de un tiroteo en $$\lim_{n\rightarrow\infty}\operatorname{E}[n]\aprox 0.284051\ n;\quad \text{(Tao/Wu - ver más abajo)}$$ es, si no es correcto, ciertamente muy cerca de ser correcta (consulte actualizar 2).

Sin embargo, este es disputada por Finch en constantes Matemáticas (de nuevo, ver más abajo para más detalles). Los resultados de Finch son fácilmente replicable en Mathematica o similares, pero yo no era capaz de reproducir incluso los resultados parciales en el Tao/Wu del papel (a pesar de dejar fuera de los valores absolutos de $\alpha$ y $\beta$ que Finch señala como incorrecta - ver abajo para más detalles), me dejó dudas en cuanto a si me falta algo en mi "traducción" del problema a Finch más la notación moderna. Yo debería estar muy agradecido si alguien me podría iluminar aún más en este asunto.

Original respuesta:

Basado en tests numéricos, yo diría que el número esperado de sobrevivientes para $n>3 \aprox n/3.5$

Prueba ejemplo test[20] (código de abajo):

anim[20,8]:

Para $1000$ ensayos, $1\leq n\leq 40$ est[40,10^3]:

Nota

El uso de RandomReal es muy poco probable que cualquiera de las dos distancias será exactamente igual, cumpliendo así con el no triángulo isósceles requisito.

Actualización 1

Historia del problema

Robert Abilock propuesto en América Mensual El Rifle-Problema (R. Abilock; 1967),

$n$ fusileros son distribuidos al azar los puntos de un plano. A una señal, cada uno dispara y mata a su vecino más cercano. Lo que se espera que número de fusileros que quedan vivos?

Este fue depositada como el Vicioso vecino problema (R. Tao y F. Y. Wu; 1986), donde la respuesta de $\aprox 0.284051 n$ restantes fusileros (o $\aprox n/3.52049$) fue presentado como la solución en $2$ dimensiones.

Esto concuerda claramente con las pruebas de la muestra el tamaño de $10^5:$

ListLinePlot[{const[#, 100000] & /@ Range@40}, GridLines -> {{}, {1/0.284051}}]

Sin embargo, en Constantes Matemáticas vecino más Cercano de gráficos (S. R. Pinzón; 2008), el Pinzón de los estados que

En [Vicioso vecino problema], el valor absoluto de los signos en las definiciones de $\varphi$ y $\psi$ erróneamente se han omitido.)$\puntos$

Dada la discrepancia entre nuestro estimado de $\dots$ y su estimado de $\dots$, parece dudoso que su aproximación $\beta(2) = 0.284051\dots$ es del todo correcto.

Así que la pregunta (la recompensa) se reduce a:

Tiene los progresos realizados desde el 2008 en el problema? En definitiva, es el Tao y Wu cálculo incorrecto, y si es así, es una estimación más precisa de $\beta(2)$ conocido?

Actualización 2

También he probado el problema en otros polígonos regulares (círculo, triángulo, pentágono, etc.) por $10^5$ ensayos, $1\leq n \leq 30$, y parece que el comentario de @D. Thomine a continuación está de acuerdo con los datos recopilados, en el que la constante para cualquier delimitada $2$ tridimensional de la región parece ser la misma para lo suficientemente grande como $n,$ es decir, independiente de la geometría global del dominio:

mientras más simulaciones, usando $2\cdot 10^6$ ensayos para $n=$ 30 y $n=100$ arrojó los siguientes resultados:

con el promedio final después de $2\cdot 10^6,$ en comparación con Tao/Wu resultado, siendo:

\begin{align} &n=30:&0.284090\dots\\ &n=100:&0.284066\dots\\ &\text{Tao/Wu:}&0.284051\dots\\ \end{align}

lo que indica que el Tao/Wu resultado de $\lim_{n\rightarrow\infty}\operatorname{E}[n]\aprox 0.284051\ n$ es, si no es correcto, ciertamente muy cerca de ser la correcta.

Los límites superior e inferior

Siguiendo @mathreadler la sugerencia de que puede ser interesante para el estudio de la propagación de datos, que incluyen la siguiente como una menor aportación al tema:

Desde que acuerdos como este

son posibles (y sus circular contrapartes, sin embargo poco probable a través de punto aleatorio de selección), claramente el límite inferior de impar $n$ es $1$ y $n$ es $0$ (ya que los puntos pueden ser emparejados).

Encontrar un límite superior es menos evidente, sin embargo. Mirando este sketch de prueba para el límite superior $n=10$ proporcionada por @JohnSmith en los comentarios, es fácil ver que el límite superior es de $7:$

y empleando el mismo método, límites superiores para mayores de $n$ puede ser construido:

Suponiendo que uno puede repetir este proceso indefinidamente, es probable que una cota superior para $n\geq 6$ es $n-\lfloor n/3\rfloor:$

que se ha establecido en contra de los datos por $2\cdot 10^4$ ensayos (puntos rojos - ver data por debajo).

Respecto a la densidad de propagación, (de nuevo con $2\cdot 10^4$ ensayos), se produce el siguiente diagrama:

ListPlot3D[Flatten[data, 1], ColorFunction -> "LakeColors"]

(cortesía de @AlexeiBoulbitch aquí), y con respecto a max. densidad de propagación a lo largo de $x/z$ ejes de arriba de la parcela, se produce el siguiente:

With[{c = 0.284051}, 
Show[ListLinePlot[Max@#[[All, 3]] & /@ data, PlotRange -> All], 
Plot[{(1 + c)/(n - (1 + c)^2)^(1/2)}, {n, 0, 100}, PlotRange -> All,
PlotStyle -> {Dashed, Red}]]]

Es tentador conjeturar altura max de distribución será de $\aprox (c+1)/\sqrt{n-(c+1)^2},$ pero por supuesto esto es en gran parte empírico.

---

test[nn_] := With[{aa = Partition[RandomReal[{0, 1}, 2 nn], 2]},
With[{cc = ({aa[[#]], First@Nearest[DeleteCases[aa, aa[[#]]], aa[[#]]]} 
& /@ Range@nn)}, 
With[{dd = Table[Position[aa, cc[[p, 2]]][[1, 1]], {p, nn}]}, 
With[{ee = Complement[Range@nn, dd]},
Column[{StringJoin[ToString["Expected: "], ToString[nn/3.5]], 
StringJoin[ToString["Survivors: "], ToString[Length@ee], ToString[": "], 
ToString[ee]], Show[Graphics[{Gray, Line@# & /@ cc}, Frame -> True, 
PlotRange -> {{0, 1}, {0, 1}}, Epilog -> {Text[Style[(Range@nn)[[#]], 
30/Floor@Log@nn], aa[[#]]] & /@ Range@nn}], ImageSize -> 300]}]]]]]

est[mm_, trials_] := ListLinePlot@({Quiet@With[{nn = #}, 
(N@Total@(With[{aa = Partition[RandomReal[{0, 1}, 2 nn], 2]},
With[{cc = ({aa[[#]], First@Nearest[DeleteCases[aa, aa[[#]]], 
aa[[#]]]} & /@ Range@nn)},
With[{dd = Table[Position[aa, cc[[p, 2]]][[1, 1]], {p, nn}]}, 
With[{ee = Complement[Range@nn, dd]},Length@ee]]]] 
& /@ Range@trials)/trials)] & /@ Range@mm, Range@mm/3.5})

anim[nn_, range_] := ListAnimate[test@nn & /@ Range@range,  
ControlPlacement -> Top, DefaultDuration -> nn]

const[mm_, trials_] := With[{ans = Quiet@With[{nn = #}, 
SetPrecision[(Total@(With[{aa = Partition[RandomReal[{0, 1}, 2 nn], 2]},
With[{cc = ({aa[[#]],First@Nearest[DeleteCases[aa, aa[[#]]], 
aa[[#]]]} & /@ Range@nn)}, 
With[{dd = Table[Position[aa, cc[[p, 2]]][[1, 1]], {p, nn}]},
With[{ee = Complement[Range@nn, dd]},
Length@ee]]]] & /@ Range@trials)/trials), 20]] &@ mm}, mm/ans]

act[nn_, trials_] := With[{aa = Partition[RandomReal[{0, 1}, 2 nn], 2]},
With[{cc = ({aa[[#]], First@Nearest[DeleteCases[aa, aa[[#]]], aa[[#]]]} & /@ 
Range@nn)}, With[{dd = Table[Position[aa, cc[[p, 2]]][[1, 1]], {p, nn}]}, 
With[{ee = Complement[Range@nn, dd]}, Length@ee]]]] & /@ Range@trials

data = Quiet@ Table[With[{tt = 2*10^4}, 
With[{aa = act[nn, tt]}, With[{bb = Sort@DeleteDuplicates@aa}, 
Transpose@{ConstantArray[nn, Length@bb], bb, (Length@# & /@ 
Split@Sort@aa)/tt}]]], {nn, 1, 100}];

Answer 2

${\bf Actualización~Oct~19}$: Añadido algunos análisis sobre los $D\to\infty$ límite de $\frac{E[n]}{n}$ para el juego original y el modificado ligeramente caso de que la geometría es la de un toro.

---

Martin ha hecho un gran trabajo en la exploración del problema y como se menciona en su respuesta, parece que hay un cierto desacuerdo en la literatura sobre el valor exacto de $\lim\limits_{n\to\infty}\frac{E[n]}{n}$, donde $\frac{E[n]}{n}$ es la fracción de los sobrevivientes en un juego con $n$ los jugadores. Voy a tratar aquí de fijar este límite de $4-5$ decimales para los primeros valores de $D$ - la dimensión, el juego se juega en.

---

Algoritmo numérico

El bootleneck en el cálculo numérico es encontrar el vecino más cercano de cualquier jugador. Una búsqueda por fuerza bruta como las escalas de $O(n^2D)$, que en una sola CPU se convierte en forma lenta para $n\gtrsim 10^2-10^3$. Para mejorar en este he añadido un uniforme de cuadrícula con $M^D$ gridcells cubriendo $[0,1]^D$ a de la simulación. $M$ es elegido tal que $n_{\rm por~celda} = n/M^D \sim $ unos pocos. Los jugadores se añadió a las células y cuando buscamos normalmente sólo tendrá que ir a través de la vecina $3^D$ las células para encontrar el vecino más cercano para cualquier jugador. Esto hace que el número de operaciones a $O(nD3^D)$ lo que nos permite ir mucho más de $n$ que con la búsqueda de fuerza bruta. El código que he usado para hacer esto, escrito en c++, se puede encontrar aquí. El código sólo es adecuado para explorar valores relativamente bajos de $D \lesssim 5$ como la cuadrícula sea necesario para acelerar el cálculo se vuelve demasiado la memoria caro para grandes $D$ (más el algoritmo de escalas exponencialmente con $D$).

---

Resultados

En la siguiente figura se puede ver el acumulativo promedio de $\frac{E[n]}{n}$ como función del número de muestras por $\{D=1,~n=10^3\}$ (izquierda) y $\{D=2,~n=10^4\}$ (a la derecha).

En la figura a continuación se muestran la evolución de $\frac{E[n]}{n}$ en función de $n$ para diferentes valores de $D$. Por cada $n$ I realizado $$ N muestras (que varía de $10^2-10^8$ en función de $D$ y $n$) hasta la precisión deseada se alcanza. Las barras de error de muestra de 3 $\hat{\sigma}$ ($99.7\%$ de confianza) de que el error estándar de $\hat{\sigma} = \frac{\sigma}{\sqrt{N}}$, donde $\sigma^2 = \frac{1}{N}\sum_{i=1}^N(f_i-\overline{f})^2$ y $f_i$ es la fracción de los sobrevivientes en una sola carrera y $\overline{f} = \frac{1}{N}\sum_{i=1}^Nf_i$ es el acumulativo decir. Para ser capaz de mostrar todo en una parcela que he restado $f$ (el valor dado en la tabla de abajo).

$~~~~~~~~$

Esto me da el siguiente resultado:

\begin{array}{c|c} D & f=\lim\limits_{n\to\infty}\frac{E[n]}{n} \\ \hline 1 & 0.25000 \pm 10^{-5} \\ \hline 2 & 0.28418 \pm 10^{-5}\\ \hline 3 & 0.30369 \pm 10^{-5}\\ \hline 4 & 0.3170 \pm 10^{-4}\\ \end{array}

El citado error es el $99.7$% de confianza estadístico de error, además de que el error estimado en la evolución con $n$ (sólo relevante para $D=4$ como hemos convergencia dentro del error estadístico por menor $D$). Tenga en cuenta que por $D=1$ tenemos el resultado analítico $f=\frac{1}{4} = 0.25$, que sirve como una prueba de nuestro análisis numérico.

La gran $D$ limit

También hice algunas simulaciones para valores bajos de $n\lesssim 10^3$ examinando la evolución de los $\frac{E[n]}{n}$ con $D$ - la dimensión, el juego se juega en. Para estos cálculos se me acaba de utilizar una bruta obligó a los vecinos a encontrar el algoritmo.

Me considera una caja cerrada y una caja con periódicos de las condiciones de contorno (es decir, $x_i=0$ es el punto de $x_i=1$). La última situación es equivalente a hacer el juego en un toro. Los resultados pueden verse a continuación

$~~~~~~~~~~~~~~$

Para valores bajos de $D$ los resultados entre las dos geometrías son bastante similares, pero empezamos a ver algunos grandes diferencias para valores grandes de $D$ (e $n$). La razón de la frontera efectos se vuelve más y más importante para las grandes $D$ puede entenderse teniendo en cuenta una esfera en el centro de nuestra caja (con un radio de $1/2$). Como aumentar $D$ nos encontramos con que el volumen de la esfera en el volumen total de la caja va a cero, por lo que (a grandes rasgos) la mayor parte del volumen de la caja es en las esquinas. Un jugador en una esquina con menos probabilidades de recibir un disparo de una persona cercana al centro de lo común sitation para grandes $D$ es que tenemos muchos jugadores en diferentes rincones de disparo de los jugadores cerca del centro que nos da un alto porcentaje de supervivencia.

Para el toro de la geometría de una persona en la esquina es la misma probabilidad de recibir un disparo como nadie, y si $a$ es $B$'s vecino más cercano que $B$ es $Un$'s vecino más cercano con probabillity $1/2$ como $D\to\infty$ (véase esta cuestión) lo que implica que $$\lim\limits_{D\to\infty}\frac{E[n]}{n} \a \left(1-\frac{1}{n}\right)^{n-1}$$ que converge a $\frac{1}{e}$ para $n\to\infty$.

Answer 3

Aquí está una simulación en la Octava. "Modelo" es el modelo lineal $\frac{2}{7}$ n que martin mostró anteriormente. Tal vez sería interesante investigar la propagación y cómo cambia con $n$?

Incluso si el valor de la media de sobrevivir gangstas está bastante cerca de $\frac{2}{7}$ n como martin descubrió en su respuesta, también podemos ver que hay un muy amplio margen de gangsta muertes. Una propagación de la que parece aumentar con el aumento del número de gangstas.

Octava código:

N_lst = 1:45;

s_lst = 1:25;

data_table_ = zeros(numel(N_lst),numel(s_lst));

para i_N = 1:numel(N_lst);

para i_s = s_lst;

N_ = N_lst(i_N);

d_x = rand(N_,1)';

d_y = rand(N_,1)';

D = abs((vec(d_x)'-vec(d_x)) + 1i*(vec(d_y)'-vec(d_y))) + ojo(N_)*2;

[v,i] = min(D,[],1);

data_table_(i_N,i_s) = numel(única([i(1,:)]));

endfor

endfor