Markov Bound on Total Cheese Weight

Probability · Easy · Free problem

Jon makes

00$ blocks of cheese, where each block's weight (in grams) is drawn independently from an $\text{Exponential}(1/250)$ distribution -- meaning each block has an expected weight of
50$ grams. Let $T_{100}$ denote the total weight of all
00$ blocks.

Using Markov's Inequality, find an upper bound for $P(T_{100} > 26{,}000)$.

Hints

  1. Weights are non-negative, so Markov's Inequality applies -- you only need the expected value of $T_{100}$.
  2. Markov's Inequality states $P(X > a) \leq E[X]/a$; compute $E[T_{100}]$ using linearity of expectation and the mean of an exponential.
  3. For $\text{Exponential}(\lambda)$ with rate $\lambda = 1/250$, the mean is
    /\lambda = 250$; $E[T_{100}] = 100 \times 250 = 25{,}000$.

Worked Solution

How to Think About It: Markov's Inequality applies to any non-negative random variable and gives a quick upper bound using only the mean. Weights are non-negative, and the total weight $T_{100}$ is a sum of non-negative terms -- so Markov applies immediately. The question is already written in exactly the form Markov requires: $P(X > a) \leq E[X]/a$. Just plug in.

Quick Estimate: The mean total weight is

00 \times 250 = 25{,}000$ grams. We are asking about exceeding
6{,}000$ grams, which is only $4\%$ above the mean. Markov will give a weak bound here (close to
$) because it uses no information about the distribution beyond the mean. Sanity check: the bound must be at most
$, and
5{,}000 / 26{,}000 \approx 0.96$, which confirms the answer is in the right range.

Approach: Direct application of Markov's Inequality.

Formal Solution:

Markov's Inequality states: for any non-negative random variable $X$ and $a > 0$,

$P(X > a) \leq \frac{E[X]}{a}$

Since each $W_i \sim \text{Exponential}(1/250)$, the mean of each block is $E[W_i] = 250$ grams. By linearity of expectation:

$E[T_{100}] = E\left[\sum_{i=1}^{100} W_i\right] = 100 \cdot 250 = 25{,}000$

Applying Markov's Inequality with $a = 26{,}000$:

$P(T_{100} > 26{,}000) \leq \frac{E[T_{100}]}{26{,}000} = \frac{25{,}000}{26{,}000} = \frac{25}{26}$

Answer: $P(T_{100} > 26{,}000) \leq \dfrac{25}{26} \approx 0.962$.

Intuition

Markov's Inequality is the simplest -- and weakest -- tail bound in probability. It requires only non-negativity and a finite mean, and it gives $P(X > a) \leq E[X]/a$. The bound is sharp (can be achieved) by a distribution that puts all its mass at $0$ and $a$, which is why it is so weak in practice: it has no idea how the mass is distributed between $0$ and $a$.

In this problem, we are asking about exceeding a threshold that is only $4\%$ above the mean, and Markov gives us a bound of $96\%$ -- almost no information. Compare this to what the CLT would give: $T_{100}$ is a sum of

00$ i.i.d. exponentials with mean
50$ and variance 50^2$, so $T_{100} \approx N(25{,}000, 100 \times 250^2)$. The standard deviation is $\sqrt{100} \times 250 = 2{,}500$, and 6{,}000$ is only $0.4$ standard deviations above the mean, giving $P \approx 34\%$ -- much tighter than Markov's $96\%$. The lesson: Markov is a proof tool and a fallback; when you know the distribution, use it.

Open the full interactive solver →