Let $T$ a random variable of non-negative integers. Suppose that there is $n \in \mathbb{N}$ and there is $\alpha>0$ such that for all $k \in \mathbb{N}$ we have
$$\mathbb{P}(T >kn) \le (1-\alpha)^k.$$
Prove that
$\mathbb{E}[T] \le \frac{n}{\alpha}$.
I tried to use the sum formula for expectation of nonnegative integer random variables
$$\mathbb{E}[T] = \sum_{i \ge 0}{\mathbb{P}(T > i)},$$
but I can't get a '$\le$' innequalty.
Best Answer
Recall from real analysis that $$\sum_{k=1}^{\infty} (1-a)^k = \frac{1-a}{a}\quad \text{for}\quad 0<a\le1.$$ Consider the random variable $n^{-1} T$. We can split its expectation up as follows: $$E[n^{-1}T] = E[n^{-1} T\cdot \mathbf{1}_{\{T\ge n\}}] + E[n^{-1} T\cdot \mathbf{1}_{\{0\le T<n\}}].$$ Observe that $$E[n^{-1} T\cdot \mathbf{1}_{\{0\le T< n\}}]\le 1\cdot P(0\le T<n) = 1 - P(T\ge n).$$ On the other hand, $S:=\lceil n^{-1} T\rceil\cdot \mathbf{1}_{\{T\ge n\}}$ is a non-negative integer-valued random variable and $$n^{-1} T\cdot \mathbf{1}_{\{0\le T< n\}}\le S.$$ By its definition, note that the following hold:
$S>0$ if and only if $T\ge n$,
$S>k$ if and only if $T>kn$ for $k=1,2,\dots$.
Therefore, using the expectation identity for non-negative integer-valued random variables, \begin{align*} E[S]&= \sum_{k=0}^{\infty} P(S>k) = \sum_{k=0}^{\infty} P(S>k) = P(S>0) + \sum_{k=1}^{\infty} P(S>k)\\ &=P(T\ge n)+ \sum_{k=1}^{\infty} P(T>kn) \le P(T\ge n) + \sum_{k=1}^{\infty} (1-a)^k\\&= P(T\ge n) + \frac{1-a}{a}. \end{align*} Combining the above three inequalities, we have $$E[n^{-1}T] \le [1-P(T\ge n)] + P(T\ge n) + \frac{1-a}{a} = \frac{1}{a}.$$ Complete the proof by multiplying both sides of the above inequality by $n$.