Expectativa de un evento

Question

Deje $A$ ser una matriz de longitud 1000 con todas las entradas 0. Quiero llenar $A$ con usando el siguiente enfoque:

En cada iteración tomo tres enteros aleatorios $(j_1,j_2,j_3)$ a partir de [1,1000] con reemplazo y hacer lo siguiente:

1. Set $A[j_1]=1$

   2a. Si $A[j_2]=1$$A[j_3]=0$, a continuación, establezca $A[j_3]=1$

   2b. si $A[j_2]=0$$A[j_3]=1$, a continuación, establezca $A[j_2]=1$

   2c. Si $A[j_2]=A[j_3]=0$, no hacer nada

¿Cuál es el número esperado de dichas pruebas, para completar con todos?

Con el reemplazo de medios de $j_2$ puede ser igual a $j_3$ o anterior de la $j_2$ etc.

Answer 1

Si estoy entendiendo el problema correctamente, parece que podemos expresar todo lo que en términos de número de $X_n$ de 1s en la matriz en el paso $n$. Esto le da una forma mucho más simple de la cadena de Markov a analizar.

Deje $N = 1000$, y supongamos que en el tiempo de $n$ tenemos $k$ 1s en la matriz. Supongamos primero que $A[j_1] = 0$ (ocurre con una probabilidad de $(N-k)/N$). Lo ponemos a 1, ganando un 1 (por lo que ahora hay $k+1$ 1s). Si $A[j_2]$ $A[j_3]$ 1 (prob $((k+1)/N)^2$) o 0 (prob $((N-(k+1))/N)^2$), no más de 1s que se han obtenido. Si exactamente uno de $A[j_2], A[j_3]$ es de 1 (prob $2(k+1)(N-(k+1))/N^2$), y 1 ganado.

Del mismo modo, si $A[j_1] = 1$ (prob $k/N$) entonces obtenemos un 1 con una probabilidad de $k(N-k)/N^2$, o no más de 1s con una probabilidad de $(k^2 + (N-k)^2)/N^2$.

Para poner todo esto junto, tenemos las probabilidades de transición para $X_n$ son: $$\begin{align*} p(k, k) &= \frac{k(k^2 + (N-k)^2)}{N^3} \\ p(k, k+1) &= \frac{k^2(N-k) + 2 (N-k)(k+1)(N-(k+1))}{N^3} \\ p(k, k+2) &= \frac{(N-k)((k+1)^2 + ((N-(k+1))^2)}{N^3} \end{align*} $$

Tal vez alguien pueda comprobar que estos suman 1, como no tengo el tiempo ahora mismo. Pero esto, al menos, reducir el problema. Podría ser una mancha de la martingala solución; voy a editar si pienso en algo.

Answer 2

Sólo para completar Nate Eldredge la respuesta. Como su respuesta, dice, es suficiente para considerar el estado en cualquier punto como el número de unos de la matriz. Deje $\mathsf E[k]$ ser el número esperado de pasos que se necesitan para llenar la matriz con, a partir de un estado con $k$. A continuación, los cálculos en esencia como en su respuesta (en los comentarios de abajo) dar una relación de recurrencia para $\mathsf E[k]$, que pueden ser resueltos por ejemplo con el siguiente código (usa Sabio; se puede poner en un .sage archivo y ejecutar), que da la respuesta: $$2861.36107443079$$

Esto está de acuerdo con la Lista de usuarios de la simulación.

N = 1000
E = [0]*(N+2)
def findE(k):
    if k>=N: return 0
    p1 = k/N          #Pr. that A[j1]=1
    p0 = 1-p1         #Pr. that A[j1]=0
    p2 = (k+1)/N      #Pr. that A[j2]=0, assuming A[j1] was 0 and was set to 1
    p1d = 2*p1*(1-p1) #Pr. that {A[j2],A[j3]} = {1, 0}, assuming A[j1] was 1
    p0d = 2*p2*(1-p2) #Pr. that {A[j2],A[j3]} = {1, 0}, assuming A[j1] was 0
    #Now,
    #E[k] = 1 + p1*(p1d*E[k+1]+(1-p1d)*E[k]) + p0*(p0d*E[k+2]+(1-p0d)*E[k+1])
    #so
    #E[k]*(1-p1*(1-p1d)) = 1 + p1*p1d*E[k+1] + p0*(p0d*E[k+2]+(1-p0d)*E[k+1])
    return (1 + p1*p1d*E[k+1] + p0*(p0d*E[k+2]+(1-p0d)*E[k+1])) / (1-p1*(1-p1d))

for k in range(N+1, -1, -1): E[k] = findE(k)
print n(E[0])

Si la última instrucción es cambiado a print E[0] imprime la respuesta exacta como un número racional que en términos mínimos es una 3075-dígito entero dividido por un 3072-dígito entero, claramente no vale la pena informar - y también corriendo todas las esperanzas de que un ser humano razonable de paciencia podría llegar a la respuesta por la mano.

Answer 3

Esto no responde a la pregunta, pero podría ser útil para otros que todavía están con la intención de responder:

Test[n_] := (iter = 0; cset = ConstantArray[0, n]; 
   While[Count[cset, 1] != n, (iter = iter + 1; 
     rand = RandomInteger[{1, n}, {3}]; cset[[rand[[1]]]] = 1; 
     If[cset[[rand[[2]]]] == 1 || 
       cset[[rand[[3]]]] == 1, (cset[[rand[[2]]]] = 1; 
       cset[[rand[[3]]]]  = 1), Null];)]; Return[iter]);

El uso de este código de mathematica uno puede generar una instancia del problema (en este caso $n=1000$). He usado esto como un Monte-Carlo enfoque para aproximar el número promedio de pasos. En la siguiente imagen se puede ver el paso de conteo en los ensayos ( I simulado 10.000 instancias del problema ):

Si el promedio de los pasos que usted consigue $n_{average} \approx 2861$, lo que también encaja con pruebas que hice con la menor paso cuenta. Por lo que podemos esperar de una solución analítica para rendir este dentro de un rango de unos pocos pasos.