0
$\begingroup$

Find the best possible upper bound on $P(X \geq 100)$ if $g_X(10)=10$ ($g_X$ is a generating function), where $X$ is a discrete random variable.

I started by writing the equation to find possible generating function $g_X(10)=(1-p)\cdot10^0+p\cdot10^{100} = 10$.
Its solution is $p = \frac{9}{10^{100}-1}$, hence $P(X\geq 100) = \frac{9}{10^{100}-1}$.

Is it possible to give a better estimate?
It seems to me that it is not, because as we increase the exponent at $p\cdot10^{100}$, (e.g. $p\cdot10^{101}$) , then $p$ decreases, and as we increase the exponent at ($1-p)\cdot10^0$ (e.g. ($1-p)\cdot10^1$), then $p$ is zero or negative.
Although I'm not sure, which is why I'm asking.

$\endgroup$
2
  • $\begingroup$ Are you assuming $X$ is a Bernoulli RV? $\endgroup$ Feb 18 at 15:27
  • $\begingroup$ @GiorgosGiapitzakis It's a discrete random variable, not necessarily one with Bernoulli distribution. $\endgroup$
    – Michał
    Feb 18 at 16:03

1 Answer 1

1
+50
$\begingroup$

From the OP, I guess you assumed that $X$ is non-negative, which implies $$10^X-1 \ge 0.$$

Now, from the Markov's inequality we have

$$\mathbb P (X \geq 100)=\mathbb P (10^X-1 \geq 10^{100}-1) \le \frac{\mathbb E (10^X-1)}{10^{100}-1}=\frac{g_X(10)-1}{10^{100}-1}=\color{blue}{\frac{9}{10^{100}-1}}$$

where recall $g_X(t):=\mathbb E (t^X)$ for $t>0$. This gives the bound you are seeking, which is tight for a random variable $X_0$ with

$$\mathbb P (10^{X_0}-1=10^{100}-1)=\frac{9}{10^{100}-1},\mathbb P (10^{X_0}-1=0)=1-\frac{9}{10^{100}-1}. $$


If $X$ can take negative values, then

$$10^X > 0.$$

In this case, again from the Markov's inequality we have

$$\mathbb P (X \geq 100)=\mathbb P (10^X \geq 10^{100}) \le \frac{\mathbb E (10^X)}{10^{100}}=\frac{g_X(10)}{10^{100}}=\color{blue}{\frac{10}{10^{100}}}.$$

This bound is not tight, but can be approached arbitrarily by the sequence $X_n$ defined as ($n \in \mathbb N$)

$$\mathbb P (10^X-10^{-n}=10^{100}-10^{-n})=\frac{10-10^{-n}}{10^{100}-10^{-n}},\mathbb P (10^X-10^{-n}=0)=1-\frac{10-10^{-n}}{10^{100}-10^{-n}}, $$

for which we have

$$g_{X_n}(10)=10, \mathbb P (X_n \geq 100) = \frac{10-10^{-n}}{10^{100}-10^{-n}} <\frac{10}{10^{100}}.$$

You can see that $\frac{10-10^{-n}}{10^{100}-10^{-n}}$ is increasing in $n$ and tends to the bound $\frac{10}{10^{100}}$ when $n \to \infty$.

$\endgroup$
2
  • $\begingroup$ I do not assume anything about $X$, except that it is a discrete random variable. In other words, X can be negative. Does this change the estimate? In my case $X$ takes $0$ or $100$, just because that seemed the best estimate to me. I once saw a similar question in which there was a hint to use $g_X(t)=E[t^X]$, but I don't know the solution. Also, thanks for your answer. $\endgroup$
    – Michał
    Feb 26 at 18:43
  • 1
    $\begingroup$ @Michał In the updated answer, I considered the case where $X$ can be negative. You may see that the new bound is greater than the bound obtained for the case where $X$ is non-negative, and it is not tight anymore. $\endgroup$
    – Amir
    Feb 26 at 19:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .