 |
|---|
| Last updated on: Sat Aug 15 18:22:53 IST 2026 |
| Last updated on: Sat Aug 15 18:22:53 IST 2026 |
Proof: The result is obvious if $V(X)=0$ or $V(Y)=0.$ So let's consider the case where $V(X), V(Y)>0.$
Define $Z_1 = \frac{X-E(X)}{V(X)}$ and $Z_2 = \frac{Y-E(Y)}{V(Y)}.$ We know that $V(Z_1+Z_2)\geq 0.$ Derive from this $\cov(X,Y)\geq -1.$ Similarly, derive $\cov(X,Y)\leq 1$ from $V(Z_1-Z_2)\geq 0.$ Also equality holds iff $V(Z_1+Z_2)=0$ or $V(Z_1-Z_2)=0$, i.e., if $Z_1+Z_2$ or $Z_1-Z_2$ is degenerate. So we have either $P(Z_1+Z_2=k)=1$ or $P(Z_1-Z_2=k)=1$ for some $k\in{\mathbb R}.$ In both cases we have $P(aX+bY=c)=1$ for some constants, $a,b,c,$ as required. [QED] It is instructive to think about the Cauchy-Schwarz inequality from a geometric perspective. If we take two vectors , $\v u$ and $\v v$ in 2D or 3D, we have the identity $$\v u\bullet\v v = \| \v u\| \cdot \|\v v\|\cos \theta,$$ where $\theta$ is the angle between the two vectors. |
|---|
EXERCISE 1: $X$ is a nonnegative random variable with finite second moment. Show that $P(X>0)\geq \frac{E^2(X)}{E(X^2)}.
Hint:
Think of $X$ as $X1_{X>0}.$$
EXERCISE 2: Let $X_1,...,X_n$ be random variables with finite second moments. Show that $$V\left(\sum X_i\right) \leq \left(\sum\sqrt{V(X_i)}\right)^2.$$
EXERCISE 3: Show that $E|X-E(X)|\leq \sqrt{V(X)}$ for any random variable $X$ with finite second moment.
EXERCISE 4: If $E(X^2)=E(Y^2) = E(XY),$ then show that $P(X=Y)=1.$
EXERCISE 5: Average salary in a company is Rs 50,000. It is claimed that 30% of the employees are getting a salary of Rs 250,000 or more. Can this claim be true?
Proof: Compare with $Y = \left\{\begin{array}{ll} \epsilon&\text{if }x\geq \epsilon\\ 0&\text{otherwise.}\end{array}\right..$
Note that $Y\leq X.$ Hence $E(Y^k)\leq E(X^k).$ But $E(Y^k) = P(X\leq \epsilon) \epsilon^k.$ Hence the result. [QED] A point about the inequalities in the above theorem. There are two inequalities, one inside the probability, and one outside. Both are mixed inequalities. Obviously, you may make the first inequality strict (thereby weakening the result). However, you may not replace the other inequality with a strict one, because otherwise you will get $0 < 0$ for the degenerate random variable $X\equiv0$. The following variant of the Markov inequality is due to Chebyshev.| Chebyshev is also credited with designing a quadruped robot-like linkage. |
Proof: This is just Markov inequality with $k=2$ applied to the random variable $|X-E(X)|.$ [QED]
EXERCISE 6: Give a counterexample to show that the nonnegativity assumption in the inequality may not be dropped.
EXERCISE 7: Let $X$ be any random variable (not necessarily nonnegative). Show that $$\forall \epsilon>0~~P(X\geq \epsilon) \leq \frac{E(X^2)}{\epsilon^2}.$$
EXERCISE 8: If you have solved the above exercise, you can also show that for any nonnegative random variable $X$ and any $\epsilon>0$ we have for each $k\in{\mathbb N},$ $$\forall \epsilon>0~~P(X\geq \epsilon) \leq \frac{E(X^k)}{\epsilon^k}.$$ Will higher values of $k$ necessarily give you better bounds?
EXERCISE 9: Prove that $\forall \epsilon>0~~\frac{1}{\sqrt{2\pi}}\int_{-\epsilon}^ \epsilon e^{-x^2/2}\, dx \leq \frac{1}{\epsilon^4}.$
Here we sort an array of numbers by picking a random element from the array, and dividing the rest into two groups, depending on whether a number is $\leq$ or $>$ than the picked element. Then we do the same thing recursively to both the groups separately, and stop when the entire array is sorted.Let $X$ denote the number steps in a Las Vegas algorithm. We often know $E(X)$ as a function of the input size. For instance, in the randomised quicksort algorithm $E(X) = n\log n,$ where $n$ is the length of the array (proof not part of this course). Then Markov inequality helps us to get an upper bound on the probability that the algorithm will take too long. This allows engineers to guarantee system satibility without knowing the exact distribution of $X.$
EXERCISE 10: Let $X$ be the number of steps needed in a randomised quick sort algorithm. It is known that $E(X)=n\log n$ if the $n$ is the length of the array to be sorted. Find an upper bound for $P(X>10^6)$ if the input array has length $10^4.$
EXERCISE 11: (Router overload) A router receives a random number ($X$) of packets every millisecond. We know from the past that $E(X)=50.$ We do not know the distribution of $X.$ The router's buffer can hold 250 packets before overflowing. Help the network engineer to provide an uppr bound to the failure rate, $P(X\geq 250).$
EXERCISE 12: (Liquidity crisis) A bank has a large portfolio of small business loans. $X=$ number of defaulters in a single month. Past experience shows $E(X)=2M.$ Liquidity crisis will arise if $X\geq 20M.$ Bound the probability of that.
EXERCISE 13: (System downtime) A financial system tracks $X$ the downtime of the system per year. Past data shows $E(X)=15$ minutes. Crash would result if $X\geq 2$ hours. Bound its probability.
EXERCISE 14: (Volatile market) When the market is highly volatile market, an investment fund's historical data becomes useless. The only certain information is the current daily expected loss $E(X)=100,000.$ Upper bound $P(X\geq 1,000,000).$
EXERCISE 15: (Primality testing) A randomised primality testing algorithm called the Miller Rabin test applies a random experiment on an input integer $n.$ The (random) output is either "Composite" or "Prime". There is theoretical guarantee that if it says "Composite", then the input is indeed composite. But if it says "Prime" then the input is composite with 0.25 probability.
Mathematically, let $$X = \left\{\begin{array}{ll}1&\text{if }\mbox{error}\\ 0&\text{otherwise.}\end{array}\right..$$ Then we have $E(X) = \frac 14.$ We run this experiment $k$ times independently (on the same input), and we output "Composite" if at least one run says so. Otherwise, we say "Prime". Give an uppoer bound on the probability that this battery of $k$ tests makes an error. [This problem can also be solved without explicit use of Markov inequality.]