Expected number of days of watching movie

183 Views Asked by At

Let us suppose I have a list of $n$ movies and each day I chose a subset of this movies where the probability of choosing any movie from the list is p . Now , what would be the expected number of days it would take to watch all of the $n$ movies ? A movie can watched again on another day but we want the day when we have at least watched each movie once .

1

There are 1 best solutions below

0
On BEST ANSWER

This looks like a variation of the coupon collector problem, but I don't see a way to use its elegant method here.

Let $a_{t}$ be the probability that after day $t$ , all movies have been seen ($t=0,1 \cdots$). Let $q=1-p$

Then $$a_{t}= (1-q^t)^n$$

Let $T$ be the amount of days it took to see al movies. Then

$$P(T \ge t)=1-a_{t-1}=1-(1-q^{t-1})^n$$

But $$E(T)=\sum_{t=1} P(T \ge t)=\sum_{u=0} 1- (1-q^u)^n $$

And

$$ 1- (1-q^u)^n =1 - \sum_{j=0}^n {n \choose j} (-1)^j q^{ju}=\sum_{j=1}^n {n \choose j} (-1)^{j+1} q^{ju}$$

$$E(T) = \sum_{j=1}^n {n \choose j} (-1)^{j+1} \sum_{u=0} q^{ju} = \sum_{j=1}^n {n \choose j} (-1)^{j+1} \frac{1}{1-q^j}$$

I wonder if this can simplified

Added: I think that this is basically equivalent to this question