For example, if I roll a $6$ side die $4$ times, and get $\{1,1,3,5\}$. The number of different outcomes would be $3$. So if rolling a fair $k$-side die $n$ times, what is the number of different outcomes I would get in expectation?
The problem looks like coupon collector, but it is asking the destination of a random walk instead of number of steps.
Any help would be appreciated!
Let $X$ be the number of different numbers rolled, and write $$ X=\sum_{i=1}^kX_i$$ where $X_i$ is the indicator random variable of the event that the $i$th number is among the numbers rolled. Then $$ \mathbb{E}[X]=\sum_{i=1}^k\mathbb{P}(X_i=1)=k\mathbb{P}(X_1=1)$$ and $$ \mathbb{P}(X_1=1)=1-\Big(\frac{k-1}{k}\Big)^n$$ and so $$ \mathbb{E}[X]=k\Big(1-\Big(\frac{k-1}{k}\Big)^n\Big)$$