Anteriormente hice una pregunta sobre cómo calcular una probabilidad de forma rápida y precisa. Sin embargo, evidentemente fue demasiado fácil ya que se le dio una solución de forma cerrada. Aquí hay una versión más difícil.
Esta tarea consiste en escribir código para calcular una probabilidad de manera exacta y rápida . El resultado debe ser una probabilidad precisa escrita como una fracción en su forma más reducida. Es decir, nunca debería salir, 4/8
sino más bien 1/2
.
Para algún número entero positivo n
, considere una cadena uniformemente aleatoria de 1s y -1s de longitud n
y llámela A. Ahora concatene a A
una copia de sí mismo. Eso es A[1] = A[n+1]
si indexa desde 1, A[2] = A[n+2]
y así sucesivamente. A
Ahora tiene longitud 2n
. Ahora también considere una segunda cadena aleatoria de longitud n
cuyos primeros n
valores son -1, 0 o 1 con probabilidad 1 / 4,1 / 2, 1/4 cada uno y llámelo B.
Ahora considere el producto interno de B
con A[1+j,...,n+j]
para diferente j =0,1,2,...
.
Por ejemplo, considere n=3
. Los posibles valores de A
y B
podrían ser A = [-1,1,1,-1,...]
y B=[0,1,-1]
. En este caso, los dos primeros productos internos son 0
y 2
.
Tarea
Para cada uno j
, comenzando j=1
, su código debería generar la probabilidad de que todos los primeros j+1
productos internos sean cero para cada uno n=j,...,50
.
Copiando la tabla producida por Martin Büttner para obtener j=1
los siguientes resultados de muestra.
n P(n)
1 1/2
2 3/8
3 7/32
4 89/512
5 269/2048
6 903/8192
7 3035/32768
8 169801/2097152
Puntuación
Su puntaje es el más grande que j
su código completa en 1 minuto en mi computadora. Para aclarar un poco, cada j
uno tiene un minuto. Tenga en cuenta que el código de programación dinámica en la pregunta vinculada anterior lo hará fácilmente j=1
.
Desempate
Si dos entradas obtienen el mismo j
puntaje, la entrada ganadora será la que obtenga la mayor puntuación n
en un minuto en mi máquina para eso j
. Si las dos mejores entradas son iguales en este criterio también, entonces el ganador será la respuesta presentada primero.
Idiomas y bibliotecas
Puede utilizar cualquier idioma y bibliotecas disponibles gratuitamente que desee. Debo poder ejecutar su código, así que incluya una explicación completa sobre cómo ejecutar / compilar su código en Linux si es posible.
Mi máquina Los tiempos se ejecutarán en mi máquina. Esta es una instalación estándar de ubuntu en un procesador AMD FX-8350 de ocho núcleos. Esto también significa que necesito poder ejecutar su código.
Entradas ganadoras
j=2
en Python por Mitch Schwartz.j=2
en Python por feersum. Actualmente la entrada más rápida.
fuente
Respuestas:
Pitón 2, j = 2
Traté de encontrar una especie de 'forma cerrada' para j = 2. Tal vez podría hacer una imagen de MathJax, aunque sería realmente feo con todo el violín del índice. Escribí este código no optimizado solo para probar la fórmula. Tarda aproximadamente 1 segundo en completarse. Los resultados coinciden con el código de Mitch Schwartz.
Considere una secuencia donde el miembro i-ésimo es
e
si A [i] == A [i + 1] on
si A [i]! = A [i + 1].i
en el programa es el número den
s. Sii
es par, la secuencia debe comenzar y terminar cone
. Sii
es impar, la secuencia debe comenzar y terminar conn
. Las secuencias se clasifican además por el número de corridas de soe
s consecutivasn
. Hayj
+ 1 de uno yj
del otro.Cuando la idea paseo aleatorio se extiende a 3 dimensiones, existe un problema desafortunado que hay 4 posibles direcciones para caminar en (uno para cada uno de
ee
,en
,ne
, onn
) que significa que no son linealmente dependientes. Entonces, elk
índice suma el número de pasos dados en una de las direcciones (1, 1, 1). Luego habrá un número exacto de pasos que se deben seguir en las otras 3 direcciones para cancelarlo.P (n, p) da el número de particiones ordenadas de n objetos en p partes. W (l, d) da el número de formas para que una caminata aleatoria de
l
pasos recorra una distancia de exactamented
. Como antes, hay 1 posibilidad de moverse hacia la izquierda, 1 oportunidad de moverse hacia la derecha y 2 para quedarse.fuente
j=3
. ¡Eso sería sorprendente!Python, j = 2
El enfoque de programación dinámica para
j = 1
mi respuesta a la pregunta anterior no necesita muchas modificaciones para funcionar en niveles superioresj
, pero se ralentiza rápidamente. Tabla de referencia:Y el código:
Aquí estamos hacer el seguimiento de los dos primeros elementos de
A
, los dos últimos elementos deB
(dondeb2
es el último elemento), y los productos internos de(A[:n], B)
,(A[1:n], B[:-1])
, y(A[2:n], B[:-2])
.fuente