Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Can more than one student attack the same problem? I believe this is the case. –  dmm Jul 29 '12 at 23:55
    
If there are more problems than students then $\dbinom d k = 0$, but the expected number of solved problems is not $0$. –  Michael Hardy Jul 29 '12 at 23:58
    
One could doubt the realism of all problems being equally difficult for all students. –  Michael Hardy Jul 29 '12 at 23:59
    
This is a duplicate (I remember having answered the other question with the short solution, the one which uses linearity of expectation like @PinkElephants below). –  Did Jul 30 '12 at 6:42

4 Answers 4

up vote 1 down vote accepted

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)$

share|improve this answer

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.

share|improve this answer
    
Isn't your bulleted list the event that at least $j$ problems are solved, rather than that excatly $j$ problems are solved? –  Michael Hardy Jul 30 '12 at 0:06
    
@MichaelHardy: Thanks, I believe I've fixed the problem now. –  Clive Newstead Jul 30 '12 at 0:17

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]$.

share|improve this answer

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 $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.