One hundred doors, one dollar behind each door. Roll a one-hundred dice for one hundred times. You can take the dollar after the door whose number is rolled out but the dollar is not replaced. What's the expectation?
What I tried:
I tried to write a general formula taking ideas from the Coupon collector problem. I found that the E[X]= (N-n)/N where N is the total number of doors and n is the amount we've opened but I don't think that works. Any advice would be appreciated.
On
Here is a slightly different approach by way of enrichment. Say the die has $n$ sides and there are $n$ doors. The answer would appear from first principles to be
$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{n^n} \sum_{q=1}^n q {n\choose q} q! {n\brace q}.}$$
Here $q$ gives the number of different values that have been seen where $1\le q\le n.$ We choose these from the $n$ available ones and partition the constituents of the sequence of rolls into $q$ non-empty sets (Stirling number), one for each type of element, where the order of the sets matters (factor $q!$ as we map each element to the places where it appears in the sequence). Any door contributes one dollar the first time it is opened and zero dollars thereafter, so we seek the expectation of the number of different values that have appeared. Note also that
$$\frac{1}{n^n} {n\choose q} q! {n\brace q}$$
gives the probability of seeing $q$ different values.
We use the EGF of the Stirling numbers to compute the sum:
$$n! [z^n] \frac{1}{n^n} \sum_{q=1}^n q {n\choose q} q! \frac{(\exp(z)-1)^q}{q!} \\ = n! [z^n] \frac{1}{n^n} \sum_{q=1}^n q {n\choose q} (\exp(z)-1)^q \\ = n\times n! [z^n] \frac{1}{n^n} \sum_{q=1}^n {n-1\choose q-1} (\exp(z)-1)^q \\ = n\times n! [z^n] (\exp(z)-1) \frac{1}{n^n} \sum_{q=0}^{n-1} {n-1\choose q} (\exp(z)-1)^q \\ = n\times n! [z^n] (\exp(z)-1) \frac{1}{n^n} \exp((n-1)z) \\ = \frac{n}{n^n} \times n! [z^n] (\exp(nz)-\exp((n-1)z)) = \frac{n}{n^n} (n^n - (n-1)^n).$$
This gives for the desired answer
$$\bbox[5px,border:2px solid #00A000]{ n \left( 1 - \left(\frac{n-1}{n}\right)^n\right)}$$
which agrees with the response that was first to appear. We also have
$$\lim_{n\to\infty} \left(1-\frac{1}{n}\right)^n = \frac{1}{e}$$
so this becomes $\sim n \left(1-\frac{1}{e}\right).$
For $1\leq i\leq100$ let $X_i$ be a random variable if door number $i$ opened and $0$ otherwise. The we want $E(\sum X_i)=\sum E(X_i)$ by linearity of expectation. But $E(X_i)$ is just the probability that door $i$ is opened, or $1$ minus the probability that it is never opened.
$E(X_i)$ is the same for all for all $i$ so we have $$100\Pr(\text{Door 1 isn't opened})=100(1-.99^{100})\approx100\left(1-{1\over e}\right)$$