Expected probablility in dice tossing

Question

The dice has m faces: the first face of the dice contains a dot, the second one contains two dots, and so on, the m-th face contains m dots. When the dice is tossed, each face appears with probability 1/m. Also each toss is independent from others.

We need to calculate the expected maximum number of dots we could get after tossing the dice n times.

Example : Let m=2 and n=2 then answer is 1.75000

Explanation : If you've made two tosses:

You can get 1 in the first toss, and 2 in the second. Maximum equals to 2.
You can get 1 in the first toss, and 1 in the second. Maximum equals to 1.
You can get 2 in the first toss, and 1 in the second. Maximum equals to 2.
You can get 2 in the first toss, and 2 in the second. Maximum equals to 2.

The probability of each outcome is 0.25, that is expectation equals to: (2+1+2+2)(0.25)=7/4

Answer 1

Let $x_i(\omega) \in \{1,...,m\}$ be the $i$th throw, with $i\in \{1,...,n\}$. Let $\mu(\omega) = \max_i x_i(\omega)$. You want to compute $E \mu$.

One way is to compute $p\{\omega | \mu(\omega) \le l \}$ for $l=1,...,m$. We see that $\mu(\omega) \le l$ iff $x_i(\omega) \in \{1,..., l\}$ for all $i$, and so $p\{\omega | \mu(\omega) \le l \} = ( { l \over m } )^n$.

Finally, we have \begin{eqnarray} E\mu &=& \sum_{k=1}^m k p\{\omega | \mu(\omega) = k\} \\ &=& \sum_{k=1}^m \sum_{l=1}^k p\{\omega | \mu(\omega) = k\} \\ &=& \sum_{l=1}^m \sum_{k=l}^m p\{\omega | \mu(\omega) = k\} \\ &=& \sum_{l=1}^m p\{\omega | \mu(\omega) \ge l\} \end{eqnarray}

Since $p\{\omega | \mu(\omega) \ge l\} = 1-p\{\omega | \mu(\omega) < l\} = 1-p\{\omega | \mu(\omega) \le l-1\}$, we have $E \mu = \sum_{l=1}^m (1-( { l-1 \over m } )^n) $.

For $m=n=2$, we have $E \mu = 2- ({1 \over 2})^2$.

Answer 2

I'm sure there's a simple way, but I couldn't think of it.

There are $m^n$ possible outcomes.

There is $a_1 = 1^n$ outcomes so that the max is $1$ (strings of length $n$ using $1$ symbol so that the symbol $1$ is used)

There are $a_2 = 2^n-1^n$ outcomes so that the max is $2$ (strings of length $n$ using $2$ symbols so that the symbol $2$ is used).

There are $a_3 = 3^n - a_2$ outcomes so that the max is $3$.

There are $a_k = k^n - a_{k-1}$ outcomes so that the max is $k$.

So what you want is:

$$\frac{1}{m^n}\sum_{k=1}^m a_k$$

Where:

$$a_k = (-1)^k\sum_{r=1}^k (-r)^n$$

Answer 3

Hints:

For any random variable $X$ that takes values in $\left\{ 0,1,\cdots\right\} $ only we have: $$\mathbb{E}X=\sum_{k=1}^{\infty}P\left\{ X\geq k\right\} $$

Next to that $P\left\{ X\geq k\right\} =1-P\left\{ X<k\right\} $