1
$\begingroup$

A group of $d$ students tries to solve $k$ problems in the following way. Each student picks only one problem at random and tries to solve it. Assume that all the attempts have probability $p$ of success and are independent of each other and of the students choice. Let $X$ denote the number of solved problems. Find $\Bbb E(X)$.

I am not sure if I just overestimating this, but would the answer simply be $E(X) = \dbinom{d}{k}p$

Because there are exactly $\dbinom{d}{k}$ independent trials and p is the success rate

Thank you

  • 0
    Can more than one student attack the same problem? I believe this is the case.2012-07-29

4 Answers 4

1

For $1 \leq i \leq k$, let $X_i$ be the random variable with value $1$ if the $i$-th problem is solved, $0$ otherwise. We have $X = \sum_{i=1}^k X_i$, and thus $\mathbb{E}(X) = \sum_{i=1}^n \mathbb{E} (X_i)$. The $X_i$'s are obviously identically distributed (they are not independent, but that's not a problem), so we simply have to find the ditribution of $X_1$ (either $P(X_1)=0$ or $P(X_1)=1$ will do).

Each student has a probability $p\frac{1}{k}$ of solving the first problem, and as $d$ students make independent attempts, the probability that it stays unsolved is $\left( 1-\frac{p}{k}\right)^d$. Thus $P(X_1=0) = \left( 1-\frac{p}{k}\right)^d$ and $\mathbb{E}(X_1) = 1-\left(1-\frac{p}{k}\right)^d$.

Finally, we get $\mathbb{E}(X) = k\left[ 1-\left(1-\frac{p}{k}\right)^d\right]$.

1

The probability that $\ge j$ problems are solved is the probability that:

  • At least one student solves one of the problems
  • At least one of the remaining students solves a second problem

$\qquad \qquad \vdots$

  • At least one of the remaining students solves a $j^{\text{th}}$ problem

And these events are all independent. And the probability that any given student chooses and solves any given problem is $\dfrac{p}{k}$, so we obtain:

$\mathbb{P}(X \ge j) = dk\dfrac{p}{k} \cdot (d-1)(k-1)\dfrac{p}{k} \cdot (d-j+1)(k-j+1) \dfrac{p}{k}$

which is precisely $\displaystyle \dfrac{p^j}{k^j} \binom{d}{j} \binom{k}{j}$.

Hence we have

$\displaystyle \mathbb{E}(X) = \sum_{j=0}^k \mathbb{P}(X \ge k) = \sum_{j=0}^k \dfrac{p^j}{k^j} \binom{d}{j} \binom{k}{j}$

I'm not sure how you could simplify this, but no doubt there is a way.


Another way of visualising it is this: you have a $d \times k$ grid, where the $d$ rows represent students and the $k$ columns represent the problems. You select one square from each row, and you need to work out the expected number of columns which have at least one square chosen from them.

  • 0
    @MichaelHardy: Thanks, I believe I've fixed the problem now.2012-07-30
1

Fix one of the problems. The probability that a particular student solves that problem is $\frac{p}{k}$ (the probability that the student selected the fixed problem, multiplied by the probability that the student solved the problem correctly). Since there are $d$ students, the probability that NOBODY solved the fixed problem correctly is $\left(1-\frac{p}{k}\right)^d$. It follows that the probability the fixed problem is solved by at least one person is $1-\left(1-\frac{p}{k}\right)^d$. The expected number of problems that are solved is then $k\left(1-\left(1-\frac{p}{k}\right)^d\right)$

1

The probability of a particular problem being solved is the sum of the probability of $j$ students choosing that problem, $\binom{d}{j}\left(\frac1k\right)^j\left(1-\frac1{k}\right)^{d-j}$, times the probability of at least one of the $j$ solving the problem, $1-(1-p)^j$. That is, $ \begin{align} \sum_{j=0}^d\binom{d}{j}\left(\frac1k\right)^j\left(1-\frac1{k}\right)^{d-j}(1-(1-p)^j) &=1-\sum_{j=0}^d\binom{d}{j}\left(\frac{1-p}k\right)^j\left(1-\frac1{k}\right)^{d-j}\\ &=1-\left(1-\frac{p}{k}\right)^d \end{align} $ By the linearity of expectation, the expected number of problems solved would be $ k-k\left(1-\frac{p}{k}\right)^d $