Given $n$ balls inside a box, $k$ black and $n-k$ white. We're picking all the balls out and laying them in order. Let $X_1,\ldots,X_n$ be random variables such that $X_i = 1$ is the $i$-th chosen ball is black and $X_i = 0$ if white. Define the random variable $$Y_n = 1 + \sum_{i = 1}^{n-1} \mathbb{1}_{\{X_i \neq X_{i+1}\}} $$ where $\mathbb{1}$ is the indicator function. What's the expectation $\mathbb{E}Y_n$ and variance $\text{Var}(Y_n)$?

I'm new to probability and have been trying this problem for a while, still can't solve it. The probability distrubition of $X_i$ here is not Bernoulli distribution, because the probability $p$ of picking up a black ball in the $i$-th draw depends on results of $1,\ldots, (i-1)$ draws for $i > 1$.

Let $M := \{\overbrace{1,\ldots,1}^{k}, \overbrace{0,\ldots,0}^{n-k}\}$ be a multiset. We can think of our sample space as $\Omega := \{\omega = (\omega^1,\ldots,\omega^n) : \omega^i \in M \}$ with cardinality $\frac{n!}{k!(n-k)!}$.

Since $Y_n(\omega) = \Big(1 + \sum_{i = 1}^{n-1} \mathbb{1}_{\{X_i \neq X_{i+1}\}}\Big)\omega$, the possible numerical values for each $Y_n$ is the set $1,\ldots,n$. So $$\mathbb{E}Y_n = \sum_{x = 1}^{n} |x| \cdot \mathbb{P}(Y_n = x)$$

Now I am stuck calculating $\mathbb{P}(Y_n = x)$, it gets messy with different cases to consider. If $x = 1$, it must be that all the draws from $1$ to $n$ fail (no black ball), but that still depends on $k$..and so on, with more cases. What am I not seeing?

Any help would be really great!


Using @LostStatistician18's hint, we first have $$\mathbb{E}(\mathbb{1}_{\{X_i \neq X_{i+1}\}}) = 0 \cdot \mathbb{P}(X_i = X_{i+1}) + 1 \cdot \mathbb{P}(X_i \neq X_{i+1}) \\ = \mathbb{P}(X_i = 1, X_{i+1} = 0) + \mathbb{P}(X_i = 0, X_{i+1} = 1) = 2 \ \frac{k (n-k)}{n (n-1)}$$

for $i = 1,\dots,(n-1)$. So now we get $$\mathbb{E}(Y_n) = 1 + \sum_{i = 1}^{n-1} \mathbb{E}(\mathbb{1}_{\{X_i \neq X_{i+1}\}}) = 1 + \frac{2 k (n-k)}{n}$$

  • $\begingroup$ What is $N$ here? Do you mean $n$ or is $N$ some random variable? $\endgroup$ May 22, 2020 at 16:59
  • $\begingroup$ I mean $n$, edited it now! $\endgroup$
    – 9Sp
    May 22, 2020 at 17:03

1 Answer 1


Just a hint: Although you are proposing to calculate the expectation using the definition $E(Y) = \sum_{y \in Y(\omega)} y P(Y=y)$, you might also try using the linearity of the expectation in this case.

$$ E(Y) = 1 + \sum_{i=1}^{n-1} E 1_{\{X_i \ne X_{i+1}\}} $$ The expectation of the indicator variables can be calculated more easily as they only take the values 0 and 1. To calculate the variance, note that generally if $Y= \sum_{i=1}^n X_i$, then $$ Var(Y) = \sum_{i=1}^n Var(X_i) + 2 \sum_{1\le i < j \le n} Cov(X_i,X_j). $$

In your case the $X_i$ are random variables taking the values 0 and 1, and so these variances/covariances can also be more easily calculated.

Going to the trouble of determining the entire distribution of $Y$ would be much tougher in this case (although could certainly be done too with some hard work).

  • $\begingroup$ Thanks a lot for your answer! I somehow completely forgot that expectations are linear :D I have edited my question to include your hint, is it correct? $\endgroup$
    – 9Sp
    May 22, 2020 at 19:49
  • $\begingroup$ Nice! That looks OK to me $\endgroup$ May 22, 2020 at 22:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .