En el momento n, elegir al azar un número natural ≤n. ¿Cuánto tiempo hasta que un único número es elegido tres veces?

Question

Para aclarar, el número ≤n es elegido uniformemente al azar en cada paso, y n elige a partir de los números naturales, comenzando por el 1.

Deseo para determinar el valor esperado de $n$ a que un número natural es elegido tres veces (por primera vez). (También me gustaría idealmente gustaría saber cómo calcular E(un número escogido $y$ veces))

He calculado $\Pr(\text{hitting a number thrice at } n=x)$ para algunos valores bajos, pero rápidamente se convierte en un montón para hacer a mano.

\begin{align*} \Pr(n=1) &= \Pr(n=2) = 0 \\ \Pr(n=3) &= 1/6 \\ \Pr(n=4) &= 1/6 \\ \Pr(n=5) &= 19/120 \end{align*}

La inspiración para esta pregunta se refiere a la tarjeta de juego de Hearthstone y una tarjeta en particular de interacción. Ver http://hearthstone.gamepedia.com/Grim_Patron http://hearthstone.gamepedia.com/Bouncing_Blade

El título de esta pregunta y la redacción utilizada en todo no es como yo concibe a la pregunta, sino una reformulación que mjqxxxx publicado.

Answer 1

Resulta que el numéricos de los resultados sobre el $\mathbb{E}[N_3]$ por David E no es una coincidencia, es exacto! $$\mathbb{E}[N_3] = \frac{1}{1-\sin(1)}$$

Deje $X_1, X_2, \ldots $ ser una secuencia de variables aleatorias. Para cada una de las $n$, supondremos $X_n$ tomar el valor del conjunto $\langle n \rangle \stackrel{def}{=}\{ 1, 2, \ldots, n \}$ con probabilidad uniforme.

Después de la $n^{th}$ iteración, tenga en cuenta las siguientes variables aleatorias:

• $Y_{m} = \# \{ i \in \langle n \rangle : X_i = m \}$ ser el número de veces que el número de $m$ es elegido.
• $Z_{m} = \# \{ i \in \langle n \rangle : Y_i = m \}$ el número de números que ha sido escogida $m$ veces.

Para aquellos de configuración, donde ninguno de los número ha sido elegido más de dos veces, $Z_{k}$ no son independientes el uno del otro. De hecho, si conocemos $Z_0 = p$, vamos a tener

$$Z_1 = n - 2p,\quad Z_2 = p\quad\text{ and }\quad Z_k = 0, \forall k > 2$$

Para este tipo de configuración, es claro en el $(n+1)^{th}$ iteración, la probabilidad de que

• $Z_0$ permanece inalterado es $\frac{p+1}{n+1}$.
• $Z_0$ aumenta por $1$$\frac{n-2p}{n+1}$.
• algunos número elegido $3$ veces es $\frac{p}{n+1}$.

Si definimos

• $f_{n,p} = \mathbb{P}\left[ Z_0 = p, Z_1 = 2n-p, Z_2 = p, Z_k > 0 \land \forall k > 2 \right]$
• $f_n(z) = \sum_{p=0}^n f_{n,p} z^p$,
• $F(z,t) = 1 + \sum_{n=1}^\infty f_n(z) t^n$

Nos encontramos con $f_{n,p}$ satisfacer la siguiente relación de recurrencia:

$$ f_{n+1,p} = \frac{p+1}{n+1}f_{n,p} + \frac{n-2(p-1)}{n+1}\begin{cases} f_{n,p-1}, & p > 0\\0, &p = 0\end{casos}\\ \implica (n+1) f_{n+1}(z) = \left\{ \left(1 + z\frac{\partial}{\partial z}\right) + z\a la izquierda( n - 2z\frac{\partial}{\partial z}\right) \right\} f_n(z) $$ Multiplicar cada término por $t^n$ y suma y aviso de $f_1(z) = 1$, podemos encontrar:

$$\begin{align} & \frac{\partial}{\partial t} ( F(t,z) - 1 - t ) = \left\{ \left(1 + z\frac{\partial}{\partial z}\right) + z\left( t\frac{\partial}{\partial t} - 2z\frac{\partial}{\partial z}\right) \right\} ( F(z,t) - 1)\\ \iff & \left\{ (1 - zt)\frac{\partial}{\partial t} - (1 + z(1-2z)\frac{\partial}{\partial t}\right\} F(z,t) = 0\\ \iff & \left\{ (1 - zt)\frac{\partial}{\partial t} - z(1-2z)\frac{\partial}{\partial t}\right\} \left( \frac{z}{1-2z} F(z,t) \right) = 0 \end{align} $$ Utilizando el método de las características, se puede mostrar que la solución general de la última PDE tiene la forma

$$F(z,t) = \frac{1-2z}{z} \varphi\left(\frac{1-\sqrt{1-2z}}{1+\sqrt{1-2z}}e^{t\sqrt{1-2z}}\right)$$ donde $\varphi(\cdots)$ es una función arbitraria. Podemos determinar $\varphi(\cdots)$ por ajuste a $t = 0$, tenemos

$$\frac{1-2z}{z} \varphi\left(\frac{1-\sqrt{1-2z}}{1+\sqrt{1-2z}}\right) = F(z,0) = 1$$ Después de un poco de álgebra, obtenemos $$F(z,t) = \frac{4u^2 e^{tu}}{((1+u) - (1-u) e^{tu})^2} \quad\text{ donde }\quad u = \sqrt{1-2z} $$

Aviso para cada $n$, $f_n(1) = \sum_{p=0}^n f_{n,p}$ es la probabilidad de que ninguno de los números ha sido elegido más de dos veces. Esto significa $f_{n-1}(1) - f_n(1)$ es la probabilidad de que algunas de las "nuevas" número elegido en el tercer momento. Así que el número que queremos es

$$\mathbb{E}[N_3] = (1-f_1(1)) + \sum_{n=2}^\infty n (f_{n-1}(1) - f_{n}(1)) = 1 + \sum_{n=1}^\infty f_n(1) = F(1,1)$$

Sustituir este regreso a nuestro expresión de $F(z,t)$, obtenemos

$$\begin{align} \mathbb{E}[N_3] & = \frac{4i^2 e^i}{((1+i) - (1-i) e^i)^2} = \frac{1}{1-\sin(1)}\\ & \approx 6.307993516443740027513521739824160128971342... \end{align} $$ Hay otras estadísticas interesantes se pueden recoger a partir de $F(z,t)$. Por ejemplo, la generación de la función para la "supervivencia" de la probabilidad $f_n(1)$ es

$$P_{survival}(t) \stackrel{def}{=} 1 + \sum_{n=0}f_n(1)t^n = F(1,t) = \frac{1}{1-\sin(t)}$$

y que para que la probabilidad de que "la muerte en $3^{rd}$ huelga" en el paso $n$ es

$$\begin{align} P_{3^{rd} strike}(t) & \stackrel{def}{=} (1-f_1(1)) t + \sum_{n=2}^\infty (f_{n-1}(1) - f_{n}(1)) t^n\\ & = (t - 1) P_{survival}(t) + 1 = \frac{t-1}{1-\sin(t)} + 1 \end{align}$$

Si un lanzamiento de la última expresión a la CAS y preguntar para calcular la expansión de Taylor, uno conseguir

$$\begin{align} P_{3^{rd} strike}(t) = & \frac{1}{6}t^3 + \frac{1}{6}t^4 + \frac{19}{120}t^5 + \frac{47}{360}t^6 +\frac{173}{1680}t^7 + \frac{131}{1680} t^8 +\frac{20903}{362880}t^9\\ & +\frac{75709}{1814400}t^{10} + \frac{1188947}{39916800}t^{11} +\frac{2516231}{119750400}t^{12} + \cdots \end{align}$$ El coeficiente de $t^k$ coincide con los números de $Pr[N_3 = k]$ aparece en otra respuesta.

Actualización 1

Vamos a ser Don Quijote y desafiar el más difícil problema de la informática $\mathbb{E}[N_y]$$y > 3$.

Similar a $y = 3$, se puede configurar un PDE para la generación de funciones. Sin embargo, si sólo desea $\mathbb{E}[N_y]$, no es necesario para resolver el PDE completamente. Uno puede usar el método de las características y expresar $\mathbb{E}[N_y]$ en cuanto a las soluciones de algunos de ODE.

La derivación es un lío. Me ahorraré detalles aburridos y aquí está la receta:

1. El caso de $y = 4$ es sencillo, uno puede mostrar que $$\mathbb{E}[N_4] = \frac{\rho^3 + 3\rho + 2}{6} \;\;\text{ donde }\;\; \rho \;\;\text{ satisface }\;\; 1 = \int_1^\rho \frac{6ds}{s^3 + 3s + 2} $$

2. Para general $y$, la instalación de un sistema de educación a distancia en $y+1$ varibles $\psi, t, z_1, z_2, \ldots, z_{y-1}$: $$ \frac{d\psi}{d\tau} = z_1 \psi\quad \frac{dt}{d\tau} = t z_1-1\quad \quad\text{ y }\quad \frac{dz_k}{d\tau} = \begin{cases} -z_k(z_k - z_{k+1}), & k < y-1\\ -z_k^2, & k = y-1 \end{casos} $$ Si uno empezar a integrar este sistema de educación a distancia utilizando los valores iniciales $$( \psi, t, z_1, \ldots, z_{y-1} ) = (1, 1, \ldots, 1 )\quad\text{ at }\quad \tau = 0$$ hasta el punto de $\rho$ donde$t(\rho) = 0$, $\psi(\rho)$ será igual a la número de $\mathbb{E}[N_y]$ buscamos.

Siguientes son algunos de los resultados numéricos. La etiqueta $\verb/R1/$ $\verb/R2/$ indican que la receta ha sido utilizado para calcular el resultado. El número detrás de la etiqueta $\verb/R2/$ es el máximo de tiempo utilizado en numéricamente la integración.

$$\begin{array}{c:l:l} y & \mathbb{E}[N_y] & \verb/methodology/\\ \hline 2 & 6.30799351644374 & \verb/exact/ = \frac{1}{1-\sin 1}\\ 2 & 6.3079930650 & \verb/R2 /(10^{-4})\\ 2 & 6.3079935164 & \verb/R2 /(10^{-6})\\ \hline 3 & 13.77250982352477 & \verb/R1/ \\ 3 & 13.7725078084 & \verb/R2 /(10^{-4})\\ 3 & 13.7725098234 & \verb/R2 /(10^{-6})\\ \hline 4 & 29.1475420469 & \verb/R2 /(10^{-4})\\ 4 & 29.1475467696 & \verb/R2 /(10^{-6})\\ \hline 5 & 60.5714357748 & \verb/R2 /(10^{-4})\\ 5 & 60.5714459868 & \verb/R2 /(10^{-6})\\ \hline 6 & 124.4243032167 & \verb/R2 /(10^{-4})\\ 6 & 124.4243208364 & \verb/R2 /(10^{-6}) \end{array} $$

Como se puede ver, $\mathbb{E}[N_y]$ le parece a aproximadamente el doble por cada incremento de $y$.

Actualización 2

Resulta que parte de la necesidad de la educación a distancia en la Actualización 1 se puede resolver de forma explícita.
Para cualquier $y \ge 3$$k = 1,2,\ldots,y-1$, tenemos

$$z_{k}(s) = \frac{e_{y-k-1}(s)}{e_{y k}(s)} \quad\text{ donde }\quad e_m(x) = \sum_{k=0}^{m} \frac{x^k}{k!}$$ La nueva simplificado receta es

$$\mathbb{E}[N_y] = e_{y-1}(\rho) \quad\text{ donde }\quad \rho \quad\text{ es raíz de la ecuación }\quad 1 = \int_0^\rho \frac{ds}{e_{y-1}(s)} $$ Siguiente es algunos resultados numéricos calculados utilizando esta nueva receta. Todos los números se ha truncado a 6 decimales para facilitar la comparación. Como se puede ver a partir de las $3^{rd}$ columna $2^y$ es razonable decente $1^{st}$ orden de aproximación para $\mathbb{E}[N_y]$ $y$ crece.

$$\begin{array}{r:r:l} y & \mathbb{E}[N_y] & \mathbb{E}[N_y]/2^y\\ \hline 3 & 6.307993 & 0.788499\\ 4 & 13.772509 & 0.860781\\ 5 & 29.147546 & 0.910860\\ 6 & 60.571445 & 0.946428\\ 7 & 124.424320 & 0.972065\\ 8 & 253.615739 & 0.990686\\ 9 & 514.170899 & 1.004240\\ 10& 1038.407593 & 1.014069\\ 11& 2091.272044 & 1.021128\\ 12& 4202.932580 & 1.026106\\ 13& 8433.748402 & 1.029510\\ 14& 16903.678242 & 1.031718\\ 15& 33849.909944 & 1.033017 \end{array} $$

Answer 2

Reprenting la salud de cada Patrono por $y$, y la cantidad de interés por $N_y$, me sale: \begin{align*} \Pr[ N_3 = 1 ] &= 0 \\ \Pr[ N_3 = 2 ] &= 0 \\ \Pr[ N_3 = 3 ] &= 1/6 \\ \Pr[ N_3 = 4 ] &= 1/6 \\ \Pr[ N_3 = 5 ] &= 19/120 \\ \Pr[ N_3 = 6 ] &= 47/360 \\ \Pr[ N_3 = 7 ] &= 173/1680 \\ \Pr[ N_3 = 8 ] &= 131/1680 \\ \Pr[ N_3 = 9 ] &= 20903/362880 \\ \Pr[ N_3 = 10 ] &= 75709/1814400 \\ \Pr[ N_3 = 11 ] &= 1188947/39916800 \\ \Pr[ N_3 = 12 ] &= 2516231/119750400 \\ \Pr[ N_3 = 13 ] &= 3386161/230630400 \\ \Pr[ N_3 = 14 ] &= 147882737/14529715200 \\ \Pr[ N_3 = 15 ] &= 1832969507/261534873600 \\ \Pr[ N_3 = 16 ] &= 570448019/118879488000 \\ \Pr[ N_3 = 17 ] &= 1162831155151/355687428096000 \\ \Pr[ N_3 = 18 ] &= 1014210646079/457312407552000 \\ \Pr[ N_3 = 19 ] &= 4674810997597/3119105138688000 \\ \end{align*}

$\mathbb{E}[N_3] = 6.30799351644$ (calculado con $x < 100$)

Este se calcula de forma recursiva por el ahorro de la cantidad de clientes con 2,1,0 hits, respectivamente, en una tupla (a,b,c), y el cálculo de las posibilidades de forma recursiva.

Para referencia, tenemos:

\begin{align*} \mathbb{E}[N_2] &= e \qquad \text{(easyish exercise)} \\ \mathbb{E}[N_3] &= 6.30799351644 \dots \\ \mathbb{E}[N_4] &= 13.7725 \dots \\ \mathbb{E}[N_5] &\approx 30 \end{align*}

Obtener una respuesta exacta para $y \geq 5$ está más allá de mi poder computacional, pero espero que $\mathbb{E}[N_5] \approx 30$. La convergencia realmente ralentiza como $y$ crece. (Como el número de casos, y el tamaño de los numeradores / denominadores de las fracciones para los cálculos exactos).

En mi humilde opinión, las posibilidades de que exista una "buena" forma cerrada para $y > 2$ son escasas.

Aunque, curiosamente, poniendo a $\mathbb{E}[N_3]$ a la inversa simbólico de la calculadora https://isc.carma.newcastle.edu.au/advancedCalc da $\mathbb{E}[N_3] \approx 1/(1-\sin(1))$ hasta increíblemente alta precisión... pero me imagino que esto es casi seguro que una coincidencia.

EDIT: resulta que yo estoy completamente equivocado acerca de esto - este es exacta - ver achille hui de la respuesta: http://math.stackexchange.com/a/1243379/200767

Rugosa atado en $\mathbb{E}[N_y]$

Podemos débilmente ligado $\mathbb{E}[N_y]$ a pesar de que, como observar que el número esperado de veces que el primer patrón es golpeado después de $n$ total de visitas es

\begin{align*} \sum_{i=1}^{n} \frac{1}{i} \sim \ln n \to \infty \end{align*}

Así, en particular, de manera muy informal, si $\ln n \geq y$, esperamos que el primer Patrono le han sido asesinados. Ie $\mathbb{E}[N_y] \leq O(e^y)$.

Código (Python 2.7):

from fractions import Fraction
N = 100;
y = 5;

probs = [{}] * (N+1);
probs[0] = {tuple([0] * y): Fraction(1, 1)};
death_prob = [Fraction(0,1)] * (N+1);

for n in range(1, N+1): # n-1 hits so far. Now calculating nth hit
    probs[n] = {};
    for prev_hit_counts, prob in probs[n-1].iteritems():
        prob_scaler = prob / n;

        for i in range(y): # A Patron who has already been hit i times gets hit
            if prev_hit_counts[i] == 0 and i != 0: # Check such a Patron exists
                continue

            new_hit_counts = list(prev_hit_counts);
            new_hit_counts[0] += 1; # Add a new Patron who has not been hit
            probability = new_hit_counts[i] * prob_scaler; # Probability of hitting such a Patron

            if i == y-1:
                # A Patron who has been hit y-1 times gets hit... we lose.
                death_prob[n] += probability;
            else:
                new_hit_counts[i] -= 1;
                new_hit_counts[i+1] += 1;
                if tuple(new_hit_counts) not in probs[n]:
                    probs[n][tuple(new_hit_counts)] = Fraction(0,1);
                probs[n][tuple(new_hit_counts)] += probability;


for n in range(1,N+1):
    if n <= 20:
        print '\\Pr[N_{0} = {1}] &= {2} = {3} \\\\'.format(y,n,death_prob[n],float(death_prob[n]));
    else:
        print '\\Pr[N_{0} = {1}] &= {2} \\\\'.format(y,n,float(death_prob[n]));

print '\\mathbb{{E}}[N_{0}] = {1}'.format(y,float(sum([n * i for n,i in enumerate(death_prob)])));
print 'Using 0 <= x <= {0}'.format(N);