Cuántos jugadores necesarios para que el juego tiene la más alta probabilidad de acabado de la forma más rápida?

Question

Bienvenidos a la ficción juego de color "etiqueta"; la no tan rápido ritmo de primo de paintball, Donde marca su oponente es todo lo que cuenta!

Si $A$ puntos $B$ con su color, a continuación, $B$ va a estar permanentemente marcado con $A$'s de color, pero, al mismo tiempo que todas las demás personas marcadas con $B$'s de color al instante de estar permanentemente marcado con $A$'s como el color.

El primero que han marcado todo el mundo gana, y el juego ha terminado!

$m<x$ donde $m = 16$, y el número de jugadores, $x$, se coloca en una habitación y la asignación de un único color.

Con cada hora que el progreso, todos los jugadores tienen una probabilidad de $1 - \frac{m}{x}$ de éxito a la marca de otro jugador. No hay un límite para la cantidad de veces que un jugador marca otro jugador.

En el caso de que $A$ marcas de otro jugador, el jugador, que está siendo marcada, $B$, es elegido al azar; a Pesar de que los jugadores no pueden diferenciarse.

Ahora, me gustaría saber cuál es el número óptimo de los jugadores para el juego que tiene la mayor probabilidad de ser el más rápido.

Es decir, cuantos jugadores se necesitan para que el juego tiene la más alta probabilidad de acabado de la forma más rápida?

Suena bastante simple, ¿verdad?

Resulta que suena más sencillo de lo que es; Al menos en mis oídos.

He intentado deformar todo esto en mi cabeza, pero no he podido encontrar un enfoque viable.

Empecé por el cálculo de $(1 - \frac{16}{32} * \frac{1}{32})^{32}$, pensando que $(1 - \frac{m}{x} * \frac{1}{x})^x$ era la manera de ir sobre el cálculo de la forma más rápida posible juego con respecto al número de jugadores. Pronto me di cuenta de que no había manera de que me iba a dar nada a cerca de los resultados correctos, por lo que Se me ocurrió algo a lo largo de las líneas de $\sum_{n=0}^{x-1} ((1 - \frac{m}{x}) * \frac{x-n}{x})^n$, lo que yo esperaba que me llevaría a algún lugar; Pero todo lo que hice fue darme de comer un absurdamente pequeño número y hacer que me de cuenta de que nunca he tenido que hacer frente a un problema como este, y que no tengo idea de cómo resolverlo.

Ahora, yo no estoy aún teniendo en cuenta que debo encontrar los casos con las más altas probabilidades de éxito, a continuación, cruzar comprobar que es él más rápido; Lo que sí creo es de suma importancia en este problema, por desgracia no conozco ninguna manera de acercarse a este.

Cualquier entrada (especialmente etiqueta adiciones) es muy apreciado!

---

EDIT 1:

Sólo para asegurarse de que no hay confusión: Si un jugador $A$ y otro jugador $B$ tanto en llegar a la marca de un rival (los opositores siendo todos los otros jugadores) dentro de una hora, entonces hay una oportunidad, y es que permitió que ese $A$ puntos $B$, e $B$ puntos $A$.

Marca otro jugador realiza de forma instantánea y simultánea.

Answer 1

En definitiva, se desea minimizar los jugadores en el juego para esperar el juego para terminar tan pronto como sea posible. Podríamos interpretar la pregunta original literalmente - " Ahora, me gustaría saber cuál es el número óptimo de los jugadores para el juego que tiene la mayor probabilidad de ser el más rápido, entonces estamos buscando simplemente el número de jugadores para terminar el juego en el menor número de pasos posible. El menor tiempo posible, un juego podría durar sólo sube a medida que más jugadores se agregan al juego, ya que requiere más pasos para un jugador de color que se extendió a todos los jugadores en el juego.

Si en el otro no estamos tratando de ser la gramática de la policía, entonces estamos tratando de minimizar el tiempo de espera necesario para terminar el juego. Representa el problema matemáticamente, es muy difícil: tiene un dinámico proceso de Markov en el que el estado de cada jugador el color influye en todos los estados futuros del juego. No he sido capaz de encontrar ninguna de las distribuciones de probabilidad de que el ajuste del juego; el más cercano que he podido encontrar es la de Dirichlet-multinomial.

La respuesta que se desea minimizar el número de jugadores en el juego para minimizar el tiempo de espera para terminar. Con x los jugadores en el juego, cualquier jugador necesita para difundir su color a x-1 separar a los jugadores. Para que un jugador gane el juego, cada jugador necesita para ser golpeado. Como el número de jugadores en el juego aumenta, las posibilidades de que un jugador es golpeado en una ronda dada disminuye a medida que x aumenta. Con dos jugadores en el juego, la probabilidad de que un jugador ha de ser golpeado es de 1 $\frac{m}{x}$. A medida que aumenta x, esta probabilidad converge a $\frac{e-1}{e}$ o 0,63 para cada jugador (concedido soy sospechosa de 'm' falta del resultado. También, se asemeja a los sombrero de verificación problema).

Y para algunos más matemáticas:

La probabilidad de que un jugador no golpea en una hora dada es $\frac{m}{x}$.

Vamos a d_t,c el número de jugadores en el momento t con un color particular. c. La probabilidad de que ninguno de los jugadores con color c son afectados por otros jugadores en una ronda dada es representado por $ (\frac{m}{x} + (1 - \frac{m}{x}) * \frac{x-1-d_{t,c}}{x-1} )^{x-d_{t,c}} $.

d_t,c es un desconocido discreta distribución de probabilidad para cada color. Yo digo desconocido porque el intento de representar la distribución de probabilidad podría resultar en que el universo colapse.

Creo que la mejor manera de acreditar el mínimo de tiempo necesario para terminar necesario para terminar el juego sería el uso de la inducción matemática. Para ello había que probable que necesite para simplificar el problema en primer lugar, mediante la demostración de que un resultado particular es menor que/mayor que otro resultado. Y en eso, buena suerte.

Answer 2

Basado en los comentarios a bjorn respuesta, parece que hay cierta confusión acerca de la cuestión. La manera en que yo entendí fue que cada persona tiene asignado un color en cualquier momento en particular. Si el jugador B jugador dispara Un, entonces cambia su color a B color. Si el jugador C, a continuación, dispara el jugador B, entonces los jugadores a y B de cambio de C del color. Queremos saber cuánto tiempo se necesita para que todos tengan el mismo color.

Deje $G$ ser el grafo cuyos vértices son los jugadores y donde los vértices $i$ $j$ están unidos por una arista si $i$ ha disparado $j$. A continuación, dos jugadores tienen el mismo color exactamente si están en la misma componente conectado de $G$.

Veamos primero la pregunta más fácil donde taggings pasar completamente al azar: Cada después de cada $\frac{\mbox{1 hour}}{(1-m/x)x}$, algún jugador etiquetas de otro jugador al azar. Así que, después de $h$ horas, se espera que el número de aristas es $h(x-m)$, y cualquier conjunto de $h(x-m)$ bordes es tan probable como cualquier otro.

De acuerdo con un teorema de Erdos y Renyi, si $h(x-m)$ es mucho más que $(1/2) x \log x$, el gráfico es muy probable que estar conectado y, si $h(x-m)$ es mucho menor que $(1/2) x \log x$, el gráfico es muy raro estar conectado. Más precisamente: una Revisión constante de $c$. Considere la posibilidad de gráficos con $x$ vértices y $(1/2) x \log x + cx$ bordes, como $x \to \infty$. La probabilidad de que una gráfica es conectado es $\exp(- \exp(- 2c))$: muy cerca de $0$ $c$ negativo y muy cerca de a $1$ $c$ positivo.

Así que yo esperaría de conectividad después de unos $(1/2) \log x$ horas. La constante $m$ sólo produce efectos de segundo orden.

Su situación es un poco diferente, porque uno de los shooter puede etiquetar a dos personas en la misma hora. Me gustaría predecir la respuesta final es el mismo. Usted puede tratar de adaptar mi respuesta aquí a su configuración.