Calculate the expected value of the number of different digits

combinatoricsexpected valueinclusion-exclusion

Question. $n$ is a $m$-digit number. ($m$ can start with zero.) Let $P(n)$ the number of different digits in $n$. What is the expected value of $P(n)$? (For example, $P(12341234)=4$.)

My approach.

Let X:={$(n, q)$|$n$ is $m$-digit number, $q$ is the set of different digits in $n$}. (For example, $(123123, \left\{ 1, 2, 3\right\}) \in X$)

Let's use double counting.

It is clear that $|X| = 10^m$.

I think when I calculate the sum of $|q|$ in all of the elements of $X$, then I can get the answer.

What should I do to calculate it? (Maybe I need the inclusion–exclusion principle.)

Best Answer

Use the linearity of expectation. What is the chance that $1$ is present? That is the expected value of an indicator variable.

Related Question