Estimación del valor de eee usando una función aleatoria

Question

Estimación del valor de eee usando una función aleatoria

J wang

Encontré la pregunta que le pide que calcule el valor de $\pi$ utilizando una función que genera un número real aleatorio en $[0,1]$ (y está distribuida uniformemente). La forma es usar la función dos veces para obtener un par real que podamos ver como un punto en el plano euclidiano, luego usar la idea del método de Monte Carlo. Me pregunto si también podemos usar esta función para estimar $e$ , sin embargo, no puedo encontrar ninguna interpretación geométrica del número, o este problema se puede resolver de otra manera?

nicomezi

Relacionado

Pedro O.

Relacionado: stats.stackexchange.com/questions/193990/…

Respuestas (7)

Estimación del valor de eee usando una función aleatoria

Jean-Claude Arbaut · Answer 1

Jean-Claude Arbaut

Generar $N$ permutaciones aleatorias (posiblemente con la mezcla aleatoria de Knuth ).

Luego cuente cuántos de ellos son trastornos : $N_D$ .

Entonces

\frac{norte}{{norte}_{D}} ≃ mi

$\frac N{N_D}\simeq e$

Un lector rural

¡Una hermosa solución!

J wang

¡Pero solo se cumple cuando N es lo suficientemente grande, calculando N! sería doloroso…

Jean-Claude Arbaut

@JWang No, la verdadera proporción converge rápidamente a

1 / e

$1/e$ como

k

$k$ crece (

k

$k$ siendo la longitud de la permutación). Sin embargo, la convergencia de la aproximación de monte carlo es mucho más lenta. Para permutaciones en

k = 10

$k=10$ elementos, con

N = 10^{8}

$N=10^8$ muestras, obtengo

N / N_{D} ≃ 2.718006253262627

$N/N_D\simeq2.718006253262627$ . No está mal. Y cualquiera que sea la longitud de la permutación, necesita muchas muestras de todos modos: con solo una, aunque la probabilidad es cercana a

1 / e

$1/e$ , solo hay dos valores posibles para

N_{D} / N

$N_D/N$ :

0

$0$ o

1

$1$ .

capitán jirafa

Un ejercicio de codificación rápido y sucio proporciona e = 2.718 +-0.036alrededor de 1000 muestras de alrededor de 1000 elementos cada una. pastebin.com/gAEXhdWf

Misha Lavrov

Si está tomando menos de

k!

$k!$ muestras, el tamaño de la muestra es la mayoría de su error: con

N

$N$ muestras, su error está en el orden de

\pm \frac{1}{\sqrt{N}}

$\pm \frac1{\sqrt N}$ , mientras que la verdadera fracción de trastornos está dentro de

\frac{1}{k!}

$\frac1{k!}$ de

\frac{1}{e}

$\frac1e$ . Si, por el contrario, estás tomando

k!

$k!$ o más muestras, debe seguir adelante y contar todos los trastornos, en lugar de muestrearlos al azar :)

Jean-Claude Arbaut

@MishaLavrov Cierto. :)

jukka kohonen · Answer 2

Dibujar $X_i \sim \text{Unif}(1,3)$ y $Y_i \sim \text{Unif}(0,1)$ para $i=1,\ldots,N$ . Rechazar las muestras donde $Y_i > 1/X_i$ . Ordenar lo aceptado $X_i$ valores y tomar el $(N/2)$ s.

Esto se basa en la observación de que $\int_1^e dx/x = 1$ . Así que hacemos muestreo de rechazo en el rectángulo. $[1,3] \times [0,1]$ para obtener puntos bajo el $1/x$ curva. tomando el $(N/2)$ el valor más pequeño estamos encontrando el punto donde tenemos $1/2$ de los puntos originales, es decir, área $1$ (observando que el rectángulo original tiene área $2$ ).

Aquí está la simulación con $N=10000$ puntos. Los puntos rechazados están en cian. De los puntos aceptados, el más a la izquierda $N/2=5000$ están en negro y el resto en azul.

¡Lindo! Aquí hay una manera de hacer esto con muchos menos rechazos. Solo genera $n$ iid puntos uniformemente entre $1$ y $3$ , ordénalos así $1<x_1<x_2<\dots<x_n<3$ , luego utilícelos como una malla para aproximar $\int_1^{x_i} dx/x$ con la regla del punto medio. seguir aumentando $i$ hasta la primera vez que la integral aproximada exceda $1$ . Entonces $e\approx x_i$ .
¡Mike, tu solución es infinitamente mejor que la mía en términos de eficiencia! Me esforzaba por emular los "puntos originales en el disco para $\pi$ "espíritu lo más cerca posible.

mateo h · Answer 3

Tirar una moneda sesgada $K$ veces que tiene probabilidad de cara $\frac{1}{K}$ ; dejar $X_1$ denota el número de cabezas que aparecen. Repitiendo este proceso $N$ el tiempo te da $N$ cuentas de cabezas $X_1,...,X_N$ . Entonces

\frac{norte}{| {1 \leq i \leq norte : X_{i} = 1} |} \approx mi

$\frac{N}{\Big|\big\{1 \leq i \leq N:X_i=1\big\}\Big|}\approx e$ cuando

N

$N$ y

K

$K$ son grandes.

Sang Chul Lee · Answer 4

Elegir $N$ enteros aleatorios $X_1,X_2,\ldots,X_N$ de manera uniforme e independiente en $\{1,2,\ldots,N\}$ , y luego cuenta el número $N_d$ de enteros distintos en esta lista, o de manera equivalente, sea

{norte}_{d} = # {X_{1}, X_{2}, \dots, X_{norte}} .

$N_d = \#\{X_1, X_2, \ldots, X_N\}.$

Entonces para grandes $N$ ,

\frac{norte}{norte - {norte}_{d}} \approx mi .

$\frac{N}{N-N_d} \approx e.$

(Es decir, el tamaño del conjunto aleatorio $\{X_1,\ldots,X_N\}$ es aproximadamente $(1-e^{-1})N$ .)

extraño · Answer 5

El número mínimo de variables aleatorias uniformes (0,1) requeridas para que su suma exceda $1$ es en promedio (exactamente) $e$ . Más generalmente, si $0 < a \le 1$ entonces el número mínimo de variables uniformes (0,1) requeridas para exceder $a$ es $e^a$ .

Dejar $X_1, X_2, X_3, \dots$ sea una secuencia de variables aleatorias iid Uniform(0,1), y sea $S_n = \sum_{i=1}^n X_i$ .

Como primer paso, afirmamos

\begin{matrix} (*) & PAG (S_{norte} \leq a) = \frac{a^{norte}}{norte!} \end{matrix}

$P(S_n \le a) =\frac{a^n}{n!} \tag{*}$ para

0 < a \leq 1

$0 < a \le 1$ y

n \geq 0

$n \ge 0$ . Demostración por inducción sobre

n

$n$ : El caso

n = 0

$n=0$ es trivial Suponer que

(*)

$(*)$ sostiene de algunos

n

$n$ . Entonces

PAG (S_{norte + 1} \leq a) = \int_{0}^{a} \frac{(a - X)^{norte}}{norte!} d X = \frac{1}{norte!} \cdot \frac{a^{norte + 1}}{norte} = \frac{a^{norte + 1}}{(norte + 1)!}

$P(S_{n+1} \le a) = \int_0^a \frac{(a-x)^n}{n!} \;dx = \frac{1}{n!} \cdot \frac{a^{n+1}}{n} = \frac{a^{n+1}}{(n+1)!}$ y la demostración está completa.

Ahora define $m(a)$ ser el menor valor de $n$ tal que $S_n > a$ . Tenemos $m(a) > n$ Exactamente cuando $S_n \le a$ , entonces

mi (metro (a)) = \sum_{norte \geq 0} PAG (metro (a) > norte) = \sum_{norte \geq 0} PAG (S_{norte} \leq a) = \sum_{norte = 0}^{\infty} \frac{a^{norte}}{norte!} = {mi}^{a}

$E(m(a)) = \sum_{n \ge 0} P(m(a) > n) = \sum_{n \ge 0} P(S_n \le a) = \sum_{n=0}^{\infty} \frac{a^n}{n!} = e^a$

Jim farned · Answer 6

Elija una secuencia de números aleatorios de $[0,1]$ , deteniéndose cuando el $n$ -ésima opción excede la $(n-1)$ -ésima elección. Repita, promediando el $(n-1)$ -ésimos valores. Este promedio se acercará $3-e$ .

¡Lindo! Sin embargo, ¿podría ser que esto se aproxime $e - 2$ en vez de $3 - e$ ?
no, estoy bastante seguro de que es 3-e. ¿Cómo conseguiste e-2?
¡Lo acabo de probar! Tenga en cuenta que el promedio sin duda será más que $1/2$ , ya que ese es el valor esperado del primer sorteo, y el valor generado siempre será al menos igual al del primer sorteo.
Pegaré por programa (en Python3), para que puedas ver si entendí mal tu algoritmo:
from random import random def s(): a = random() b = random() while b > a: a = bb = random() return a N = 1000000; imprimir (2 + suma (s () para i en el rango (N))/ N)
Esto genera un valor muy cercano a $e$ . Disculpas por el diseño, aparentemente no puedes escribir código en un comentario
El promedio será menor a .5, ya que ese será el valor esperado de las terminaciones en segunda opción; recuerda que estamos construyendo una secuencia decreciente .
Ah, ok, no lo leí con atención, ¡estaba construyendo una secuencia creciente ! Así que el promedio de sus muestras $s$ es el mismo que el promedio de mis muestras $1 - s$

tkf · Answer 7

Elegir $n$ números uniformemente en $[0,1]$ . Dejar $X_n$ ser el valor $x$ que escogiste, para lo cual $x^x$ toma el valor más pequeño. Entonces como $n\to\infty$ tenemos $\mathbb{E}X_n\to \frac 1e$ .

Prueba: Primero tenga en cuenta que $x^x$ tiene un mínimo en $x=\frac1e$ . También tenga en cuenta que ambas ramas de la función inversa a $x^x, x\in[0,1]$ son continuos. Para $\epsilon>0$ elegir $\delta>0$ tal que $x^x<\left(\frac1e\right)^\frac1e+\delta\implies |x-\frac1e|<\epsilon$ . Para suficientemente grande $n$ , la probabilidad de que ninguno de los números muestreados satisfaga $x^x<\left(\frac1e\right)^\frac1e+\delta$ es menos que $\epsilon$ y si uno de los números muestreados satisface esto, entonces $X_n$ también lo hará, así que $|X_n-\frac1e|<\epsilon$ . De este modo

(\frac{1}{mi} - ϵ) (1 - ϵ) < mi X_{norte} \leq (\frac{1}{mi} + ϵ) (1 - ϵ) + ϵ .

$(\frac1e-\epsilon)(1-\epsilon)<\mathbb{E}X_n\leq (\frac1e+\epsilon)(1-\epsilon)+\epsilon.$

ordenar el $x^x$ se reduce a la aritmética entera:

Para ordenar el $x^x, y^y$ uno puede intercalarlos entre racionales:

\frac{a_{X}}{b_{X}} \leq X \leq \frac{C_{X}}{d_{X}}, \frac{a_{y}}{b_{y}} \leq y \leq \frac{C_{y}}{d_{y}}, a_{X}, b_{X}, C_{X}, d_{X} \in norte,

$\frac{a_x}{b_x}\leq x\leq\frac{c_x}{d_x},\qquad \frac{a_y}{b_y}\leq y\leq\frac{c_y}{d_y},\qquad a_x,b_x,c_x,d_x\in \mathbb{N},$ de modo que

F (\frac{a_{X}}{b_{X}}), F (\frac{C_{X}}{d_{X}}) \leq F (\frac{a_{y}}{b_{y}}), F (\frac{C_{y}}{d_{y}}) o r F (\frac{a_{X}}{b_{X}}), F (\frac{C_{X}}{d_{X}}) \geq F (\frac{a_{y}}{b_{y}}), F (\frac{C_{y}}{d_{y}}),

$f(\frac{a_x}{b_x}),f(\frac{c_x}{d_x})\leq f(\frac{a_y}{b_y}),f(\frac{c_y}{d_y}) \qquad {\rm or}\quad f(\frac{a_x}{b_x}),f(\frac{c_x}{d_x})\geq f(\frac{a_y}{b_y}),f(\frac{c_y}{d_y}),$ dónde

f (x) = x^{x}

$f(x)=x^x$ .

Comparar $f(\frac{u}{v})$ y $f(\frac{z}{w})$ con $u,v,w,z\in\mathbb{N}_{>0}$ , tenga en cuenta que

{(\frac{tu}{v})}^{\frac{tu}{v}} \leq {(\frac{z}{w})}^{\frac{z}{w}} ⟺ {(\frac{tu}{v})}^{tu w} \leq {(\frac{z}{w})}^{z v} ⟺ {tu}^{tu w} w^{z v} \leq z^{z v} v^{tu w} .

$\left(\frac{u}{v}\right)^{\frac{u}{v}}\leq \left(\frac{z}{w}\right)^{\frac{z}{w}}\iff \left(\frac{u}{v}\right)^{{u}{w}}\leq \left(\frac{z}{w}\right)^{{z}{v}}\iff u^{uw}w^{zv}\leq z^{zv}v^{uw}.$

Estimación del valor de eee usando una función aleatoria

J wang

nicomezi

Pedro O.

Respuestas (7)

Jean-Claude Arbaut

Un lector rural

J wang

Jean-Claude Arbaut

capitán jirafa

Misha Lavrov

Jean-Claude Arbaut

jukka kohonen

Mike Earnest

jukka kohonen

mateo h

Sang Chul Lee

extraño

Jim farned

doetoe

Jim farned

doetoe

doetoe

doetoe

doetoe

Jim farned

doetoe

tkf

¿Por qué los límites de esta integral no consideran ambas igualdades?

¿Cómo demuestro que etA=limn→∞((I−tAn)−1)netA=limn→∞((I−tAn)−1)ne^{tA}=\lim_{n\rightarrow\infty} (( Yo-\frac{tA}{n})^{-1})^n?

∑∞n=0ak∑n=0∞ak\sum_{n=0}^\infty a_k converge absolutamente y ∑∞n=0bk∑n=0∞bk\sum_{n=0}^\infty b_k converge ¿Hace esto implica que ∑∞n=0bksin(ak)∑n=0∞bksin⁡(ak)\sum_{n=0}^\infty b_k\sin(a_k) converge?

¿Determinar los límites de una integral triple?

Estimación de la desviación estándar de la población con la desviación estándar de la muestra

¿Qué es la varianza muestral de la varianza muestral y qué es la distribución muestral teórica?

Aplicaciones geométricas de números complejos

La paradoja de la escalera, o por qué π≠4π≠4\pi\ne4

Rotar un punto en un círculo con radio y posición conocidos

¿Usando pdf X para encontrar pdf Y, y deduciendo los límites en los que la función de densidad de probabilidad de Y es válida?