Probability of i.i.d random variables not being equal to each other

Question

Let $X_1, X_2, \dots, X_m$ be i.i.d random variables uniformly distributed on the set $\{1,2, \dots, n\}$. What is $\mathbb{P}(X_1\neq X_2 \neq \dots \neq X_m)$?

Edit: n > m

Answer 1

• For $m>n$, it's just zero because you can't pick $m> n$ distincts numbers out of a set of cardinal n.

• For $m\le n$, notice that

  1. you have $n$ choice for $X_1$,

  2. but then there are $n-1$ choices left for $X_2$,

  3. then $n-2$ choices left for $X_3$,

  4. ...

  5. finally, $n-m+1$ choices left for $X_m$

Putting everything together, the probabilty we're looking for is : $\frac{n}{n}\times\frac{n-1}{n}\times\frac{n-2}{n}...\times\frac{n-m+1}{n}=\frac{n!}{n^m (n-m)!}$

Answer 2

If $m>n$; then the answer is $0$, because you'd have to choose $m$ different numbers out of $\{1,\dots,n\}$, which is obviously impossible.

If $n\ge m$, then you need to choose, with order, $m$ many numbers out of $\{1,\dots,n\}$ to act as values of $X_1,\dots,X_n$. Do you see how to do this?