4 votos

Combinatoria: la Media y la Varianza de una función de indicador de los elementos dispuestos en un círculo.

Tengo un problema a partir de una tarea que he estado luchando con. Normalmente no publicar la tarea aquí, pero me he pasado varias horas tratando de entender la forma correcta de resolver esto , fue en vano. Voy a ofrecer mi trabajo, y espero que alguien me apunte en la dirección correcta.

El problema:

There are 25 balls (10 blue, 15 red) arranged randomly in a circle.
Let X be a random variable who's value is the number of BLUE balls 
with a RED ball on either side of it.
    A. Find E[X]
    B. Find Var(X)

Así que aquí está cómo lo hice hasta ahora: $$ \text{Let 'Xi' ser un indicador, tal que:}\\ X_i = \left\{ \begin{array}{1 l} 1 & \quad \text{if the ith ball is blue, and i-1, i+1 balls are both red}\\ 0 & \quad \text{otherwise} \end{array} \right.\\ $$

Por lo tanto, tenemos E[X]: $$ E[X_i] = \frac{15}{25} * \frac{10}{24} * \frac{14}{23} = \frac{7}{46}\\ \\ E[X] = \sum_{i=1}^{25} E[X_i] = 25*\frac{7}{46} = 3.804\\ $$

Ahora para la varianza: $$ Var(X) = \sum_{i=1}^{25} Var(X_i) + 2*\sum_{i<}\sum_{j} Cov(X_i,X_j) \\ Var(X_i) = p*(1-p) = \frac{7}{46}*\frac{39}{46} = \frac{273}{2116} \\ P \lbrace X_i = 1, X_j = 1 \rbrace\left\{ \begin{array}{1 l} |i-j|=1 & \quad \text{0 (since 2 blues are adjacent)}\\ |i-j|=2 & \quad \frac{7}{46}*\frac{9}{22}*\frac{13}{21} = \frac{39}{1012}\\ |i-j|>2 & \quad \frac{7}{46}*\frac{13}{22}*\frac{9}{21}*\frac{12}{20} = \frac{117}{5060} \end{array} \right.\\ \text{y puesto que } \quad Cov(X_i,X_j) = E[X_i X_j] - E[X_i]E[X_j] \\ \\ $$ obtenemos: $$ Cov(X_i,X_j) = \left\{ \begin{array}{1 l} |i-j|=1 & \quad 0 - (\frac{7}{46})^2 = -\frac{49}{2116}\\ |i-j|=2 & \quad \frac{39}{1012}-(\frac{7}{46})^2 = \frac{179}{11638}\\ |i-j|>2 & \quad \frac{117}{5060}-(\frac{7}{46})^2 = -\frac{1}{29095}\\ \end{array} \right.\\ $$

Ahora, tenemos la suma de las Covarianzas. Para ello necesitamos saber cuántos de cada caso hay - y esto es de donde yo soy se confundan. Yo creo que haríamos de la siguiente manera: Hemos 25c2 diferentes posibilidades donde i!=j (donde pueden ser colocados). Tenemos 25 si |i-j| = 1, 25, donde |i-j|=2 (es un círculo), y 250 donde |i-j|>2.

Ingenuamente, me sale: $$ Var(X) = 25*\frac{273}{2116} + 2*(25*(-\frac{49}{2116})+25*\frac{179}{11638}+250*(-\frac{1}{29095})) = 2.8194\\ $$

Pero es un círculo, por lo que técnicamente tenemos 25 maneras de mirar el círculo, lo que significa que debo dividir por 25 - pero, estos no están teniendo en cuenta todas las permutaciones de la 25c10 diferentes posibilidades, así que sería el descuento posibilidades de hacerlo..

Siento que esto es incorrecto, porque yo no estoy tomando en cuenta el círculo (excepto permitiendo a los 25 indicadores en lugar de 24 o 23, que es sólo la adición de posibilidades y no de la eliminación de ellos).

Ayuda, por favor?

4voto

Jon Clegg Puntos 661

Hay varios defendible interpretaciones de la cuestión, dependiendo de cómo la "disposición aleatoria" se lleva a cabo.

Como multinomial problema

Las bolas rojas determinar $n=15$ espacios ("slots") entre ellos. Supongamos que se llenan equiprobably y de forma independiente por el $k=10$ bolas de color azul. $X$ cuenta el número de ranuras de llenado con exactamente una bola azul.

Para encontrar la expectativa de $X$, considere la posibilidad de una única ranura. Deje $X_i$ ser el indicador de que el evento de que la ranura tiene exactamente una bola azul. Debido a que el recuento de las bolas de color azul en la ranura ($Y_i$) tiene un Binomio$(k, 1/n)$ distribución,

$$\mathbb{E}(X_i) = \Pr(X_i = 1) = \Pr(Y_i=1) = \binom{k}{1}\frac{(n-1)^{k-1}}{n^k} = \frac{k}{n}\left(1-\frac{1}{n}\right)^{k-1}.$$

Whence, by linearity of expectation,

$$\mu_1 = \mathbb{E}(X) = \mathbb{E}\left(\sum_iX_i\right) = \sum_i\mathbb{E}(X_i) = n\mathbb{E}(X_i) = k\left(1-\frac{1}{n}\right)^{k-1}.$$

To find the variance we will need to obtain the expectation of

$$X^2 = \left(\sum_i X_i\right)^2 = \sum_i \left(X_i\right)^2 + \sum_{i\ne j}X_iX_j = X + \sum_{i\ne j}X_iX_j.$$

(The last equality follows from $X_i^2 = X_i$.) All terms in the last sum have identical distributions. Consider one of them:

$$\mathbb{E}(X_iX_j) = \Pr(X_iX_j=1) = \Pr(Y_i=1,\, Y_j=1).$$

The latter is the event that one ball lands in slot $i$, another in slot $j$, and the remaining $k-2$ balls in the remaining $n-2$ slots. This is a multinomial probability given by

$$ \Pr(Y_i=1,\, Y_j=1) = \binom{k}{1,1,k-2} \frac{(n-2)^{k-2}}{n^k} = \frac{1}{n^2}k(k-1)\left(1-\frac{2}{n}\right)^{k-2}.$$

Because there are $n(n-1)$ distinct ordered pairs $(i,j)$, we obtain

$$\mu_2 = \mathbb{E}(X^2) = \mathbb{E}(X) + n(n-1)\mathbb{E}(X_iX_j) = \mu_1 + k(k-1)\left(1-\frac{2}{n}\right)^{k-2}\left(1-\frac{1}{n}\right).$$

The variance of $X$ is, as usual,

$$\text{var}(X) = \mu_2 - \mu_1^2.$$

For $k=10, n=15$ compute that $\mathbb{E}(X) = \mu_1 = 5.374412$ and $\text{var}(X) = 3.226079$.

As a permutation problem

Suppose instead that all $(n+k)!$ possible permutations of the balls in the circle are equiprobable. Let $\mathcal{P}$ be the $n+k$ positions indexed by the integers modulo $n+k$. As a matter of notation, let $\text{red}(i)$ be the event there is a red ball at position $i$ and $\text{blue}(i)$ be the event there is a blue ball at position $i$.

This time let's make a position-centric analysis rather than one from the point of view of the blue balls: for each $i\in\mathcal{P}$, let $X_i$ be the indicator that a blue ball is at position $i$ and red balls are situated at positions $i-1$ and $i+1$. The chance that $X_i=1$ is readily found by multiplying a succession of conditional probabilities:

$$\eqalign{ \mathbb{E}(X_i=1) &= \Pr(X_i=1) \\ &= \Pr(\text{rojo}(i-1))\Pr(\text{blue}(i)|\text{rojo}(i-1))\Pr(\text{rojo}(i+1)|\text{blue}(i), \text{rojo}(i-1)) \\ &= \frac{n}{n+k}\frac{k}{n+k-1}\frac{n-1}{n+k-2} \\ &= \frac{n^{(2)} k^{(1)}}{(n+k)^{(3)}}. }$$

Here, $a^{(j)}=a(a-1)\cdots(a-j+1)$ denotes the factorial power.

As before, additivity of expectation implies

$$\mu_1 = \mathbb{E}(X) = (n+k)\mathbb{E}(X_0) = \frac{n^{(2)} k^{(1)}}{(n+k-1)^{(2)}}.$$

To obtain the variance we will need to compute the expected products $\mathbb{E}(X_iX_j)$. These involve four distinct configurations:

  1. $i=j$. There are $n+k$ of these, each contributing $\mathbb{E}(X_i^2) = \mathbb{E}(X_i)$ to the second moment. The total contribution therefore is $\mu_1$.

  2. $|i-j|=1$: es decir, $i$ e $j$ son vecinos inmediatos en el círculo. (La notación $|a|$ se refiere a la distancia alrededor del círculo, que puede ser calculada como $\min\{|\pm a + j(n-k)|: j\in\mathbb{Z}\}.$) En este caso es imposible que $X_i$ e $X_j$ igualdad $1$, por lo que la contribución total es cero.

  3. $|i-j|=2$. Estas son las configuraciones de la forma roja-azul-rojo-azul-rojo. Razonando como antes (con cadenas de probabilidades condicionales), cada configuración tiene una expectativa de $n^{(3)} k^{(2)}/(n+k)^{(5)}$. Hay $2(n+k)$ pares ordenados $(i,j)$ con esta relación, donde la contribución es

    $$2\frac{n^{(3)} k^{(2)}}{(n+k-1)^{(4)}}.$$

    (Este valor se toma como cero cada vez que $n+k\lt 4$, con el mismo convenio para la celebración de todas las expresiones similares, a continuación.)

  4. $|i-j|\gt 2$. Estas son las configuraciones de la forma roja-azul-rojo...rojo-azul-rojo. Hay $(n+k)(n+k-5)$ estos pares ordenados, dando una contribución

    $$\frac{n^{(4)} k^{(2)}}{(n+k-1)^{(4)}}.$$

En consecuencia, la varianza es

$$\text{var}(X) = \mu_1 + 2\frac{n^{(3)} k^{(2)}}{(n+k-1)^{(4)}} + \frac{n^{(4)} k^{(2)}}{(n+k-1)^{(4)}} - \mu_1^2.$$

With $n=15$ and $k=10$ we obtain $\mu_1 = 175/46\aprox 3.80435$, $\mu_2 = 4375/253$, and the variance is $65625/23276\aprox 2.81943.$ Estos resultados coinciden con los presentados en la pregunta.


La verificación de los resultados

Hay varias formas de comprobar estos resultados, incluyendo la simulación y la enumeración exhaustiva. Para ilustrar la simulación, aquí es una revisión de la multinomial resultados. (La plataforma es R.)

n <- 15        # Slots
k <- 10        # Balls
n.iter <- 10^5 # Simulation length
set.seed(17)
x <- replicate(n.iter, sum(1 == table(sample.int(n, k, replace=TRUE))))
cat("Mean =", round(mean(x), 3), "Var =", round(var(x), 3))

La salida es

Media = 5.367 Var = 3.2

acordar estrechamente con el análisis multinomial.

Aquí es un cálculo de la distribución completa de la $X$ en el caso de permutación. (La plataforma Mathematica.)

neighbors[s_List, n_] := 
 Total[(Boole[Mod[#, n] != 0] & /@ (RotateRight[s] - (s - 1))) 
       (Boole[Mod[#, n] != 0] & /@ (RotateLeft[s] - (s + 1)))];
With[{n = 15, k = 10}, Tally[neighbors[#, n + k] & /@ 
                       Subsets[Range[n + k], {k}]]]

{{0, 40380}, {1, 205100}, {2, 495950}, {3, 709800}, {4, 775775}, {5, 500500}, {6, 375375}, {7, 85800}, {8, 75075}, {10, 5005}}

Es decir, hay una probabilidad de $40380/\binom{25}{10}$ que $X=0$, una probabilidad de $205100/\binom{25}{10}$ que $X=1$, y así sucesivamente.

La expectativa es $\mu_1=(0\times 40380 + 1\times 205100 + \cdots + 10\times 5005)/\binom{25}{10} = 175/46$ y el segundo momento, y se calculan de manera similar, se $\mu_2 = 4375/253$, de acuerdo con el análisis.

3voto

Sebastiaan Puntos 86

Trate de mirar el problema desde la perspectiva de una pelota. Estás en lo correcto en que hay 3 casos de la covarianza. El ajuste de la función para calcular la varianza de la suma que esperemos que aclara las cosas. Tenga en cuenta que la varianza de una suma de stochasts es un producto cartesiano de las covarianzas. Vamos a utilizar sólo estas covarianzas.

Para cada bola yo, usted necesitará suma:

  1. una vez que la covarianza con sí mismo (que es igual a la varianza)
  2. el doble de la covarianza con su vecino
  3. el doble de la covarianza con su segunda prójimo
  4. 20 veces la covarianza con bolas de más de 2 plazas de bola yo

Sumando esto a través de todas las bolas que los resultados en su respuesta. El uso de las posiciones relativas de las bolas en lugar de los índices que nos libera de la ambigüedad de la posición de las bolas en el círculo.

En una nota al margen: Otra forma de ver este problema es: Cuando usted se construiría una línea recta de bolas, usted probablemente no volvería a sentarse en el otro lado de la mesa a la conclusión de que usted no debería contar reflejado líneas.

i-Ciencias.com

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.

Powered by:

X