WTS) Geometric distribution is the only discrete memoryless distribution

Question

I want to prove that if a discrete distribution is memoryless, the distribution must be geometric. I read up on older posts asking this question, but I couldn't follow any of the answers. How should I get started on this proof? Any hints or steps would be appreciated.

Answer 1

First let's prove that the geometric is memoryless :

$$\mathbb{P}[X > n+k \mid X > k] = \frac{\mathbb{P}[X > n+k,X > k]}{\mathbb{P}[X > k]} = \frac{\mathbb{P}[X > n+k]}{\mathbb{P}[X > k]} = $$

$$ = \frac{(1-p)^{n+k}}{(1-p)^{k}} = \mathbb{P}[X>n]$$

Viceversa, if we have a distribution such that for every $k$

$\mathbb{P}[X>n+k \mid X > k] = \mathbb{P}[X > n]$ holds,it must holds for $k=1$.

In first place we can notice that $$\mathbb{P}[X>n] = \mathbb{P}[X>n+1 \mid X > 1] = \frac{\mathbb{P}[X > n+1]}{\mathbb{P}[X>1]}$$

If we denote with $p:= 1 - \mathbb{P}[X>1]$ we have :

$$\mathbb{P}[X>n+1] = \mathbb{P}[X>n]\mathbb{P}[X>1] =$$

$$(1-p)\mathbb{P}[X>n] = (1-p)^{2}\mathbb{P}[X>n-1] \cdots = (1-p)^{n+1}$$

Which gives :

$$\mathbb{P}[X = n] = \mathbb{P}[X>n-1] - \mathbb{P}[X>n] = (1-p)^{n-1}-(1-p)^{n} = p(1-p)^{n-1}$$

Hence, the geometric distribution.

Let me know if there are flaws or different notation which you are not comfortable with.