3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
3
  • 1
    $\begingroup$ Thanks!!! I forget to say that $\alpha \in [0,1]$. But, I got the idea! $\endgroup$ Dec 20 '20 at 17:53
  • 1
    $\begingroup$ No problem. We should add the $a=1$ case, although it is not hard. In this case, $P(T>n) = 0$, so $P(T\le n) = 1$. Therefore, $E[T] \le n P(T\le n) = n$, as desired. $\endgroup$
    – Satana
    Dec 20 '20 at 17:57
  • $\begingroup$ @GuilhermeCosta Actually, I believe the $a=1$ case is covered by my answer. (But certainly doesn't require that full argument, evidenced by the shorter solution in the comments.) For $a=0$, it implies that $P(T>x)=1$ for all $x>0$. Therefore, $E[T]\ge x\cdot P(T>x) = x$ for all $x>0$. This implies that $E[T]$ is unbounded, and we write $E[T]=\infty$. Although dividing by $0$ is undefined, if we formally set $\infty=1/0$, then the statement is true in the $a=0$ case as well. $\endgroup$
    – Satana
    Dec 20 '20 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.