Probability of choosing the same number

probability

There are $k$ choices and $n$ people.

  • First person will choose a random number.
  • Second person will choose a random number and will have $1\over k$ probability to choose the number chosen by others.
  • Third person will have $2\over k$ probability.
  • $n$-th person will have ${n-1} \over k$ probability.

Geting the probability that way will be way too hard, let's get the probability of not having two identical choices:

  • First person will choose a random number (and have $k \over k$ probability).
  • Second person will choose a random number and have $k-1 \over k$ to choose the number not chosen by others.
  • Third person will have $k-2 \over k$ probability.
  • $n$-th person will have $k-n+1 \over k$ probability.

Probability ($p$) is then: $$ p=1-{{k(k-1)(k-2)(k-3)...(k-n+3)(k-n+2)(k-n+1)} \over {k^n}}=1-{k! \over {k^n(k-n)! }} $$


Hint: find the probability that all the numbers are distinct.

Related

How to prove $x^{n}$ is not uniformly continuous
Calippo, toothpaste and milk .. packing
Nilpotent matrices with same minimal polynomial and nullity
Prove that if $\gcd(a,b)=1$ then $\gcd(ab,c) = \gcd(a,c) \gcd(b,c)$
Showing $\varphi(t)\neq 0$ when $\varphi$ is a characteristic function of an infinitely divisible distribution
rational approximation of $\pi$, where denominator lies in $[a,b]$
Average shortest distance between some random points in a box
Projection of a point onto a convex polyhedra
Understanding a proof that $2x + 3y$ is divisible by $17$ iff $9x + 5y$ is divisible by $17$
Multivariable Delta Epsilon Proof $\lim_{(x,y)\to(0,0)}\frac{x^3y^2}{x^4+y^4}$ --- looking for a hint
Find the limit $\displaystyle\lim_{n\rightarrow\infty}{(1+1/n)^{n^2}e^{-n}}$?
$f'(c) \ge 0 , \forall c \in (a,b)$ then $f$ is increasing in $[a,b]$ , proof of this without Mean Value theorem