Usando una carrera de jugadores para aproximar ππ\pi

Question

Usando una carrera de jugadores para aproximar ππ\pi

Pi
suma
Matemáticas
probabilidad
combinatoria
coeficientes binomiales

Rohit Pandey

Imagine que dos jugadores adinerados comienzan a lanzar sus propias monedas justas por separado, ganando 1 $ si sale cara y perdiendo 1 $ si sale cruz. Ambos comienzan en 0 $ y tienen saldos bancarios infinitos. Ambos quieren llegar a k $ . ¿Cuál es la probabilidad de que ambos alcancen sus objetivos en el mismo lanzamiento?

Con base en esta pregunta, vemos que las respuestas a todas esas preguntas toman la forma $A+\frac{B}{\pi}$ . Aquí, nos estamos enfocando estrictamente en los sorteos. Primero, sabemos que el tiempo de parada (probabilidad de que alcance su objetivo la primera vez en el lanzamiento) $2t+k$ ) para cualquier jugador está dada por:

a_{k} (t) = \frac{k}{k + t} \frac{(\binom{2 t + k - 1}{t})}{2^{2 t + k}}

$a_k(t) = \frac{k}{k+t}\frac{{2t+k-1 \choose t}}{2^{2t+k}}$

Ahora, la probabilidad de un empate general es simplemente la probabilidad de que ambos alcancen su objetivo en el lanzamiento. $2t+k$ , sumado sobre todos los valores posibles de $t$ .

D_{k} = \sum_{t = 0}^{\infty} {(\frac{k}{k + t} \frac{(\binom{2 t + k - 1}{t})}{2^{2 t + k}})}^{2}

$D_k = \sum\limits_{t=0}^{\infty} \left(\frac{k}{k+t}\frac{{2t+k-1 \choose t}}{2^{2t+k}}\right)^2$

Mathematica no puede encontrar una buena expresión de forma cerrada para la suma anterior (si puede, me impresionará mucho). Sin embargo, conectando varios valores de $k$ en encontramos que la respuesta siempre toma la forma:

D_{k} = \frac{{mi}_{k}}{F_{k} π} - {GRAMO}_{k}

$D_k = \frac{E_k}{F_k \pi} - G_k$

Dónde $E_k$ , $F_k$ y $G_k$ son todos enteros. Conectando los primeros valores de $G_k$ (calculado usando Mathematica) en OEIS, obtuve la secuencia A002002 . Esto significa que:

{GRAMO}_{k} = \sum_{yo = 0}^{k - 1} (\binom{k}{yo + 1}) (\binom{k + yo}{yo})

$G_k = \sum\limits_{l=0}^{k-1} {k \choose l+1} {k+l \choose l}$

Sin embargo, no he podido encontrar las expresiones correspondientes para $E_k$ y $F_k$ . ¿Alguien puede ayudarme con esto? Podemos usarlo para obtener una expresión para $\pi$ desde $D_{\infty} = 0$

Estas son las primeras expresiones para $D_k$ .

D_{1} = \frac{4}{π} - 1

$D_1 = \frac{4}{\pi}-1$

D_{2} = \frac{dieciséis}{π} - 5

$D_2 = \frac{16}{\pi}-5$

D_{3} = \frac{236}{3 π} - 25

$D_3 = \frac{236}{3 \pi}-25$

D_{4} = \frac{1216}{3 π} - 129

$D_4 = \frac{1216}{3 \pi} - 129$

D_{5} = \frac{32092}{15 π} - 681

$D_5 = \frac{32092}{15 \pi} - 681$

D_{6} = \frac{172144}{15 π} - 3653

$D_6 = \frac{172144}{15 \pi} - 3653$

D_{7} = \frac{1307924}{21 π} - 19825

$D_7 = \frac{1307924}{21 \pi} - 19825$

D_{8} = \frac{7161088}{21 π} - 108545

$D_8 = \frac{7161088}{21 \pi} - 108545$

D_{9} = \frac{592194476}{315 π} - 598417

$D_9 = \frac{592194476}{315 \pi} - 598417$

D_{10} = \frac{3282949168}{315 π} - 3317445

$D_{10} = \frac{3282949168}{315 \pi} - 3317445$

D_{11} = \frac{40221561524}{693 π} - 18474633

$D_{11} = \frac{40221561524}{693 \pi} - 18474633$

D_{12} = \frac{224841634624}{693 π} - 103274625

$D_{12} = \frac{224841634624}{693 \pi} - 103274625$

Desafortunadamente, Mathematica renuncia a proporcionar buenas expresiones en términos de $\pi$ , $D_{13}$ adelante.

La idea es cortesía de /u/boyobo en este hilo de reddit .

maestro del rencor

Mi instinto es que tener

E_{k}

$E_k$ y

F_{k}

$F_k$ en su forma más baja te está haciendo perder algunos factores comunes; o deberías tratar

E_{k} / F_{k}

$E_k/F_k$ como una sola variable o hay factores que deben ser encontrados. Asumiendo que

236 / 16

$236/16$ es de hecho igual a

E_{3} / E_{2}

$E_3/E_2$ , los factores no serán grandes. Esto es, por supuesto, especulación y se basa puramente en mi intuición: no puedo encontrar ningún patrón al hacerlo, pero tal vez alguien más pueda hacerlo.

jeremy dover

De acuerdo con @Spitemaster; el

F_{k}

$F_k$ denominador casi definitivamente debe tener un

k!

$k!$ componente, si observas cómo entran los factores primos 3, 5, 7 y 11.

Rohit Pandey

¿Existe también una enciclopedia en línea para secuencias no enteras? Tal vez las fracciones

E_{k} / F_{k}

$E_k/F_k$ seguir algún patrón.

Rohit Pandey

A037964 Brevemente ofreció esperanza.

alex ravski

Me temo que una enciclopedia de secuencias no enteras no está en línea sino un apéndice de El Libro, en el que, según Paul Erdős, Dios había escrito las mejores y más elegantes demostraciones de teoremas matemáticos. :-) Pero incluso estando restringido a enteros, tengo la esperanza de adaptarme para

F_{k}

$F_k$ una de las primeras secuencias en esta consulta. Supongo que un conocimiento de

F_{13}

$F_{13}$ puede ayudar a elegir el camino correcto.

Rohit Pandey

Gracias alex También por la nota sobre el blog. Tristemente, Mathematica renuncia a proporcionar una buena expresión en términos de

π

$\pi$ para n=13 (lo hace hasta 12). Escupe "HypergeometricFPQ[{13/2,13/2,7,7},{1,14,14},1]/67108864" cuando conecto 13. La respuesta numérica es 1.89455e-3.

alex ravski

Miré más de cerca las secuencias mencionadas anteriormente. Algunos de ellos parecen relevantes, especialmente A086116 con una referencia de MathWorld a " Random Walk--1-Dimensional " de Eric W. Weisstein.

Rohit Pandey

Esos 21 son realmente espinas en los costados. Desearía que hubiera una forma de calcular la expresión para 13.

Anders Kaseorg

Aunque Mathematica no puede reducirse (d[13] + g[13])Pia un número racional, le dará un resultado muy llamativo para ContinuedFraction[(d[13] + g[13])Pi + N[10^-100, 100]], que puede truncar en el elemento estúpidamente grande para obtener una evidencia numérica muy sólida de que

\frac{E_{13}}{F_{13}}

$\frac{E_{13}}{F_{13}}$ es FromContinuedFraction[{1819512525, 1, 4, 2, 1, 1, 1, 1, 1, 2, 3}]=

\frac{1821332038340}{1001}

$\frac{1821332038340}{1001}$ . Los próximos a partir de

\frac{E_{14}}{F_{14}}

$\frac{E_{14}}{F_{14}}$ parece ser

\frac{10242265213328}{1001}, \frac{2598075674762068}{45045}, \frac{14675811920024576}{45045}, \frac{282378678293341060}{153153}

$\frac{10242265213328}{1001}, \frac{2598075674762068}{45045}, \frac{14675811920024576}{45045}, \frac{282378678293341060}{153153}$ .

Rohit Pandey

¡Gracias, esto es genial! ¿Puede compartir una captura de pantalla de su código de Mathematica con estos comandos? Todavía soy nuevo con eso y ni siquiera sé cómo poner las d y las g en matrices. Además, ¿cuál es el papel de N[10^-100,100]?

Anders Kaseorg

@RohitPandey Este no es el mejor espacio para enseñar Mathematica, pero lo acabo de hacer

d[k_] = Sum[(k/(k + t) Binomial[2t + k - 1, t]/2^(2t + k))^2, {t, 0, Infinity}]; g[k_] = Sum[Binomial[k, l + 1] Binomial[k + l, l], {l, 0, k - 1}]

(los corchetes simples son para funciones, no para matrices). yo añadí

10^{- 100}

$10^{-100}$ para evitar obligar a Mathematica a comparar una expresión que no sabe que es racional con la fracción exacta; de lo contrario, no está dispuesto a comprometerse con el último elemento que necesitamos de la expansión de fracción continua. N[…, 100]evalúa numéricamente con 100 dígitos de precisión.

Rohit Pandey

Bien, gracias de nuevo. No pensé que alguna vez conocería una recurrencia de este problema. Incluso podría ser posible resolverlo ahora :)

Respuestas (1)

Usando una carrera de jugadores para aproximar ππ\pi

Mi instinto es que tener $E_k$ y $F_k$ en su forma más baja te está haciendo perder algunos factores comunes; o deberías tratar $E_k/F_k$ como una sola variable o hay factores que deben ser encontrados. Asumiendo que $236/16$ es de hecho igual a $E_3/E_2$ , los factores no serán grandes. Esto es, por supuesto, especulación y se basa puramente en mi intuición: no puedo encontrar ningún patrón al hacerlo, pero tal vez alguien más pueda hacerlo.
De acuerdo con @Spitemaster; el $F_k$ denominador casi definitivamente debe tener un $k!$ componente, si observas cómo entran los factores primos 3, 5, 7 y 11.
¿Existe también una enciclopedia en línea para secuencias no enteras? Tal vez las fracciones $E_k/F_k$ seguir algún patrón.
Me temo que una enciclopedia de secuencias no enteras no está en línea sino un apéndice de El Libro, en el que, según Paul Erdős, Dios había escrito las mejores y más elegantes demostraciones de teoremas matemáticos. :-) Pero incluso estando restringido a enteros, tengo la esperanza de adaptarme para $F_k$ una de las primeras secuencias en esta consulta. Supongo que un conocimiento de $F_{13}$ puede ayudar a elegir el camino correcto.
Gracias alex También por la nota sobre el blog. Tristemente, Mathematica renuncia a proporcionar una buena expresión en términos de $\pi$ para n=13 (lo hace hasta 12). Escupe "HypergeometricFPQ[{13/2,13/2,7,7},{1,14,14},1]/67108864" cuando conecto 13. La respuesta numérica es 1.89455e-3.
Miré más de cerca las secuencias mencionadas anteriormente. Algunos de ellos parecen relevantes, especialmente A086116 con una referencia de MathWorld a " Random Walk--1-Dimensional " de Eric W. Weisstein.
Esos 21 son realmente espinas en los costados. Desearía que hubiera una forma de calcular la expresión para 13.
Aunque Mathematica no puede reducirse (d[13] + g[13])Pia un número racional, le dará un resultado muy llamativo para ContinuedFraction[(d[13] + g[13])Pi + N[10^-100, 100]], que puede truncar en el elemento estúpidamente grande para obtener una evidencia numérica muy sólida de que $\frac{E_{13}}{F_{13}}$ es FromContinuedFraction[{1819512525, 1, 4, 2, 1, 1, 1, 1, 1, 2, 3}]= $\frac{1821332038340}{1001}$ . Los próximos a partir de $\frac{E_{14}}{F_{14}}$ parece ser $\frac{10242265213328}{1001}, \frac{2598075674762068}{45045}, \frac{14675811920024576}{45045}, \frac{282378678293341060}{153153}$ .
¡Gracias, esto es genial! ¿Puede compartir una captura de pantalla de su código de Mathematica con estos comandos? Todavía soy nuevo con eso y ni siquiera sé cómo poner las d y las g en matrices. Además, ¿cuál es el papel de N[10^-100,100]?
@RohitPandey Este no es el mejor espacio para enseñar Mathematica, pero lo acabo de hacer d[k_] = Sum[(k/(k + t) Binomial[2t + k - 1, t]/2^(2t + k))^2, {t, 0, Infinity}]; g[k_] = Sum[Binomial[k, l + 1] Binomial[k + l, l], {l, 0, k - 1}](los corchetes simples son para funciones, no para matrices). yo añadí $10^{-100}$ para evitar obligar a Mathematica a comparar una expresión que no sabe que es racional con la fracción exacta; de lo contrario, no está dispuesto a comprometerse con el último elemento que necesitamos de la expansión de fracción continua. N[…, 100]evalúa numéricamente con 100 dígitos de precisión.
Bien, gracias de nuevo. No pensé que alguna vez conocería una recurrencia de este problema. Incluso podría ser posible resolverlo ahora :)

Anders Kaseorg · Answer 1

La entrada OEIS para A002002 da la recurrencia

2 (6 k^{2} - 12 k + 5) {GRAMO}_{k - 1} - (k - 2) (2 k - 1) {GRAMO}_{k - 2} - k (2 k - 3) {GRAMO}_{k} = 0.

$2(6k^2-12k+5)G_{k-1}-(k-2)(2k-1)G_{k-2}-k(2k-3)G_k = 0.$

En una corazonada al azar, intenté $D_n$ con el mismo operador y encontró que

2 (6 k^{2} - 12 k + 5) D_{k - 1} - (k - 2) (2 k - 1) D_{k - 2} - k (2 k - 3) D_{k} = \frac{8}{π}

$2(6k^2-12k+5)D_{k-1}-(k-2)(2k-1)D_{k-2}-k(2k-3)D_k = \frac{8}{\pi}$

se mantiene para todos los valores que Mathematica puede reducir a forma cerrada ( $2 \le k \le 12$ ), y continúa manteniéndose numéricamente en cientos de dígitos significativos para miles de términos, por lo que es casi seguro que esta es la recurrencia correcta.

Usando una carrera de jugadores para aproximar ππ\pi

Rohit Pandey

maestro del rencor

jeremy dover

Rohit Pandey

Rohit Pandey

alex ravski

Rohit Pandey

alex ravski

Rohit Pandey

Anders Kaseorg

Rohit Pandey

Anders Kaseorg

Rohit Pandey

Respuestas (1)

Anders Kaseorg

Demostrar una identidad combinatoria que involucre la suma del producto de coeficientes binomiales

Simplificando el producto de múltiples expansiones binomiales

Prueba combinatoria de la identidad 3n=∑nk=0(nk)2k3n=∑k=0n(nk)2k3^n=\sum_{k=0}^n \binom nk 2^k

Pregunta de prueba de suma binomial/combinatoria

Suma del producto de coeficientes binomiales: ∑nk=0(−1)k(nk)(n+kk)=(−1)n∑k=0n(−1)k(nk)(n+kk)=(− 1)n\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{n + k}{k} = (-1)^n

Probabilidad de sacar 5 cartas del mazo barajado

Cálculo de puntos mínimos para pasar como equipo en una liga deportiva

Prueba combinatoria de ∑i=0m2n−i(ni)(mi)=∑i=0m(n+m−im)(ni)∑i=0m2n−i(ni)(mi)=∑i=0m(n+ m−im)(ni) \sum \limits_{i = 0} ^{m} 2^{ni} {n \choose i}{m \choose i} = \sum\limits_{i=0}^m { n + m - yo \elegir m} {n \elegir i}

Prueba combinatoria para la identidad ∑nk=0(nk)(−2)k=(−1)n∑k=0n(nk)(−2)k=(−1)n\sum_{k=0}^n \binom{n}{k}\left(-2\right)^k = (-1)^n

Suma parcial de coeficientes binomiales n elige k multiplicado por k para k de n/2+1 a n