Supongamos que tenemos una composición débil del entero n en partes de k. (Un débil composiciones es esencialmente una partición en que orden se permite temas y 0)
Mi pregunta es, ¿cuál es el valor esperado de la mayor parte de la composición? El supuesto es que todas las composiciones tienen igual probabilidad.
Me voy a dar una respuesta exacta en la forma de una suma doble y, a continuación, una derivación demostrando por qué la aproximación $$E[M] \approx \frac{H_k}{\log(1+k/n)} - \frac{1}{2}$$ usando el máximo de los geométricas variables aleatorias (y mencionado por leonbloy) es excelente.
La Expresión Exacta. Como Henry notas en los comentarios anteriores, se espera que la mayor parte de los débiles composición de $n$ a $k$ partes es 1 menos que el esperado mayor parte de (fuerte) composiciones de $n+k$ a $k$ positivo partes. Al azar de la descomposición de la $n+k$ a $k$ positivo partes, a su vez, es el mismo problema que tomar un palo de longitud $n+k$ y rotura en $k-1$ elegido al azar de distintas entero puntos.
El último problema ha sido estudiado. Si dejamos $M^+$ denotar la pieza más grande, David y Nagaraja del Orden de las Estadísticas, el Problema 6.4.10, p. 155, da, para $m \geq 1$, $$P(M^+ \leq m) = \frac{1}{\binom{n+k-1}{k-1}} \sum_{i=0}^k (-1)^i \binom{k}{i} \binom{n+k-1- mi}{k-1}.$$ (El enfoque es considerar el coeficiente de $n+k$$(x + x^2 + \cdots x^m)^k$.) Por lo tanto $$E[M^+] = \sum_{m=0}^{n+k} \left(1 - \frac{1}{\binom{n+k-1}{k-1}} \sum_{i=0}^k (-1)^i \binom{k}{i} \binom{n+k-1- mi}{k-1}\right)$$ $$ = \sum_{m=0}^{n+k} \sum_{i=1}^k (-1)^{i+1} \binom{k}{i} \frac{\binom{n+k-1 -mi}{k-1}}{\binom{n+k-1}{k-1}}.$$ Así que la respuesta a la OP pregunta es 1 menos que esto: $$E[M] = \sum_{m=1}^{n+k} \sum_{i=1}^k (-1)^{i+1} \binom{k}{i} \frac{\binom{n+k-1 -mi}{k-1}}{\binom{n+k-1}{k-1}} - 1,$$ que es exacto, pero no es tan limpio como nos gustaría. (Observe que esta expresión da las mismas respuestas Henry obtenidos para valores pequeños de a$n$$k$.)
La Aproximación. Mientras que el doble de la suma de la probabilidad no tiene una forma cerrada, si hemos de aproximar el cociente de los coeficientes binomiales mediante el conocido asintótica para el cociente de funciones gamma, $\frac{\Gamma(z+a)}{\Gamma(z+b)} \approx z^{a-b}$ tenemos $$\frac{\binom{n+k-1-mi}{k-1}}{\binom{n+k-1}{k-1}} = \frac{(n+k-1-mi)! n!}{(n+k-1)! (n-mi)!} \approx (n+k)^{-mi} n^{mi} = \frac{1}{(1+k/n)^{mi}}.$$ Así que ahora tenemos $$E[M^+] \approx \sum_{i=1}^k (-1)^{i+1} \binom{k}{i} \sum_{m=0}^{n+k} \frac{1}{(1+k/n)^{mi}} \approx \sum_{i=1}^k (-1)^{i+1} \binom{k}{i} \sum_{m=0}^{\infty} \left(\frac{1}{(1+k/n)^i}\right)^m$$ $$ = \sum_{i=1}^k (-1)^{i+1} \binom{k}{i} \frac{1}{1 - (1+k/n)^{-i}}.$$
Como demuestro en mi respuesta aquí, este es el máximo esperado de una muestra de tamaño $k$ a partir de una distribución geométrica con parámetro de $p = 1 - q = 1- 1/(1+k/n)$. Entonces, en mi respuesta aquí, puedo demostrar que esto es muy aproximó por $\frac{1}{2} + \frac{1}{\lambda} H_k,$ donde $\lambda = -\log (1-p)$. Por lo tanto, tenemos, como se ha mencionado por leonbloy, que $E[M]$ es muy aproximó por $$E[M] \approx \frac{H_k}{\log(1+k/n)} - \frac{1}{2}.$$
Yo no puedo ofrecer una respuesta explícita, pero esto podría ayudar a las investigaciones:
Usar el siguiente código R
library(gtools)
library(matrixStats)
mean_max_weak_compositions <- function(total,parts) {
co <- cbind(rep(0, choose(total+parts-1, parts-1)),
combinations(total+parts-1, parts-1) ,
rep(total+parts, choose(total+parts-1, parts-1)) )
mean(rowMaxs(co[,-1] - co[,-(parts+1)])) - 1 }
vmmwc <- Vectorize(mean_max_weak_compositions)
means <- cbind(1:15, outer(1:15, 2:10, FUN="vmmwc"))
produce la siguiente tabla de espera máximo de valores, donde el número de elementos que va horizontalmente y el total va verticalmente
> means
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,] 1 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000
[2,] 2 1.666667 1.500000 1.400000 1.333333 1.285714 1.250000 1.222222 1.200000 1.181818
[3,] 3 2.500000 2.200000 2.000000 1.857143 1.750000 1.666667 1.600000 1.545455 1.500000
[4,] 4 3.200000 2.800000 2.542857 2.357143 2.214286 2.100000 2.006061 1.927273 1.860140
[5,] 5 4.000000 3.428571 3.071429 2.825397 2.642857 2.500000 2.383838 2.286713 2.203796
[6,] 6 4.714286 4.035714 3.595238 3.285714 3.056277 2.878788 2.736597 2.619381 2.520480
[7,] 7 5.500000 4.666667 4.133333 3.757576 3.477273 3.259907 3.086247 2.944056 2.825175
[8,] 8 6.222222 5.266667 4.654545 4.222222 3.897436 3.643357 3.438850 3.270629 3.129782
[9,] 9 7.000000 5.890909 5.181818 4.685315 4.314685 4.025175 3.791608 3.598684 3.436446
[10,] 10 7.727273 6.500000 5.706294 5.146853 4.729271 4.403846 4.141711 3.925134 3.742666
[11,] 11 8.500000 7.115385 6.230769 5.608059 5.142857 4.780543 4.489191 4.248869 4.046559
[12,] 12 9.230769 7.725275 6.753846 6.068681 5.556076 5.156486 4.835239 4.570564 4.348076
[13,] 13 10.000000 8.342857 7.278571 6.529412 5.969188 5.532250 5.180805 4.891287 4.648104
[14,] 14 10.733333 8.950000 7.800000 6.988562 6.381321 5.907430 5.525972 5.211540 4.947393
[15,] 15 11.500000 9.566176 8.323529 7.447884 6.792957 6.281992 5.870626 5.531382 5.246255
Trazado este (totales en el eje horizontal, las expectativas de los valores máximos en el eje vertical, y los números de partes como colores dígitos) se parece a
Las expectativas de los valores máximos parecen crecer cerca linealmente a los totales, pero al caer más lentamente que inversamente proporcional a la cantidad de piezas.
Agregó
Para las pequeñas $n$ es posible expresar el valor esperado de la mayor parte de la composición explícitamente como un polinomio de relación, tales como:
$$E_{\max}(1,k) = 1$$
$$E_{\max}(2,k) = 1+\frac{2}{k+1}$$
$$E_{\max}(3,k) = 1+\frac{6(k+1)}{(k+1)(k+2)}$$
$$E_{\max}(4,k) = 1+\frac{12(k^2+2k+3)}{(k+1)(k+2)(k+3)}$$
$$E_{\max}(5,k) = 1+\frac{20(k^3+3k^2+14k+6)}{(k+1)(k+2)(k+3)(k+4)}$$
$$E_{\max}(6,k) = 1+\frac{30(k^4+4k^3+39k^2+32k+44)}{(k+1)(k+2)(k+3)(k+4)(k+5)}$$
and there are enough obvious patterns in the coefficients of the numerators to be able to suggest a reasonable approximation for cases of $k$ very much greater than $$ n.
Aquí está mi aproximación asintótica:
Vamos a considerar la (equivalente, como ha señalado Henry) en caso de fuertes composiciones de $n+k=m$ a $k$ positivo partes.
En términos probabilísticos, tenemos $k$ variables aleatorias $x_i$ tomando valores en $1\cdots m$, con $\sum x_i =m$ y fueron todas las posibles realizaciones son equiprobables.
Yo reclamo (si mi vida no depende de ella) que el problema es asintóticamente equivalente (¿por qué? ¿en qué sentido? se explica a continuación) para tener $k$ iid geométricas variables aleatorias $y_i$ (tomando valores en $1\cdots \infty$) con una media de $m/k=1/p$ (aviso que aquí $\sum y_i$ no es fijo, sino $E[\sum y_i] =m$).
Entonces, una primera aproximación sería
$\displaystyle E_M = E(max(x_i)) -1 \approx E(max(y_i)) -1 = G\left(k,\frac{k}{k+n}\right) - 1$
donde $G(k,p)$ la expectativa de que el máximo de $k$ IID geométrica de las variables aleatorias de parámetro $p$. Este problema más tarde se discute aquí y aquí. La fórmula exacta es bastante complicada:
$\displaystyle G(k,p) = \sum_{i=1}^k \binom{k}{i} (-1)^{i+1} \frac{1}{1-(1-p)^i}$
Una estrecha aproximación está dada por:
$\displaystyle G(k,p) \approx \frac{H_k}{- \log(1-p)} + \frac{1}{2} $ , $\displaystyle H_k=\sum_{i=1}^k \frac{1}{i}$ (número armónico).
lo que da a nuestra segunda aproximación:
$\displaystyle E_M \approx \frac{H_k}{\log(1+k/n)} - \frac{1}{2}$
Y para $n$ aumento de la con $k$ constante, el primer fin de la expansión del logaritmo da esta tercera aproximación, que muestra el aumento lineal observada por Henry:
$\displaystyle E_M \approx n \frac{ H_k} {k} - \frac{1}{2} \approx n \frac{ H_k} {k}$ $ \hspace{14pt} (n \to \infty)$
También es fácil ver que si tanto $n,k$ de incremento con relación constante, a continuación, $E_M$ crece como $\log(k)$.
Algunos de los resultados, para comparar con la de Henry valores, para la segunda aproximación (muy similar a la primera; y la tercera es bastante más grueso)
1 2 3 4 5 6 7 8 9 10
1 0.9427 0.8654 0.8225 0.7944 0.7744 0.7591 0.7469 0.7370 0.7286 0.7215
2 1.9663 1.6640 1.5008 1.3963 1.3226 1.2673 1.2239 1.1887 1.1595 1.1347
3 2.9761 2.4364 2.1449 1.9588 1.8280 1.7301 1.6536 1.5918 1.5407 1.4975
4 3.9814 3.1995 2.7761 2.5056 2.3157 2.1738 2.0631 1.9739 1.9002 1.8380
5 4.9848 3.9580 3.4007 3.0444 2.7942 2.6073 2.4617 2.3444 2.2476 2.1661
6 5.9872 4.7141 4.0216 3.5784 3.2670 3.0346 2.8535 2.7077 2.5874 2.4862
7 6.9889 5.4686 4.6401 4.1093 3.7363 3.4577 3.2407 3.0661 2.9221 2.8010
8 7.9902 6.2221 5.2570 4.6381 4.2030 3.8780 3.6248 3.4210 3.2531 3.1119
9 8.9912 6.9749 5.8728 5.1655 4.6679 4.2962 4.0065 3.7734 3.5813 3.4198
10 9.9921 7.7272 6.4877 5.6917 5.1314 4.7127 4.3864 4.1239 3.9075 3.7256
11 10.9927 8.4791 7.1021 6.2171 5.5939 5.1281 4.7649 4.4728 4.2320 4.0296
12 11.9933 9.2307 7.7159 6.7418 6.0555 5.5424 5.1424 4.8205 4.5552 4.3322
13 12.9938 9.9821 8.3294 7.2660 6.5165 5.9560 5.5189 5.1672 4.8773 4.6336
14 13.9943 10.7333 8.9426 7.7897 6.9770 6.3690 5.8948 5.5132 5.1985 4.9341
15 14.9946 11.4844 9.5555 8.3132 7.4370 6.7814 6.2700 5.8584 5.5190 5.2338
Algunos (suelto) justificación acerca de la aproximación. Para quienes están familiarizados con la estadística la física, esto está relacionado con un disco duro de la barra (unidimensional) de gas, más de un espacio discreto, con la distancia entre consecutivos particules como variables, y la (asympotical) la equivalencia de dos "conjuntos": el original tiene volumen fijo (m) y el número de partículas (k) (que correspondería a un "canónica" ensemble), la segunda mantiene el número de partículas pero el volumen puede variar (sería un isobárica de conjunto), pero tales que la media el volumen es igual al volumen fijo de la original. La condición de que las configuraciones el original conjunto tienen la misma probabilidad está relacionada con un sistema sin interacción energía (a excepción de la exlusion), y que corresponde (en el segundo conjunto) a un de partículas que pueden aparecer en cada celda con una probabilidad independiente de la de sus vecinos: y a partir de aquí tengo el geométrico.
En otros términos, la equivalencia puede ser justificado en que el segundo modelo probalistic es igual a la primera si acondicionado, en el caso de que las variables que se suma a a $m$ - y asintóticamente tenemos menos probabilidades de pasar de este caso.
Todo esto no ofrecer una rigurosa prueba, por supuesto. También se podría argumentar que esta tipo de aproximación al "conjunto de equivalencia" es plausible para el cómputo de la típica estadística magnitudes que son en su mayoría relacionados con los promedios, pero aquí estamos de computación el valor extremo, es menos claro que se debe trabajar.
Añadido: Algunas aclaraciones sobre el método de aproximación:
Recordemos que ${\bf x}=\{x_i\}$ , $i=1\cdots k$ es nuestra original discreto de la variable aleatoria; apoyo está restringido por $x_i\ge 1$$\sum x_i = m= n+k$. Dentro de esta región, todas las realizaciones tiene la misma probabilidad, por lo que la función de probabilidad es constante:
$P({\bf x}) = \frac{1}{Z}$
( $Z(n,k)$, la "función de partición", sería el recuento de todas las configuraciones posibles, pero eso no importa aquí).
Por otro lado, la propuesta de ${\bf y}=\{y_i\}$ ha iid geométrica de los componentes, con el parámetro $p=k/m$, por lo que su función de probabilidad es
$\displaystyle P({\bf y}) = \prod p (1-p)^{y_i} = p^k (1-p)^{\sum y_i}$
con $y_i \ge 1$. Llamar a $ s({\bf y})=\sum y_i$, es fácil ver que si nos condición en $s = m$, obtenemos la distribución original (que es constante, y en la misma región).
$P({\bf y} | s = m ) = P({\bf x})$
Estamos interesados en $E[g({ \bf x})]$ donde $g({\bf x}) = max(x_1 \cdots x_k)$, y quiere ver si puede ser aproximada por $E[g({\bf y})]$ (un poco floja la notación aquí)
$\displaystyle E[g({\bf y})] = \int g({\bf y}) P({\bf y}) dy = \int g({\bf y}) \sum_s P({\bf y} | s) P(s) dy $
Ahora, debido a la forma en que elegimos $p$,$E(s)=m$, y podemos esperar que $P(s)$ será muy alcanzó su punto máximo alrededor de ese valor (para mostrar que la estadística de conjuntos -canonnical, microcanonical, grand-canónica, etc - son asympotically equivalentes, se utiliza esta línea de razonamiento ). Y así, asympotically, podemos esperar ser justificado en aproximado de la suma por la que solo término. Lo que significaría que
$E[g({\bf y})] \approx E[g({\bf x})]$
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
