¿Cuál es la probabilidad de que un elemento permanezca en la misma posición en la matriz de n elementos distintos (por ejemplo, 0..n-1) después de realizar k intercambios aleatorios (el intercambio se realiza como elegir los índices k1 y k2 (k1 <k2) y cambiar un [k1] y un [k2]) en la matriz? Además, ¿cuál es la probabilidad de que la matriz permanezca igual después de estos k intercambios aleatorios?

Answer 1

La respuesta se puede calcular utilizando la siguiente recurrencia. Deje que [math] n [/ math] sea el tamaño de la matriz.

Sea [math] p_x [/ math] la probabilidad de que después de que [math] x [/ math] intercambie un elemento en particular, esté en su lugar original. Por simetría, esta probabilidad es la misma para cada elemento. También por simetría, la probabilidad de que el elemento [matemática] a [/ matemática] esté actualmente en la posición [matemática] b \ not = a [/ matemática] es la misma para todos [matemática] a, b [/ matemática]. Denotémoslo [math] q_x = (1-p_x) / (n-1) [/ math].

Tenemos [matemáticas] p_0 = 1 [/ matemáticas] y

[matemática] p_ {x + 1} = \ left ((n-1) q_x + {n-1 \ choose 2} p_x \ right) ~ / ~ {n \ choose 2} [/ math]

(¿Por qué? Considere el último intercambio y un elemento arbitrario. Con probabilidad [matemática] p_x [/ matemática] el elemento está en su lugar original, y con probabilidad [matemática] {n-1 \ elegir 2} / {n \ elegir 2 } [/ math] permanecerá allí. Además, para cada una de las otras ubicaciones [math] n-1 [/ math], nuestro elemento está actualmente en esa ubicación con probabilidad [math] q_x [/ math], y lo hará moverse a su ubicación original con probabilidad [matemática] 1 / {n \ elegir 2} [/ matemática].)

Para una [matemática] n [/ matemática] particular y un número particular de pasos [matemática] k [/ matemática] se puede usar la recurrencia anterior (y programación / memorización dinámica) para calcular la probabilidad de que un elemento particular termine en su lugar original

Aquí hay unos ejemplos:

• [matemáticas] n = 100, ~ k = 100 [/ matemáticas]: 13.86% de probabilidad de que un elemento en particular esté en su lugar original, solo 0.87% de probabilidad de que esté en un lugar determinado, muy lejos de ser aleatorio
• [matemáticas] n = 100, ~ k = 200 [/ matemáticas]: 2.67% de probabilidad de estar en la ubicación original, aún no lo suficientemente aleatorio
• [matemáticas] n = 100, ~ k = 300 [/ matemáticas]: 1.22% de probabilidad para el mismo lugar, 0.998% para cualquier otro lugar – comienza a ser casi aleatorio
• [matemáticas] n = 100, ~ k = 500 [/ matemáticas]: probabilidad de 1.004% para el mismo lugar, lo suficientemente aleatorio para algunos propósitos
• [matemática] n = 100000, ~ k = 500000 [/ matemática]: probabilidad de 5.54 / 100000 para el mismo lugar, todavía muy lejos de ser aleatorio

Empíricamente, los intercambios aleatorios [matemática] \ Theta (n \ log n) [/ matemática] son ​​necesarios y suficientes para obtener una probabilidad razonablemente cercana a [matemática] 1 / n [/ matemática]. (Esto también se ha demostrado, al menos para un algoritmo de intercambio aleatorio ligeramente diferente. A continuación se proporciona un enlace).

Una vez que dejamos de enfocarnos en un elemento en particular y miramos toda la permutación, se podría suponer que “la probabilidad de que cualquier elemento esté en cualquier ubicación es cercana a [matemáticas] 1 / n [/ matemáticas]” es lo mismo que “cada permutación es aproximadamente igualmente probable “. Esto es falso

El culpable es la paridad de la permutación: la paridad del número de ciclos que tiene (o, equivalentemente, la paridad del número de inversiones). Cada intercambio cambia esta paridad. Por lo tanto, dada una matriz de elementos [math] n [/ math] y un número suficientemente grande pero fijo [math] x [/ math] de swaps, solo [math] n! / 2 [/ math] diferentes permutaciones puede lograrse. Las otras [matemáticas] n! / 2 [/ matemáticas] son ​​demostrablemente imposibles.

Y esto es lo que sucederá realmente: una vez que realice un número suficiente de intercambios, cada una de las permutaciones [matemáticas] n! / 2 [/ matemáticas] que son posibles actualmente aparecerá con una probabilidad cercana a [matemáticas] 2 / n! [ /matemáticas].

Aquí hay un artículo (bastante antiguo) que analiza un método de barajado similar: https://statistics.stanford.edu/…
(tenga en cuenta que la forma en que eligen los elementos para intercambiar se ocupa del problema que plantea la paridad de la permutación al hacer posible no intercambiar nada en algunos pasos).

PD: Como obvio, cuando realmente quieres permutar una matriz, Fisher-Yates shuffle lo hace de manera correcta y óptima. Se deben evitar los intercambios completamente al azar.

Answer 2

Denotemos con [matemática] P_s [/ matemática] la probabilidad de que un solo intercambio implique el elemento que me interesa. Suponiendo que cada intercambio es igualmente probable, [matemática] P_s = \ frac {N-1} {\ binom { N} {2}} = \ frac {2} {N} [/ matemáticas].

Denotemos con [math] P_ {ss} [/ math] la probabilidad de que un solo intercambio involucre nuestro número y lo mueva a una posición muy específica. Prácticamente, esta es la posibilidad de que un intercambio aleatorio involucre 2 elementos específicos, y por lo tanto es trivialmente [matemático] P_ {ss} = \ frac {1} {\ binom {N} {2}} = \ frac {2} { N (N-1)} [/ matemáticas].

Denotemos con [math] P_k [/ math] la probabilidad de que nuestro número específico vuelva a su posición inicial después de los intercambios de [math] k [/ math]. Trivialmente, [matemáticas] P_0 = 1 [/ matemáticas]. Además, todo el proceso puede describirse como una cadena de Markov sin memoria, y por lo tanto la probabilidad de que el número esté en su posición después del número de intercambio [math] k [/ math] puede expresarse recursivamente en función de la probabilidad de que esté en su posición después del número de intercambio [math] k-1 [/ math], sin tener que tener en cuenta los estados de los swaps anteriores, es decir, [math] P_k = P_ {k-1} (1-P_s) + (1- P_ {k-1}) P_ {ss} [/ matemática] [matemática] = P_ {ss} + P_ {k-1} (1 – P_s – P_ {ss}) [/ matemática].

La solución se puede encontrar en O (K) usando este código:

from __future__ import division N = input('input number of elements: ') K = input('input number of swaps: ') Ps = 2/N Pss = 2/(N**2-N) Pk = 1 a = Pss b = 1 - Ps - Pss for k in range(K): Pk = a + Pk*b print 'Pk =', Pk 

Dato curioso: para K >> N, la probabilidad Pk tiende a ser simplemente 1 / N, porque la matriz se barajará tanto que el elemento que le interesa es igualmente probable en cualquiera de las N posiciones.

Todavía estoy pensando en cómo resolver la segunda parte de la pregunta …

Answer 3

50-50