¿Cuál es el número esperado de números generados aleatoriamente en el rango [a, b] requerido para alcanzar una suma$\geq X$?

Question

Somos la generación de números aleatorios (enteros) en el rango de $[a, b]$. Todos los valores son igualmente probables.

Vamos a seguir para generar números aleatorios en este rango, y se suman los sucesivos valores hasta que su suma es mayor o igual a un número $X$.

¿Cuál es el número esperado de rollos para llegar al menos a $X$?

Ejemplo:

a = 1000
b = 2000
X = 5000

Value 1: 1257 (total sum so far = 1257)
Value 2: 1889 (total sum so far = 3146)
Value 3: 1902 (total sum so far = 5048; all done)

Por lo que tomaron $3$ rollos para llegar a $\geq5000$. Intuitivamente, podemos decir que no va a tomar más de $5$ rollos si cada rollo es $1000$. También podemos decir que no tendrá menos de $3$ rollos si cada rollo se $2000$. Así que es lógico que en el ejemplo anterior, se espera que el número de rollos se encuentra en algún lugar entre el $3$ e $5$.

¿Cómo podría esto ser resuelto en el caso general, para valores arbitrarios $[a, b]$ e $X$? Ha sido bastante tiempo desde la última vez que tomó las estadísticas, así que me he olvidado de cómo trabajar con discretas variables aleatorias y el valor esperado.

Answer 1

Deje $T$ ser el número de veces que se tarda en alcanzar la $X$. Calculamos el $E[T]$ través $E[T]=\sum_{t=0}^\infty P(T>t)$.

Con el fin de tener $T>t$, la suma de los primeros a$T$ de las muestras debe ser de menos de $X$. Deje $S_i$ es el valor de la $i^{th}$ de la muestra. A continuación, un experimento en el $T>t$ tiene el primer $t$ valores de la satisfacción de $$ S_1+S_2+\dots+S_t<X,\\ un\le S_i\le b $$ Dejando $E=X-1-(S_1+\dots+S_t)$, obtenemos $$ S_1+\dots+S_t+E=X-1,\\ un\le S_i\le b,\\ E\ge 0 $$ El número entero de soluciones para el anterior sistema de ecuaciones y desigualdades en las variables de $S_i$ e $E$ puede ser calculada a través de la generación de funciones. El número de soluciones es el coeficiente de $s^{X-1}$ en $$ (s^a+s^{+1}+\dots+s^b)^t(1-s)^{-1}=s^{a}\cdot(1-s^{b-a+1})^t(1-s)^{-(t+1)} $$ Después de un montón de trabajo, este coeficiente es igual a $$ \sum_{k=0}^{\frac{X-1-ta}{b-a+1}} (-1)^k\binom{t}k\binom{t+X-1-ta-(b-a+1)k}{t} $$ Finalmente, llegamos \begin{align} E[T] &=\sum_{t=0}^{X/a} P(T>t) \\&=\boxed{\sum_{t=0}^{X/a} (b-a+1)^{-t}\sum_{k=0}^{\frac{X-1-ta}{b-a+1}}(-1)^k\binom{t}k\binom{t+X-1-ta-(b-a+1)k}{t}} \end{align} Tenga en cuenta que cuando se $a=0$, la suma de $t$ va a ir de $t=0$ a $\infty$, por lo que sólo puede ser calculada aproximadamente con un ordenador. Sin embargo, esta advertencia puede ser evitado mediante la siguiente observación; si $T(a,b,X)$ es el tiempo de espera para llegar a $X$ sumas de $\operatorname{Unif}\{a,a+1,\dots,b\}$ variables aleatorias, a continuación, $E(T(0,b,X))=\frac{b+1}bE(T(1,b,X))$.

Cuando escribo $\sum_{k=0}^a f(k)$ e $a$ no es un número entero, lo que quiero decir es $\sum_{k=0}^{\lfloor a \rfloor}f(k)$.

Answer 2

Bien, ahora que el riguroso argumento que he mencionado. De crédito a finales de la década de Kent Merryfield para trazar el argumento limpiamente, aunque estoy seguro de que he contribuido en la etapa de desarrollo. AoPS enlace

Supongamos que agregar copias independientes de un razonablemente agradable no negativo variable aleatoria continua con densidad de $f$, la media de $\mu$, y la varianza $\sigma^2$ hasta superar algunos fijos $y$. Como $y\to\infty$, se espera que el número de $g(y)$ de estas variables necesarias para exceder $y$es $$g(y)=\boxed{\frac{y}{\mu}+\frac12+\frac{\sigma^2}{2\mu^2}+o(1)}$$ En el caso de los uniformes $[a,b]$ distribución de este problema, que es $g(y)=\frac{2y}{a+b}+\frac12+\frac{(b-a)^2}{6(b+a)^2}+o(1)$.

Para probar esto, condición en la primera copia de la variable. Si tiene el valor de $x$, se espera que el número de términos adicionales necesarios es $g(y-x)$. Agregar el uno para el término nos acondicionado, integrar en contra de la densidad, y $$g(y)=1+\int_0^y f(x)g(y-x)\,dx$$ Esta es una convolución. Para resolver en algo podemos trabajar con más facilidad, aplicar un método de transformación. Específicamente, en este caso con una convolución más de $[0,\infty]$, la transformada de Laplace es el más apropiado. Si $F(s)=\int_0^{\infty}e^{-sx}f(x)\,dx$ e $G(s)=\int_0^{\infty}e^{-sy}g(y)\,dy$, entonces, transformar la ecuación integral para $g$, obtenemos $$G(s)=\frac1s+F(s)G(s)$$ Resolver para $G$, y $$G(s)=\frac1{s(1-F(s))}$$ Ahora, tenga en cuenta que $F$ es esencialmente el momento de generación de la función de la variable con la densidad de $f$; hay un cambio de signo, pero de cualquier modo, es el mismo. Como tal, tiene el poder de expansión de la serie $$F(s)=1-\mu s+\frac{\mu^2+\sigma^2}{2\mu^2}s^2 + O(s^3)$$ cerca de cero. Entonces $$G(s)=\frac1{\mu s^2-\frac{\mu^2+\sigma^2}{2}s^3+O(s^4)} = \frac1{\mu}s^{-2}+\frac{\mu^2+\sigma^2}{2\mu^2}s^{-1}+Q(s)$$ donde $Q(s)$ tiene una singularidad removible en cero. También, desde el "razonablemente buena" condición, $Q$ decae en $\infty$ Cómo de rápido? Así, mientras la densidad de $f$ está acotada arriba por algunos exponencial, sus transformar $F$ va a cero, como se $s\to\infty$. A continuación, $G(s)=\frac1{s(1-F(s)}=O(s^{-1})$ como $s\to\infty$; sustrae los otros dos términos, $Q(s)=O(s^{-1})$ como $s\to\infty$.

Ahora, tomamos la transformada inversa de Laplace de $G$. La inversa de la transformación de $s^{-2}$ es $y$ y la inversa de la transformación de $s^{-1}$ es $1$, por lo que existe la $\frac{y}{\mu}+\frac{\sigma^2+\mu^2}{2\sigma^2}$ términos de la expansión de la $g$. Para el resto $Q$, llevamos a cabo la integral fórmula $q(y)=\frac1{2\pi}\int_{\infty}^{\infty}Q(it)e^{ity}\,dt$. De nuevo por la amabilidad $f$ - un cuadrado integrable densidad va a hacer - esto decae a cero, como se $y\to\infty$ (de Riemann-Lebesgue lema).

Y ahora, es el momento para obtener más concreto. Nuestro ejemplo original fue una distribución uniforme en $[a,b]$, que tiene una media $\mu=\frac{a+b}{2}$ y la varianza $\sigma^2=\frac{(b-a)^2}{12}$. Que da $$g(y)=\boxed{\frac{2y}{a+b}+\frac12+\frac{(b-a)^2}{6(a+b)^2}+o(1)}$$ También, podemos ser más explícito; las transformaciones se $F(s)=\frac1{(b-a)s}(e^{-as}-e^{-bs})$y $$G(s)=\frac{1}{s-\frac1{b-a}e^{-as}+\frac1{b-a}e^{-bs}}$$ Esta $G$ es analítica en la mitad derecha del plano-excepto para la pole en cero, y es comparable a $\frac1s$ a $\infty$ en todas las direcciones en que la mitad de plano. El resto término $Q$ es lo suave y se desintegra como $\frac1s$ a lo largo del eje imaginario, por lo que su inversa transformar $q$ tendrá un salto de discontinuidad (en cero, donde pasa de cero a $1$) y se pudren rápidamente.

Si queremos una forma explícita para $g$ - es un desastre. Tres diferentes exponenciales en que el denominador empuja esta lejos del estándar de las tablas de transformaciones, y la división de éste como una serie geométrica presenta demasiados términos. Voy a tratar de escribir algo que de todos modos: \begin{align*}G(s) &= \frac{1}{s-\frac1{b-a}e^{-as}+\frac1{b-a}e^{-bs}}\\ &= s^{-1} +\frac{s^{-2}}{b-a}\left(e^{-as}-e^{-bs}\right)+\frac{s^{-3}}{(b-a)^2}\left(e^{-as}-e^{-bs}\right)^2+\cdots\\ &= \sum_{n=0}^{\infty} \frac{s^{-n-1}}{(b-a)^n}\left(e^{-as}-e^{-bs}\right)^n\\ &= \sum_{n=0}^{\infty}\sum_{k=0}^n\frac{s^{-n-1}}{(b-a)^n}\binom{n}{k}(-1)^k e^{-s(kb+(n-k)a)}\end{align*} Ahora, en la tabla de transformadas de Laplace que estoy usando, hay una entrada "retrasado" $n$th de potencia con cambio de frecuencia"; la transformación de $(y-\tau)^n e^{-\alpha(y-\tau)}u(y-\tau)$ (donde $u$ es la unidad de función de paso) es $n!e^{-\tau s}(s+\alpha)^{-n-1}$. A partir de este y la linealidad de la transformada, obtenemos $$g(y) = \sum_{n=0}^{\infty}\sum_{k=0}^n[y-(kb+(n-k)a)]^n\frac{(-1)^k}{k!(n-k)!}u[t-(kb+(n-k)a)]$$ $$g(y) = \sum_{j=0}^{\infty}\sum_{k=0}^{\infty} (-1)^k\frac{[y-(ja+kb)]^{j+k}}{j!k!}u[t-(kb+(n-k)a)]$$ Para cualquier $y$, esto es una suma finita, que sólo suma los términos para los que $ja+kb \le y$. Es horrible para el uso en la práctica, ya que consiste en la suma y resta de números grandes para conseguir algo relativamente pequeña.

El $a=0$ caso nos permite dividir las cosas de manera diferente, y sale con algo que realmente sea razonablemente práctico. Siga el enlace en el inicio del post, si la quieres ver.

Answer 3

El número esperado está dominado por el plazo basado en la media de $\frac{2X}{a+b}$ - , pero podemos hacer algo mejor que eso. Como $X\to\infty$, $$E(n) = \frac{2X}{a+b}+\frac{2(a^2+ab+b^2)}{3(a^2+2ab+b^2)}+o(1)$$ Por qué? Considerar el exceso. En el límite de $X\to\infty$, la frecuencia de golpear a un punto en particular los enfoques de una densidad uniforme de $\frac{2}{b+a}$. Para los puntos en $[X,X+a)$, esto es cierto para ser la primera vez que hemos superado $X$, por lo que la función de densidad para que el primer tiempo superior a $X$ es de aproximadamente $\frac{2}{b+a}$ en ese rango. Para $t\in[X+a,X+b)$, la probabilidad de que es la primera vez que excedan $X$ es $\frac{X+b-t}{b-a}$; necesitamos el último término se añaden al menos $t-X$. Multiplicar por $\frac{2}{b+a}$, y la función de densidad por primera vez superior a $X$ es de aproximadamente $\frac{2(X+b-t)}{b^2-a^2}$ a $[X+a,X+b)$. Para $t<X$ o $t\ge X+b$, por supuesto, la densidad es igual a cero. Gráficamente, esta densidad es una pieza rectangular seguido por un triángulo inclinado a cero. Ahora, el valor esperado de la primera suma sea mayor que la de $X$ es de aproximadamente $$\int_{X}^{X+a}\frac{2t}{b+a}\,dt+\int_{X+a}^{X+b}\frac{2t(X+b-t)}{b^2-a^2}\,dt$$ $$=\frac{2a(2X+a)}{2(b+a)}+\frac{2(b-a)(2X+a+b)(X+b)}{2(b^2-a^2)}-\frac{2(b-a)((X+a)^2+(X+a)(X+b)+(X+b)^2)}{3(b^2-a^2)}$$ $$=\frac{6aX+3a^2+6X^2+3(a+3b)X+3ab+3b^2-6X^2-6(a+b)X-2(a^2+ab+b^2)}{3(b+a)}$$ $$=\frac{3(a+b)X+a^2+ab+b^2}{3(b+a)}=X+\frac{a^2+ab+b^2}{3(a+b)}$$ Se Divide por el promedio de $\frac{a+b}{2}$ de cada término de la suma, y tenemos una expresión asintótica para $E(n)$.

Este no es un argumento riguroso. Si yo quería hacer eso, me gustaría llevar a cabo algo así como el momento de generación de función.

Answer 4

Dado $m$ variables discretas en el rango de $[a,b]$, el número de maneras de obtener una suma $s$ de ellos corresponde a $$ \eqalign{ Y N_b (s - ma,d,m) = \cr y = {\rm No}{\rm .}\,{\rm de}\,{\rm soluciones}\,{\rm}\;\left\{ \matriz{ un \le {\rm integer}\;y_{\,j} \le b \hfill \cr y_{\,1} + y_{\,2} + \; \cdots \; + y_{\,m} = s \hfill \cr} \right.\quad = \cr y = {\rm No}{\rm .}\,{\rm de}\,{\rm soluciones}\,{\rm}\;\left\{ \matriz{ {\rm 0} \le {\rm integer}\;x_{\,j} \le b - a = d \hfill \cr x_{\,1} + x_{\,2} + \; \cdots \; + x_{\,m} = s - ma \hfill \cr} \right. \cr} $$ donde $N_b$ está dado por $$ \bbox[lightyellow] { N_b (s-ma,d,m)\quad \left| {\;0 \leqslant \text{números enteros }s,m,d} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s-ma}{d+1}\, \leqslant \,m} \right)} {\left( { - 1} \right)^k \binom{m}{k} \binom { s -ma+ m - 1 - k\left( {d + 1} \right) } { s-ma - k\left( {d + 1} \right)}\ } } \etiqueta{1} $$ como ampliamente explicado en este post.
También vamos a notar la propiedad de simetría de $N_b$ $$ N_b (s - ma,d,m) = N_b (md - \left( {s - ma} \right),d), m) = N_b (mb - s,d,m) $$

La probabilidad de obtener exactamente la suma de $s$ en $m$ rollos es por lo tanto $$ \bbox[lightyellow] { \eqalign{ & p(s\;;\,m,a,b) = {{N_b (s - ma,d,m)} \over {\left( {d + 1} \right)^{\,m} }} = {{N_b (mb - s,d,m)} \over {\left( {d + 1} \right)^{\,m} }} = \cr Y = {1 \over {\left( {d + 1} \right)^{\,m} }} \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,{{s - ma} \over {d + 1}}\, \le \,m} \right)} { \left( { - 1} \right)^k \binom{m}{k} \binom{ s -ma+ m - 1 - k\left( {d + 1} \right) }{ s-ma - k\left( {d + 1} \right)} } = \cr Y = {1 \over {\left( {d + 1} \right)^{\,m} }} \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,{{mb - s} \over {d + 1}}\, \le \,m} \right)} { \left( { - 1} \right)^k \binom{m}{k} \binom{ mb-s+ m - 1 - k\left( {d + 1} \right) }{ mb-s - k\left( {d + 1} \right)} } \cr} } \etiqueta{2} $$ y la suma de $p$ sobre $s$ es de hecho uno.

La probabilidad de $p$ rápidamente converge, por el Teorema Central del Límite, a la de Gauss en la variable $s$ $$ \cal N\left( {\mu\sigma ^{\,2} } \right)\quad \left| \matriz{ \;\mu = m\left( {{d \over 2} +} \right) = m\left( {{{a + b} \over 2}} \right) \hfill \cr \;\sigma ^{\,2} = m{{\left( {d + 1} \right)^{\,2} - 1} \más de {12}} \hfill \cr} \right. $$ ver por ejemplo este post.

Es fácil demostrar (por el "doble convoluton" de binomios) que la versión Acumulativa, es decir, la probabilidad de obtener una suma $\le S$, es $$ \bbox[lightyellow] { \eqalign{ & P(S\;;\,m,a,b) = {1 \over {\left( {d + 1} \right)^{\,m} }}\sum\limits_{0\, \le \,\,s\,\, \le \,S} {N_b (s - ma,d,m)} = \cr Y = {1 \over {\left( {d + 1} \right)^{\,m} }}\sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,{{s - ma} \over {d + 1}}\, \le \,m} \right)} { \left( { - 1} \right)^k \binom{m}{k} \binom{S - ma + m - k\left( {d + 1} \right) }{S - ma - k\left( {d + 1} \right) } } \cr & \aprox {1 \over 2}\left( {1 + {\rm fer}\left( {\sqrt 6 {{S + 1/2 - m\left( {a + b} \right)/2} \over {\left( {b - a + 1} \right)\sqrt m \;}}} \right)} \right) \cr} } \etiqueta{3} $$

La siguiente parcela permite apreciar la buena aproximación proporcionada por el asymptotics incluso en el relativamente pequeño de los valores de los parámetros involucrados.

Que se basa,
la probabilidad de que se alcancen o superen un predefinidos suma $X$ a $m$-th rollo y no antes
está dada por la probabilidad de que
llegamos $S<X$ como la suma de los primeros a$m-1$ rollos, y luego de que el $m$-th uno tiene un valor de $s$ tal que $X \le S+s$,
o, lo que es evidentemente el mismo, por
la probabilidad de contraer $X \le S$ en $m$ rollos de menos la probabilidad de obtener el mismo en $m-1$ rollos.

Que es, en conclusión $$ \bbox[lightyellow] { \eqalign{ Y Q(m\;;\,X,a,b)\quad \left| \matriz{ \;1 \le m \hfill \cr \;0 \le X \hfill \cr \;0 \le \le b \hfill \cr} \right.\quad = \cr Y = 1 - P(X - 1\;;\,m,a,b) - 1 + P(X - 1\;;\,m - 1,a,b) = \cr Y = P(X - 1\;;\,m - 1,a,b) - P(X - 1\;;\,m,a,b) \cr} } \etiqueta{4} $$ y la suma de $Q$ sobre $m$ correctamente cheques a uno.

Ejemplo

a) Para valores pequeños de a$X,a,b$ la expresión exacta para $Q$ (4) da los resultados que se muestran (por ejemplo, $a=1, \; b=4$) que parecen ser correctas, y la fila sumas correctamente compruebe $1$.

b) Para grandes valores de los parámetros, como en el ejemplo $a=1000,\; b=2000, \; X=5000$ vamos a utilizar la versión asintótica de $Q$ que da los resultados graficados a continuación