Subconjunto seleccionado al azar, valor esperado de la suma

Question

Problema interesante que encontré mientras aprendía:

Dado $X=\left\{1,..,n\right\}$. Seleccionamos aleatoriamente un subconjunto de $X$ y lo llamamos $A$. Cada subconjunto es igualmente probable.

a) Encuentra el valor esperado de la suma de los elementos de A.

b) Encuentra el valor esperado de la suma de los elementos de A, bajo la condición de que tiene $k$ elementos.

a) Creo que sé cómo resolver a). Si cada subconjunto es seleccionado con la misma probabilidad entonces creo que es equivalente a seleccionar cada elemento de $X$ con probabilidad $\frac{1}{2}$. Así, usando indicadores, obtenemos que el valor esperado que buscamos es $\frac{n(n+1)}{4}$. Pero no puedo encontrar ningún argumento riguroso de por qué es equivalente seleccionar cada elemento con probabilidad $1/2$.

b) Una pequeña observación con $k=1$ (cada elemento seleccionado con probabilidad $1/n$) y $k=n$ (cada elemento seleccionado con probabilidad $1$) me da la sensación de que el enfoque de a) puede ser utilizado con probabilidad $k/n$ y luego el resultado es $\frac{k(n+1)}{2}$. Pero es mucho menos intuitivo que la observación en a). ¿Alguien puede ayudar?

Answer 1

En cuanto a tu primera pregunta, ten en cuenta que un subconjunto tiene una representación equivalente como una secuencia binaria. Por ejemplo, para $n = 4$, el subconjunto $\{1,3\}$ se puede identificar con $(1,0,1,0)$. Ahora, elegir un subconjunto de forma uniforme al azar, es como elegir una secuencia de forma uniforme al azar de las $2^n$ posibilidades. Deberías ser capaz de argumentar el resto.

En cuanto a tu segunda pregunta, sea $X_i$ el indicador de que el $i$ está presente en el subconjunto aleatorio (es decir, la $i$-ésima posición en la representación binaria de arriba tiene un $1$). Entonces, quieres $$ E\Big[ \sum_{i=1}^n i X_i \Big| \sum_{i=1}^n X_i = k\Big] = \sum_{i=1}^n i\, E\Big[X_i \Big| \sum_j X_j = k\Big] $$ Ahora, puedes usar la simetría. Sea $a_i :=E[X_i \Big| \sum_j X_j = k]$ (que es la probabilidad condicional de elegir el $i$). Entonces todos los $a_i$ deberían ser iguales y $\sum_i a_i = k$ (¿por qué?), de lo que se deduce que $a_i = k/n$. Esto te da la respuesta que tienes, y también muestra que la probabilidad condicional de elegir el $i$ es $k/n$ para cada $i.

Answer 2

Todos tus suposiciones son correctas. Lo que sucede aquí es que inicialmente trabajas en el espacio de probabilidad $\Omega={\cal P}(X)$, el conjunto de todos los subconjuntos de $X$.

En ese espacio de probabilidad, puedes definir la variable aleatoria $V_i$, igual a $1$ si $i\in A$ y $0$ en caso contrario.

Denotemos por $E_i=\lbrace A \in \Omega | i \in A \rbrace$ y $N_i=\lbrace A \in \Omega | i \not\in A \rbrace$. Luego, $E_i$ y $N_i$ tienen el mismo número de elementos (de hecho, $A \mapsto \lbrace i \rbrace \cup A$ es una biyección entre $E_i$ y $N_i$), por lo que es igualmente probable que $A$ contenga a $i$ o no: $P(V_i=0)=P(V_i=1)=\frac{1}{2}$. Esto justifica tu "a)".

Answer 3

Para a) puedes emparejar cada subconjunto con su complemento para demostrar que un elemento dado está en la mitad de los subconjuntos, por lo que está en el subconjunto elegido la mitad del tiempo.

Para b) cada elemento tiene la misma probabilidad de ser elegido. Si quieres obtener $k$ de ellos, necesitas que esa probabilidad sea $\frac kn$.

Buen razonamiento en ambos casos.