¿Hasta dónde puede llegar la intransigencia de la probabilidad?

Question

Hace tiempo leí sobre dados no transitivos - conjuntos de dados en los que "tiene más probabilidades de sacar un número mayor que" no es una relación transitiva. Cuando se me pasó la sorpresa, me pregunté: ¿hasta dónde se puede llevar este fenómeno? La página de Wikipedia enlazada tiene una sección llamada "Investigación de Freivald" que afirma que si $n$ Los dados están dispuestos en un círculo, cada uno con una probabilidad $p$ de ser mayor que el siguiente en la fila, entonces $p<3/4$ (con $p$ de otro modo se permite cerrar arbitrariamente). Sin embargo, tiene la infame etiqueta de [cita requerida] y no he podido encontrar ninguna referencia. Pero es posible una pregunta mucho más general.

Si tenemos $n$ variables aleatorias, todas independientes, etiquetadas $1,2,\dots, n$ y denotamos por $p_k$ la probabilidad $P(X_k > X_{k+1})$ (con el índice $n+1$ se desplazó en bicicleta hasta $1$ ), entonces podemos hablar del vector $\vec{p}=(p_1,\dots,p_n)\in(0,1)^n$ . Esto plantea la pregunta: ¿cuál es la forma del espacio $V \subset (0,1)^n$ de todos los posibles $\vec{p}$ 's? En particular, creo que podría haber una función simétrica tal que $V$ es la región delimitada por los conjuntos de niveles de $f(\vec{x})$ y $f(\vec{1}-\vec{x})$ para algunos $f:\mathbb{R}^n\to\mathbb{R}$ pero no estoy seguro, y por supuesto parece que sería imposible encontrar tal $f$ explícitamente. (Además, no estoy seguro de si la respuesta sería diferente para situaciones continuas y discretas, o en casos mixtos, pero todas las combinaciones suenan interesantes).

Answer 1

Podemos suponer sin pérdida de generalidad que todos los números son diferentes, ya que de lo contrario podríamos hacerlos ligeramente diferentes sin disminuir la probabilidad de que cualquier dado sea mayor que cualquier otro (ya que los resultados iguales no contribuyen a esa probabilidad).

A grandes rasgos, si la mediana del dado perdedor es mayor que la mediana del dado ganador, entonces la mitad inferior del dado ganador no puede vencer a la mitad superior del dado perdedor, por lo que para que la mediana aumente, debemos tener $p<3/4$ . Hay que rellenar algunos detalles para números pares e Impares de lados; el resultado es que $p\le3/4-(n/2+\alpha)/n^2$ , donde $n$ es el número de lados y $\alpha=0$ para incluso $n$ y $\alpha=1/4$ para impar $n$ . Esto va a $3/4$ como $n$ va al infinito.

El número de cualquier rango que no sea la mediana puede aumentarse más fácilmente, ya que se puede dejar que todos los números por debajo de él en el dado ganador superen a todos los números por debajo de él en el dado perdedor, y lo mismo para los números por encima de él, y la restricción que esto impone es más estricta en la mediana. Así, para cada rango, hay una combinación admisible para aumentar el número en ese rango.

Ahora pon $n$ dados con $n$ en un ciclo, e imponer un orden parcial a los números aún desconocidos exigiendo que en cada par de dados consecutivos los números formen uno de los patrones de orden construidos anteriormente, con el número de rango $k$ que se incrementa en el paso $k$ (empezando por el rango más alto). Para ver que este orden parcial es un orden total, observe que no hay ninguna restricción que requiera que cualquier número en las partes inferiores que se reducen por debajo de los rangos que se aumentan sea mayor que cualquier número en las partes superiores que crecen por encima de los rangos que se aumentan. Por lo tanto, no hay ciclos en este orden (esto es fácil de ver si se dibuja su gráfico para $n=3$ o $4$ ), por lo que podemos encontrar números adecuados mediante la ordenación topológica. Así, siempre podemos construir un ciclo con $n$ dados con $n$ lados para $p$ como en el caso anterior; de hecho, esta construcción hace que sea bastante sencillo derivar los números adecuados.

Aquí hay ejemplos para $n=3$ y $n=4$ (este último en hexadecimal), con un intento de visualizar la acyclicidad del gráfico de órdenes:

1 2 8
|/ /|
0 6 7
 /|/|
3 4 5
|/|/
1 2 8
|/ /|
0 6 7

3 4 5 F
|/|/ /|
1 2 D E
|/ /|/|
0 A B C
 /|/|/|
6 7 8 9
|/|/|/
3 4 5 F
|/|/ /|
1 2 D E
|/ /|/|
0 A B C