Rolling $n$ $k$-caras de los dados y el descarte de la menor $m$ de ellos.

Question

En esta pregunta la voy a utilizar la notación $\Bbb{E}(n,k,m)$ a se refieren a la media esperada de rodadura $n$ $k$-caras de los dados y el descarte de la menor $m$ de ellos.

---

La más trivial de respuesta ocurre cuando $m = 0$, en cuyo caso debemos descartar ninguna dados y llegamos al resultado:

$$\Bbb{E}(n,k,0) = \frac{k}{2} + \frac{1}{2}$$

---

Al $m = 1$, lo que yo consideraba un caso de ejemplo para dar algo de intuición para este problema. Mirando en el caso de $\Bbb{E}(2, 6, 1)$, me encontré con el siguiente patrón.

Hay un $1$s, tres $2$s, cinco $3$s, etc.

La suma de estos resultados es:

$$\sum_{i=1}^{6} i(2i-1)$$

En general, el resultado esperado para $\Bbb{E}(2,k,1)$ es:

$$\frac{\sum_{i=1}^{k} i(2i-1)}{k^2} = \frac{\sum_{i=1}^{k} 2i^2 - \sum_{i=1}^{k} i}{k^2} = \frac{\frac{2k(k+1)(2k+1)}{6} - \frac{k(k+1)}{2}}{k^2} = \frac{2}{3}k + \frac{1}{2} - \frac{1}{6k}$$

---

Ahora quiero considerar $\Bbb{E}(3,k,2)$. En el caso anterior cada valor de $i$ se produjo $2i - 1$ número de veces. De dónde sacaste $2i - 1$?

Parece que la frecuencia de aparición es la diferencia de cuadrados consecutivos.

$$i^2 - (i-1)^2 = 2i - 1$$

Esto parece intuitivo basado en la imagen que he proporcionado. Podemos razón de que en el caso de $n = 3$, la frecuencia de aparición será la diferencia consecutivos en los cubos.

$$i^3 - (i-1)^3 = 3i^2 - 3i + 1$$

El resultado esperado de $\Bbb{E}(3,k,2)$ es complicado, así que sólo voy a escribir las iniciales de la expresión y la expresión simplificada.

$$\frac{\sum_{i=1}^{k} i(3i^2-3i+1)}{k^3} = \frac{3}{4}k + \frac{1}{2} - \frac{1}{4k}$$

---

Vamos a ver finalmente el caso de $\Bbb{E}(n,k,n-1)$. Basado en los resultados anteriores, suponemos que parece:

$$\frac{\sum_{i=1}^{k} i(i^n - (i-1)^n))}{k^n} = \frac{n}{n+1}k + \frac{1}{2} - \mathcal{O}(\frac{1}{k})$$

Mis dos preguntas son:

• Es mi conjetura para $\Bbb{E}(n,k,n-1)$ correcto, y si es así, ¿cómo puedo demostrarlo?
• ¿Qué sucede cuando $m \ne n-1$? ¿Cómo puedo ajustar mi análisis a la cuenta para el descarte de los dados esos que me dejan , no sólo el valor máximo?

Answer 1

Si $M$ es el valor máximo en el $n$ dados lanzados, a continuación,$\mathbb{P}(M\leq x)=(x/k)^n$, de modo que $\mathbb{E}(M)=\sum_{x=0}^{k-1} \left(1-\left({x\over k}\right)^n\right)=k-{1\over k^n}\sum_{x=0}^{k-1}x^n.$ el Uso de Faulhaber la fórmula puede demostrar que $$\sum_{x=0}^{k-1}x^n ={1\over n+1}\left[k^{n+1}-{1\over 2}(n+1)k^n+O(k^{n-1})\right]$$ y poniendo a estos en conjunto da, como se esperaba, $$\mathbb{E}(M)={n\over n+1}\,k+{1\over 2}+O(1/k).$$

---

Aquí está una más argumento general. Para cualquier $1\leq j\leq n$ deje $X_{(j)}$ $j$th el fin de estadística de la $n$ rollos de dados. Para $0\leq x<k$, vamos a $Y$ el número de tiradas de dados que tomar valores en $\{1,2,\dots, x\}$. Tenemos $X_{(j)}>x$ si y sólo si $Y<j$, de modo que $$ \mathbb{P}(X_{(j)}>x)=\mathbb{P}(S<j)=\sum_{y=0}^{j-1}{n\elegir y} \left({x\sobre k}\right)^y \left(1-{x\sobre k}\right)^{n-y}.$$

Por lo tanto, tenemos la fórmula explícita $$\mathbb{E}(X_{(j)})=\sum_{x=0}^{k-1}\sum_{y=0}^{j-1}{n\elegir y} \left({x\sobre k}\right)^y \left(1-{x\sobre k}\right)^{n-y}.\tag1$$

Para un gran $k$ asymptotics, cambio el orden de la suma y reescribir como una suma de Riemann para obtener $$\mathbb{E}(X_{(j)})=k\sum_{y=0}^{j-1}\sum_{x=0}^{k-1}{n\elegir y} \left({x\sobre k}\right)^y \left(1-{x\sobre k}\right)^{n-y}{1\over k}\approx k\sum_{y=0}^{j-1} \int_0^1 {n\elegir y} w^y(1-w)^{n-y}\,dw={k\,j\más de n+1}.$$

El uso de la de Euler-Maclaurin fórmula, usted puede obtener más términos en la expansión asintótica, por ejemplo, $$\mathbb{E}(X_{(j)})={k\,j\over n+1}+{1\over 2}+O(1/k).$$

---

Asymptotics son agradables, pero la fórmula (1) también nos permite derivar los límites $${kj\over n+1}\leq \mathbb{E}(X_{(j)})\leq {kj\over n+1}+1.$$

Answer 2

El valor esperado de un dado después de tirar a la $n$ a veces y el descarte de la menor $m$ valores

Empezamos con algunos $n$ idéntico de la feria de dados de $d$ lados que van desde $1$$d$. Voy a empezar a definir para cada uno de los dados de una variable aleatoria $X_i$, y voy a definir el r.v. $A$ como media de los $X_i$ es decir

$$A=\frac1n\sum X_i$$

Entonces el valor esperado de $A$

$$\Bbb E[A]=\Bbb E\left[\frac1n\sum X_i\right]=\frac1n\sum\Bbb E[X_i]$$

A continuación, se definen dos grupos: el proyecto de grupo de la longitud de la $m$ y el grupo restante de duración $n-m$, y tres tipos de dados en función de los valores que en algunos de instalación: los dados $X_v$ con el valor máximo $v$ de la descartados grupo, los dados $X_\ell$ con valores inferiores a $v$, y los dados $X_h$ que mantienen valores superiores a $v$ es decir,

$$X_v=v,\ X_\ell\in\{1,...,v-1\},\text{ and }X_h\in\{v+1,...,d\}\\V\in\{1,...,d\}$$

donde $V$ es la r.v. para el $v$ del valor. Los tres tipos de dados son independientes una de la otra, sino que alcance depende de $V$.

Cualquier tiro se compone de dados de estos tres tipos, arroja sólo difieren en la cantidad de cada tipo, y en cada tiro, al menos, un dado de la especie $X_v$ está presente. Voy a nombrar la cantidad de $X_\ell$ como sólo la r.v. $L$, la cantidad de $X_h$ $H$ y por último la cantidad de $X_v$$n-H-L$, es decir,

$$L\in\{0,...,m-1\},\text{ and }H\in\{0,n-m\}$$

Observe que $L$ $H$ son independientes una de la otra, sino que alcance depende de $V$, por ejemplo si $V=1$ no no $X_\ell$ dados en el tiro lo $L=0$.

Entonces tenemos que

$$\begin{align}\Bbb E[A|H,L,V]&=\frac1n\sum\Bbb E[X_i]=\frac1n(L\Bbb E[X_ \ell]+H\Bbb E[X_h]+(n-H-L)\Bbb E[X_v])\\&=\frac1n\left(\frac12LV+\frac12H(d+V+1)+(n-H-L)V\right) \end{align}$$

debido a $\Bbb E[X_\ell]=\Bbb E[X|X<v]$ $\Bbb E[X_h]=\Bbb E[X|X>v]$ (aviso que $\{X_i: X_i<v\}$, $\{X_i: X_i=v\}$ y $\{X_i: X_i>v\}$ es sólo una partición del conjunto de $\{X_i\}$).

Pero la causa por la que estamos descartando la $m$ más bajo de los valores que queremos, en promedio, sólo el $X_i$ de los restantes del grupo compuesto sólo de $X_h$ y algunos $X_v$ es decir

$$\Bbb E[A^*|H,V]=\frac1{n-m}\left(H\frac{d+V+1}{2}+(n-m-H)V\right)$$

y

$$\begin{align}\Bbb E[A^*]&=\Bbb E[\Bbb E[A^*|H,V]]\\&=\sum_{h,v}\Bbb E[A^*|H=h,V=v]\Pr[H=h,V=v]\\&=\sum_{h,v}\frac1{n-m}\left(h\frac{d+v+1}{2}+(n-m-h)v\right)f(h,v)\end{align}$$

donde $f(h,v)$ es la articulación de masa de probabilidad de la función de $H$$V$, y esta es una distribución marginal de la más general $f(h,\ell,v)$ es decir, el conjunto de la masa de probabilidad de la función de $H$, $L$ y $V$, que es una especie de distribución multinomial porque representan a las diferentes configuraciones de un tiro divide en tres tipo de eventos con diferente probabilidad de cada uno, es decir,

$$\begin{align}f(h,\ell,v)&=\binom{n}{\ell,h,n-\ell-h}\Pr[X_i>v]^h\Pr[X_i<v]^\ell\Pr[X_i=v]^{n-\ell-h}\\&=\binom{n}{\ell,h,n-\ell-h}\left(\frac{d-v}{d}\right)^h\left(\frac{v-1}{d}\right)^\ell\left(\frac{1}{d}\right)^{n-\ell-h}\\&=\frac1{d^n}\cdot\frac{n^{\underline{\ell+h}}}{\ell!h!}(d-v)^h(v-1)^\ell\end{align}$$

(donde $a^{\underline b}$ es una caída factorial) y

$$f(h,v)=\sum_\ell f(h,\ell,v)$$

Y finalmente tenemos

$$\begin{align}\Bbb E[A^*]&=\sum_{h,\ell,v}\left(\frac{h(d+1-v)}{2(n-m)}+v\right)\binom{n}{\ell,h,n-\ell-h}\left(\frac{d-v}{d}\right)^h\left(\frac{v-1}{d}\right)^\ell\left(\frac{1}{d}\right)^{n-\ell-h}\\&=\frac1{d^n}\sum_{h,\ell,v}\left(\frac{h(d+1-v)}{2(n-m)}+v\right)\frac{n^{\underline{\ell+h}}}{\ell!h!}(d-v)^h(v-1)^\ell\end{align}$$

y no creo que esta expresión se puede simplificar significativamente (parcial multinomial sumas no tiene forma cerrada). De todos modos se puede utilizar para desarrollar algún programa para evaluar $\Bbb E[A^*]$.

(*El rango de las diferentes sumatorias son la gama de los respectivos r.v.)