Suppose there are N possible independent events. At each step each event can occur with probability p. Suppose, that at some particular step, event #1 has occurred exactly k times already. I need to find expected number of events, which occurred at least once at this step.

My solution is following: starting from step k, I calculated probability p1 that event #1 has already occurred exactly k times at this step. Then I need to calculated expected number of events that occurred at least once (I haven't found how to do that yet). Then I will multiply this result with p1 and continue like this until p1 becomes too small for a given step.

Can someone please advice me on how to calculate expected number of events, which occurred at least once at every step, and also how to make this algorithm computationally efficient.

Thank you!


Note: if the occurrence of the events are independent each step, then they cannot be mutually exclusive. Multiple events may occur in a single step (or none may).

Let $X$ be the number of events other than event #1 that have occurred at least once.

Let $Y$ be the number of steps that have occurred when the event #1 has occurred exactly $k$ steps.

$$X\in [0..N-1], Y\in[k..\infty)$$

By the law of total expectation:

$$\operatorname{E_X}[X]= \operatorname{E_Y}[\operatorname{E_{X\mid Y}}[X\mid Y]]$$

Let us split the problem.

So, first up: $\operatorname{E_{X\mid Y}}[X\mid Y]$

$$\operatorname{E_{X\mid Y}}[X\mid Y]=\operatorname{E_{X \mid Y}}[\sum_{i=2}^n X_i \mid Y] \\ = \sum_{i=2}^n \operatorname{E_{X_i \mid Y}}[X_i \mid Y]$$ Where $X_i\in [0,1]$ is the binary variable, that event $i$ has occurred at least once.

$$\operatorname{E_{X_i\mid Y}}[X_i\mid Y] = 0 \operatorname{P}(X_i=0\mid Y=y) + 1 \operatorname{P}(X_i=1\mid Y=y)$$

If $p$ is the probability of event $i$ occurring in any step, then the probability of it not occurring in $y$ steps is: $$\operatorname{P}(X_i=0\mid Y=y) = (1-p)^y$$

The probability that it occurs at least once is then: $$\operatorname{P}(X_i=1\mid Y=y) = 1-(1-p)^y$$

Thus $$\operatorname{E_{X_i\mid Y}}[X_i\mid Y] = 1-(1-p)^y$$

$$\therefore \operatorname{E_{X\mid Y}}[X\mid Y] = (n-1) (1-(1-p)^y)$$

Now, find: $\operatorname{E_Y}[\operatorname{E_{X\mid Y}}[X\mid Y]]$

$$\operatorname{E_Y}[\operatorname{E_{X\mid Y}}[X\mid Y]] = \sum_{y=k}^{\infty} \operatorname{E_{X\mid Y}}[X\mid Y]\;\operatorname{P}(Y=y) \\ = (n-1) \sum_{y=k}^{\infty} (1-(1-p)^y)\;\operatorname{P}(Y=y)$$

We need to determine: $\operatorname{P}(Y=y)$

We have event #1 occurring $k$ times (given), and not occurring $y-k$ times. Also the $k^{th}$ occurrence must be on the last step; while the remaining $k-1$ occurrences may be permuted anywhere within the remaining $y-1$ steps.

$$P(Y=y) = {y-1\choose k-1} (1-p)^{y-k}p^k$$


$$\operatorname{E_X}[X] = (n-1) \sum_{y=k}^{\infty} {y-1\choose k-1} (1-(1-p)^y)(1-p)^{y-k}p^k$$

According to WolframAlpha, this series has a closed form:

$$\operatorname{E_X}[X] = (n-1)\left(1- \frac{(1-p)^k}{(2-p)^k}\right)$$

  • $\begingroup$ Thank you for detailed explanation! Can you please clarify, why you wrote the following: EXi∣Y[Xi∣Y]=1−(1−p)y∴EX∣Y[X∣Y]=(n−1)(1−(1−p)y), shouldn't we use combination here? $\endgroup$ – Tofig Hasanov May 14 '14 at 5:26
  • 1
    $\begingroup$ @TofigHasanov The expectation of a sum of independent random variables is simply the sum of the expectations of the independent random variables. If you roll three dice and sum the results, the expected value is three times the expected value of any one die's result. $E[\sum\limits_{i=1}^3 D_i] = 3 E[D_1] = 3\times{3.5} = 10.5$ $\endgroup$ – Graham Kemp May 14 '14 at 11:48
  • $\begingroup$ Thanks! That makes sense. Wolfram formula is very elegant as well! $\endgroup$ – Tofig Hasanov May 15 '14 at 6:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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