Minimizar la probabilidad de que un empate en una votación democrática

Question

Un grupo de $k$ de la gente quiere elegir democráticamente entre $n$ opciones posibles. Organizar una encuesta en la que cada persona votos para $r$ $n$ opciones, sin repetición, es decir, hay $n \choose r$ opciones posibles por persona. La más alta puntuación de la opción será el ganador de la elección, salvo que exista un empate, por supuesto...

Pregunta: Suponiendo que cada persona elige $r$ $n$ opciones con el uniforme de probabilidad. ¿Cuál es el valor de $r$ para el cual la probabilidad de la encuesta termina en un empate es mínima? Esperemos que la respuesta será único y en una forma cerrada $r=f(k,n)$.

Lamentablemente, más allá de trivial comentarios sobre los casos extremos (como $r=n$ implica dibujar va a pasar con total probabilidad y $r,k << n$ implica sorteo será bastante probable debido a la escasa votación) yo no tengo nada valioso que decir acerca de mis intentos hasta ahora.

Edit: Para cualquier persona que downvotes esto - por favor explique lo que usted piensa que está mal con la pregunta. Para poner las cosas en claro: Esto no es una tarea problema!. Aún así, si crees que esto es un problema trivial por favor, explique su solución - si no, entonces por favor reconsiderar el downvote.

Answer 1

Tratamos este rigor para $k=2$, y conjecturally para todos los $k$.

Para $k=2$, nos encontramos con $r \sim \sqrt{n}$.

Cuando a y B, cada voto $r$ opciones, evitar un empate iff B elige $1$ opción ya elegido por Una, y, a continuación, elige $(r-1)$ opciones no elegidas por A. por Lo que la probabilidad de evitar un empate es $$p=r {n-r \choose r-1} \ / \ {n \choose r}.$$ Esta probabilidad no puede ser maximizada en un límite como $r=0$ o $r=n$, ya que los que dan una probabilidad de $0$, por lo que debe ser maximizada en un lugar donde el discreto derivada es aproximadamente el $0$.

El óptimo $r$ será, por tanto, ser una solución a la $$\frac{r {n-r \elegir i-1}}{ {n \elegir r}} \sim \frac{(r+1) {n-r-1 \elegir r}}{ {n \elegir r+1}}.$$ En realidad podemos resolver esto: Cruz-la multiplicación y la cancelación de la reduce a $$r^2(n-r)^2 \sim (r+1)^2(n-2r)(n-2r+1).$$ Descuidar la final $+1$ y de la plaza de enraizamiento conduce a una ecuación cuadrática cuya solución es $$r \sim \sqrt{n+1} -1.$$ Para una primera aproximación a $r\sim\sqrt{n}$, y más precisamente, $r$ es un número entero dentro de$2$$\sqrt{n}$.

La generalización de mayor k

Esto sugiere una estrategia para la mayor $k$, es decir, la orientación, la expectativa de que exactamente una opción recibirán dos votos.

El $k,n,r$ escenario conduce exactamente una opción de conseguir dos votos con una probabilidad de $$p=\frac{{n \elegir kr-1}(kr-1)!(k-1)r^2} {\left({n \elegir r}r!\right)^k}$$

Mientras tanto, el número esperado de opciones de recibir dos votos es $$n{k \choose 2}\left(\frac{r}{n}\right)^2 \left(\frac{n-r}{n}\right)^{k-2}.$$ Así que elija $$r \sim \sqrt{n/{k \choose 2}}$$ y para un gran $n$, esto evita que los lazos con la limitación de probabilidad $$p \sim \frac{2}{ke}.$$

Answer 2

Creo que esto es bastante difícil.

Aquí está una simulación con $n=15$, $k=6$. La abscisa es $r$, en azul (eje derecho) tenemos que la probabilidad de empate, y en la red (eje izquierdo) el promedio de votos para el ganador.

No puedo estar seguro acerca de los errores de programación, pero estoy bastante seguro de que el golpe uglyness de la línea azul (la que determina la mínima que nos interesa, yo.e, $r=f(k,n)$) no es debido a la estadística de ruido de cada carrera consta de 10^6 ensayos, y diferentes simulaciones dan prácticamente los mismos valores.

En caso de que usted está interesado, aquí está la fuente (no se olvide que usted necesita para mantener el número de intentos de baja si usted desea que se ejecute en Ideone).