সমাধান — অধ্যায় ৩.১ · Probability Inequalities¶

অধ্যায় ফাইল: part-3-convergence-processes/03-01-probability-inequalities.md (§৭ অনুশীলনী)। সব সংখ্যাগত উত্তর numpy ও বিশ্লেষণাত্মক গণনা দিয়ে যাচাই করা হয়েছে। প্রতীক: $\mathbb{E}[X]=\mu$, $\mathrm{Var}(X)=\sigma^2$, $\bar X_n$ হলো $n$টি নমুনার গড়।

ক · ধারণাগত (conceptual)¶

সমাধান ১ (★)¶

Markov-এর প্রমাণে মূল ধাপ: যেকোনো $a>0$-এর জন্য $X \ge a\cdot\mathbf{1}\{X\ge a\}$ — অর্থাৎ $X\ge a$ হলে ডান পক্ষ $a$, নয়তো $0$, আর $X\ge0$ বলেই $X\ge0\ge$ ডান পক্ষ যখন indicator $0$। এখানেই nonnegativity অপরিহার্য: যদি $X$ ঋণাত্মক হতে পারত, তবে indicator $0$ থাকা অবস্থায় $X<0$ হতে পারত, আর $X \ge a\cdot\mathbf{1}\{X\ge a\}$ ভেঙে যেত। দুই পাশে expectation নিলে $\mathbb{E}[X]\ge a\,P(X\ge a)$, তাই $P(X\ge a)\le\mathbb{E}[X]/a$।

উদাহরণে কেন ভুল হয়। ধরুন $X$ সমান-সম্ভাব্যভাবে $-100$ বা $+100$ নেয়, তাই $\mathbb{E}[X]=0$। তাহলে "Markov bound" $\mathbb{E}[X]/a = 0/a = 0$ দাবি করত $P(X\ge 100)\le 0$ — কিন্তু আসলে $P(X\ge 100)=0.5$! বড় ঋণাত্মক মান গড়কে টেনে নামিয়ে একটি অর্থহীন (এমনকি মিথ্যা) ছাদ দেয়। তাই Markov-এ $X\ge0$ আবশ্যক; ঋণাত্মক হলে আগে nonnegative রূপে (যেমন $\lvert X\rvert$ বা $(X-\mu)^2$) রূপান্তর করে প্রয়োগ করতে হয় — যা ঠিক Chebyshev করে।

সমাধান ২ (★)¶

পরস্পরবিরোধী নয়। Chebyshev বলে "অন্তত $75\%$" — এটি একটি নিম্নসীমা/মেঝে (floor) যা সব distribution-এর জন্য একসাথে খাটতে হবে। Normal-এ প্রকৃত মান $\approx95\%$, যা $75\%$-এর চেয়ে বড় — মেঝে লঙ্ঘিত হয়নি, বরং স্বাচ্ছন্দ্যে মানা হয়েছে।

Chebyshev এত রক্ষণশীল কারণ তাকে সবচেয়ে খারাপ (worst-case) distribution-কেও ঢাকতে হয়। এমন distribution বানানো যায় যেখানে bound প্রায় সমতায় পৌঁছায়: যেমন $X$ নেয় $\mu-k\sigma,\ \mu,\ \mu+k\sigma$ মান যথাক্রমে probability $\tfrac{1}{2k^2},\ 1-\tfrac{1}{k^2},\ \tfrac{1}{2k^2}$-তে — তখন variance ঠিক $\sigma^2$ এবং $P(\lvert X-\mu\rvert\ge k\sigma)=1/k^2$ হুবহু। Normal-এর মতো "ভালো" (পাতলা-tail) distribution সেই worst case থেকে অনেক দূরে, তাই সেখানে bound ঢিলা মনে হয়। সারকথা: সর্বজনীনতার মূল্য রক্ষণশীলতা।

সমাধান ৩ (★★)¶

$g(x)=x^2$ convex, তাই Jensen দেয় $g(\mathbb{E}[X])\le\mathbb{E}[g(X)]$, অর্থাৎ $(\mathbb{E}[X])^2\le\mathbb{E}[X^2]$। পুনর্বিন্যাসে: $$ \mathbb{E}[X^2]-(\mathbb{E}[X])^2 \ge 0. $$ কিন্তু বাঁ পক্ষ ঠিক $\mathrm{Var}(X)$ (2.5-এর গণনা-সূত্র)। তাই এই বিশেষ Jensen ক্ষেত্রটি আসলে variance অঋণাত্মক ($\mathrm{Var}(X)\ge0$) হওয়ার সমতুল্য — যা সত্য কারণ variance একটি বর্গের গড়।

concave $g$-তে দিক উল্টো। $g$ concave মানে $-g$ convex। $-g$-তে Jensen: $(-g)(\mathbb{E}[X])\le\mathbb{E}[(-g)(X)]$, উভয় পক্ষে $-1$ গুণে অসমতা উল্টে যায়: $$ g(\mathbb{E}[X]) \ge \mathbb{E}[g(X)] \qquad (g\ \text{concave}). $$ যেমন $\log$ concave, তাই $\log\mathbb{E}[X]\ge\mathbb{E}[\log X]$ (AM–GM-এর সাধারণ রূপ); $\sqrt{\cdot}$ concave, তাই $\sqrt{\mathbb{E}[X]}\ge\mathbb{E}[\sqrt X]$।

সমাধান ৪ (★★)¶

$\bar X_n$-এর $\mathrm{Var}(\bar X_n)=\sigma^2/n$ (i.i.d.), তাই Chebyshev দেয় $$ P(\lvert\bar X_n-\mu\rvert\ge t)\le \frac{\sigma^2/n}{t^2}=\frac{\sigma^2}{nt^2}\quad(\text{polynomial: }1/n\ \text{হারে নামে}), $$ আর Hoeffding (bounded $[0,1]$, $\sigma^2$ লাগে না) দেয় $2e^{-2nt^2}$ (exponential: $n$ exponent-এ)।

বড় $n$-এ exponential decay polynomial-কে নাটকীয়ভাবে ছাপিয়ে যায়। তবে ছোট $n$-এ Hoeffding সবসময় ছোট নয় — যেমন $n=100,t=0.1$: $$ \text{Hoeffding}=2e^{-2(100)(0.01)}=2e^{-2}\approx 0.271,\qquad \text{Chebyshev (}\sigma^2=0.25\text{)}=\frac{0.25}{100\cdot0.01}=0.25. $$ এখানে Chebyshev সামান্য ছোট! কিন্তু $n$ বাড়ালেই Hoeffding জিতে যায়: $n=400$-তে Hoeffding $=2e^{-8}\approx 6.7\times10^{-4}$, Chebyshev $=0.0625$ — প্রায় ১০০ গুণ ছোট; $n=1000$-তে Hoeffding $\approx 4\times10^{-9}$ বনাম Chebyshev $0.025$। এই exponential হ্রাসই concentration inequality-কে শক্তিশালী করে: শুধু "tail শূন্যে যায়" নয়, "অবিশ্বাস্য দ্রুত যায়" — যা finite-sample গ্যারান্টি (confidence interval, generalization bound) দিতে অপরিহার্য।

খ · গণনামূলক (computational)¶

সমাধান ৫ (★) [E1]¶

$X\ge0$, $\mathbb{E}[X]=50$, $a=200$। Markov: $$ P(X\ge 200)\le \frac{\mathbb{E}[X]}{200}=\frac{50}{200}=\boxed{\tfrac14}=0.25. $$ এই bound সম্ভবত প্রকৃত ভগ্নাংশের চেয়ে অনেক বড়, কারণ Markov কেবল mean (গড়) ব্যবহার করে — আয়ের প্রকৃত আকৃতি (অধিকাংশ মান $200$-এর অনেক নিচে কেন্দ্রীভূত) সম্পর্কে কোনো তথ্য নেয় না, তাই worst-case ঢিলা ছাদ দেয়।

সমাধান ৬ (★★) [E2]¶

$\mu=70,\ \sigma=10$।

(ক) $P(\lvert X-70\rvert\ge 20)$: এখানে $k\sigma=20 \Rightarrow k=20/10=2$। Chebyshev: $$ P(\lvert X-70\rvert\ge 20)\le \frac{1}{k^2}=\frac{1}{4}=\boxed{0.25}. $$

(খ) চাই অন্তত $90\%$ মধ্যে, অর্থাৎ $1-\dfrac1{k^2}\ge 0.9 \Rightarrow \dfrac1{k^2}\le 0.1 \Rightarrow k^2\ge 10 \Rightarrow k\ge\sqrt{10}\approx 3.162$। তাই $$ c=k\sigma=\sqrt{10}\cdot 10\approx \boxed{31.6}. $$ অর্থাৎ Chebyshev গ্যারান্টি দেয় $[70-31.6,\,70+31.6]=[38.4,\,101.6]$-এ অন্তত $90\%$ শিক্ষার্থী। (রক্ষণশীল — Normal হলে $\mu\pm 1.645\sigma$-তেই $90\%$ থাকত।)

সমাধান ৭ (★★) [E3]¶

$X\in\{1,3\}$, প্রতিটি probability $0.5$; $g(x)=x^2$। $$ \mathbb{E}[X]=0.5(1)+0.5(3)=2 \;\Rightarrow\; g(\mathbb{E}[X])=2^2=\boxed{4}. $$ $$ \mathbb{E}[g(X)]=0.5(1^2)+0.5(3^2)=0.5(1)+0.5(9)=\boxed{5}. $$ যেহেতু $4\le5$, Jensen যাচাই হলো ($g$ convex)। Jensen gap $=\mathbb{E}[g(X)]-g(\mathbb{E}[X])=5-4=\boxed{1}$।

gap কি $\mathrm{Var}(X)$? হ্যাঁ — এই বিশেষ $g(x)=x^2$-এ: $$ \mathbb{E}[g(X)]-g(\mathbb{E}[X])=\mathbb{E}[X^2]-(\mathbb{E}[X])^2=\mathrm{Var}(X). $$ এখানে $\mathrm{Var}(X)=5-4=1$, ঠিক gap-এর সমান। (সাধারণভাবে অন্য $g$-তে gap $\ne\mathrm{Var}$; এটি $x^2$-এর বিশেষত্ব, কারণ $g''=2$ ধ্রুব।)

সমাধান ৮ (★★) [E4]¶

fair coin, $n=100$, $X_i\in[0,1]$ (তাই $b_i-a_i=1$), $\mathbb{E}[\bar X_n]=0.5$, $t=0.1$।

Hoeffding: $$ P(\lvert\bar X_n-0.5\rvert\ge 0.1)\le 2\exp(-2n t^2)=2\exp(-2\cdot100\cdot0.01)=2e^{-2}\approx \boxed{0.271}. $$

Chebyshev: এক coin-এর $\sigma^2=p(1-p)=0.25$, তাই $\mathrm{Var}(\bar X_n)=0.25/100=0.0025$: $$ P(\lvert\bar X_n-0.5\rvert\ge 0.1)\le \frac{\mathrm{Var}(\bar X_n)}{t^2}=\frac{0.0025}{0.01}=\boxed{0.25}. $$

তুলনা। এই ছোট $n$-এ Chebyshev ($0.25$) সামান্য আঁটসাঁট Hoeffding ($0.271$)-এর চেয়ে! কারণ Hoeffding-এর শক্তি asymptotic — $n$ বাড়লে তার exponential decay Chebyshev-এর $1/n$-কে বহুগুণ ছাপিয়ে যায় (যেমন $n=500$-তে Hoeffding $2e^{-10}\approx9\times10^{-5}$ বনাম Chebyshev $0.05$)। (প্রকৃত empirical মান এদের দুটোর চেয়েই অনেক ছোট, $\approx 0.035$ — দুটোই বৈধ কিন্তু রক্ষণশীল ছাদ।)

গ · প্রমাণভিত্তিক (proof-based)¶

সমাধান ৯ (★★) — Markov → Chebyshev¶

ধরি $Y=(X-\mu)^2$। $Y\ge0$ (বর্গ), তাই Markov প্রয়োগযোগ্য। লক্ষ করুন $$ \lvert X-\mu\rvert\ge k\sigma \iff (X-\mu)^2\ge k^2\sigma^2 \iff Y\ge k^2\sigma^2. $$ এখন $Y$-তে threshold $a=k^2\sigma^2$-এ Markov: $$ P(Y\ge k^2\sigma^2)\le \frac{\mathbb{E}[Y]}{k^2\sigma^2}. $$ কিন্তু $\mathbb{E}[Y]=\mathbb{E}[(X-\mu)^2]=\mathrm{Var}(X)=\sigma^2$ (সংজ্ঞা)। বসিয়ে: $$ P(\lvert X-\mu\rvert\ge k\sigma)=P(Y\ge k^2\sigma^2)\le \frac{\sigma^2}{k^2\sigma^2}=\frac{1}{k^2}. \qquad\blacksquare $$ এটাই Chebyshev — অর্থাৎ Chebyshev হলো "$(X-\mu)^2$-এ প্রয়োগ করা Markov"।

সমাধান ১০ (★★) — Jensen, supporting-line কৌশল¶

$g$ convex ও differentiable, $\mu=\mathbb{E}[X]$। Convex function-এর মূল ধর্ম: প্রতিটি বিন্দুতে tangent line পুরো curve-এর নিচে থাকে (supporting line)। $x=\mu$-তে tangent: $$ \ell(x)=g(\mu)+g'(\mu)(x-\mu),\qquad g(x)\ge \ell(x)\ \ \forall x. $$ এই অসমতা random variable $X$-এ প্রয়োগ করি: $g(X)\ge g(\mu)+g'(\mu)(X-\mu)$, যা একটি পয়েন্টওয়াইজ সম্পর্ক (প্রতিটি outcome-এ সত্য)। দুই পাশে expectation নিই (expectation monotone — 2.5): $$ \mathbb{E}[g(X)] \ge \mathbb{E}\big[g(\mu)+g'(\mu)(X-\mu)\big] = g(\mu)+g'(\mu)\underbrace{(\mathbb{E}[X]-\mu)}_{=0} = g(\mu)=g(\mathbb{E}[X]). $$ কারণ $g(\mu),\,g'(\mu)$ ধ্রুবক এবং $\mathbb{E}[X]-\mu=0$। তাই $g(\mathbb{E}[X])\le\mathbb{E}[g(X)]$। $\blacksquare$ (differentiability না থাকলেও subgradient দিয়ে একই যুক্তি খাটে; rigorous রূপ Part VII।)

সমাধান ১১ (★★★) — Hoeffding's lemma¶

দাবি: $X\in[a,b]$, $\mathbb{E}[X]=0$ হলে যেকোনো $s>0$-তে $\mathbb{E}[e^{sX}]\le e^{s^2(b-a)^2/8}$।

ধাপ ১ — convexity দিয়ে $e^{sx}$-কে রৈখিকভাবে উপরে ঢাকা। $x\mapsto e^{sx}$ convex, তাই $[a,b]$-এর যেকোনো $x$-এ ($x=\frac{b-x}{b-a}a+\frac{x-a}{b-a}b$ রূপে লিখে) chord-উপরে-থাকা ধর্মে: $$ e^{sx}\le \frac{b-x}{b-a}\,e^{sa}+\frac{x-a}{b-a}\,e^{sb}. $$ ধাপ ২ — expectation নিই ($\mathbb{E}[X]=0$ ব্যবহার করে): $$ \mathbb{E}[e^{sX}]\le \frac{b-\mathbb{E}[X]}{b-a}e^{sa}+\frac{\mathbb{E}[X]-a}{b-a}e^{sb}=\frac{b}{b-a}e^{sa}-\frac{a}{b-a}e^{sb}. $$ ডান পক্ষকে $e^{\psi(s)}$ আকারে লিখি, যেখানে (পরামিতি $p=\frac{-a}{b-a}\in[0,1]$, $u=s(b-a)$ নিয়ে গণনা করলে) $$ \psi(s)=\log\mathbb{E}[e^{sX}]\ \text{উপরে-আবদ্ধকারী রাশির log} = -pu+\log(1-p+pe^{u}). $$ ধাপ ৩ — Taylor + দ্বিতীয় derivative bound। সহজ ক্যালকুলাসে $\psi(0)=0$, $\psi'(0)=0$ (কারণ $\mathbb{E}[X]=0$), এবং $$ \psi''(u)=\frac{p(1-p)e^{u}}{(1-p+pe^{u})^2}\le \frac14 \quad(\text{যেহেতু }q(1-q)\le\tfrac14\ \forall q\in[0,1]). $$ তাই $u$-চলকে $\psi''\le \tfrac14$, আর $s$-চলকে chain-rule-এ $\dfrac{d^2}{ds^2}\le \dfrac{(b-a)^2}{4}$। Taylor (দ্বিতীয় ক্রম, কোনো $\xi$-তে): $$ \psi(s)=\psi(0)+s\psi'(0)+\frac{s^2}{2}\psi''(\xi)\le 0+0+\frac{s^2}{2}\cdot\frac{(b-a)^2}{4}=\frac{s^2(b-a)^2}{8}. $$ exponentiate করে $\mathbb{E}[e^{sX}]=e^{\psi(s)}\le e^{s^2(b-a)^2/8}$। $\blacksquare$

lemma → পূর্ণ Hoeffding। এই MGF-bound-কে Chernoff পদ্ধতি-তে ব্যবহার করা হয়: $S_n=\sum(X_i-\mathbb{E}X_i)$-এর জন্য $P(S_n\ge \tau)\le e^{-s\tau}\mathbb{E}[e^{sS_n}]=e^{-s\tau}\prod_i\mathbb{E}[e^{s(X_i-\mathbb{E}X_i)}]$ (Markov-on-$e^{sS_n}$ + independence), তারপর প্রতিটি পদে lemma বসিয়ে ও $s$-এর ওপর minimize করে $\exp\!\big(-2\tau^2/\sum(b_i-a_i)^2\big)$ পাওয়া যায়; $\bar X_n$-রূপে রূপান্তর ও দুই-পার্শ্বের জন্য $\times2$ দিলে $2\exp(-2n^2t^2/\sum(b_i-a_i)^2)$।

ঘ · কোডিং (coding)¶

সমাধান ১২ (★)¶

import numpy as np
rng = np.random.default_rng(0)
samples = rng.exponential(scale=1.0, size=1_000_000)   # Exp(rate=1), E[X]=1
EX = 1.0
print(f"{'a':>3} {'empirical P(X>=a)':>18} {'Markov 1/a':>12} {'bound OK?':>10}")
for a in [2, 3, 4, 5]:
    emp = np.mean(samples >= a)
    bound = EX / a
    print(f"{a:>3} {emp:>18.4f} {bound:>12.4f} {str(emp <= bound):>10}")

প্রকৃত আউটপুট (চালিয়ে যাচাই করা):

  a  empirical P(X>=a)   Markov 1/a  bound OK?
  2             0.1353       0.5000       True
  3             0.0500       0.3333       True
  4             0.0184       0.2500       True
  5             0.0068       0.2000       True

প্রতিটি ক্ষেত্রে empirical tail $\le$ Markov bound — bound সবসময় বড় (এবং বেশ ঢিলা, কারণ Exponential-এর সত্য tail $e^{-a}$ exponentially নামে, Markov-এর $1/a$ ধীরে)।

সমাধান ১৩ (★★)¶

import numpy as np

def chebyshev_check(sample, k):
    mu, s = sample.mean(), sample.std()
    emp = np.mean(np.abs(sample - mu) >= k * s)   # empirical tail
    bound = 1.0 / k**2                             # Chebyshev bound
    return emp, bound, emp <= bound

rng = np.random.default_rng(7)
N = 2_000_000
dists = {
    "Normal":      rng.normal(0, 1, N),
    "Uniform":     rng.uniform(-1, 1, N),
    "Exponential": rng.exponential(1.0, N),
}
print(f"{'dist':>12} {'k':>4} {'empirical':>10} {'1/k^2':>8} {'OK?':>6}")
for name, s in dists.items():
    for k in [1.5, 2.0, 3.0]:
        emp, bound, ok = chebyshev_check(s, k)
        print(f"{name:>12} {k:>4} {emp:>10.4f} {bound:>8.4f} {str(ok):>6}")

প্রকৃত আউটপুট (মান সামান্য দোলে, সব OK? True):

        dist    k  empirical    1/k^2    OK?
      Normal  1.5     0.1336   0.4444   True
      Normal  2.0     0.0455   0.2500   True
      Normal  3.0     0.0027   0.1111   True
     Uniform  1.5     0.1340   0.4444   True
     Uniform  2.0     0.0000   0.2500   True
     Uniform  3.0     0.0000   0.1111   True
 Exponential  1.5     0.0608   0.4444   True
 Exponential  2.0     0.0498   0.2500   True
 Exponential  3.0     0.0183   0.1111   True

তিনটি ভিন্ন distribution ও তিনটি $k$ — কোথাও empirical tail Chebyshev bound $1/k^2$ ছাড়ায়নি। Uniform-এ $k\ge2$-তে empirical $0$, কারণ Uniform$(-1,1)$-এর সর্বোচ্চ deviation $\approx 1.73\sigma$ (bounded support), তাই $2\sigma$ ছাড়িয়ে কোনো mass-ই নেই — Chebyshev এখানে চরম রক্ষণশীল।

সমাধান ১৪ (★★★) [E4]¶

import numpy as np
import matplotlib; matplotlib.use("Agg")
import matplotlib.pyplot as plt

rng = np.random.default_rng(2025)
TRIALS = 300_000
t = 0.05
ns = [10, 50, 100, 500, 1000]
emp, hoef = [], []
for n in ns:
    draws = rng.binomial(1, 0.5, size=(TRIALS, n))
    dev = np.abs(draws.mean(axis=1) - 0.5)
    emp.append(max(np.mean(dev >= t), 1.0 / TRIALS))   # log-floor
    hoef.append(2 * np.exp(-2 * n * t**2))

print(f"{'n':>5} {'empirical':>12} {'Hoeffding':>12} {'bound OK?':>10}")
for n, e, h in zip(ns, emp, hoef):
    print(f"{n:>5} {e:>12.5f} {h:>12.5f} {str(e <= h):>10}")

fig, ax = plt.subplots(figsize=(8, 4.6))
ax.plot(ns, emp, "o-", color="#2f6db5", lw=2, label="empirical P(|Xbar-0.5| >= 0.05)")
ax.plot(ns, hoef, "s--", color="#c0392b", lw=2, label="Hoeffding 2 exp(-2 n t^2)")
ax.set_yscale("log"); ax.set_xlabel("n"); ax.set_ylabel("probability (log)")
ax.set_title("Empirical tail vs Hoeffding bound (fair coin, t=0.05)")
ax.legend(fontsize=9); fig.tight_layout()
# fig.savefig("/tmp/q14_hoeffding.png", dpi=150)   # ঐচ্ছিক

প্রকৃত আউটপুট (মান সামান্য দোলে):

    n    empirical    Hoeffding  bound OK?
   10      0.75143      1.90100       True
   50      0.32395      1.60653       True
  100      0.16319      1.36717       True
  500      0.02692      0.59443       True
 1000      0.00307      0.27067       True

দুটোই $n$ বাড়লে নামে; log y-axis-এ প্রায় সরলরেখা মানে exponential decay। Hoeffding bound সবসময় empirical-এর উপরে (bound বৈধ), তবে ছোট $n$-এ bound $>1$ (অর্থহীন, কারণ probability $\le1$) — Hoeffding বড় $n$ ও মাঝারি $t$-তে সবচেয়ে কার্যকর। ($t=0.05$ ছোট হওয়ায় bound বড় $n$ পর্যন্ত $1$-এর নিচে নামতে দেরি করে; $t=0.1$-এ অনেক আগে নামত।)

শিক্ষণীয় সারাংশ। তিনটি ধারা মনে রাখুন: (১) Markov = nonnegative + mean → ঢিলা সর্বজনীন ছাদ; (২) Chebyshev = Markov-on-$(X-\mu)^2$ → mean+variance থেকে $1/k^2$; (৩) Hoeffding = Hoeffding's-lemma + Chernoff → bounded+independent থেকে exponential ছাদ। আর Jensen convexity/concavity-র দিক ঠিক করে দেয় ($\mathbb{E}[X^2]\ge(\mathbb{E}X)^2$ তার সরলতম ফল)। পরের অধ্যায়ে Chebyshev সরাসরি Weak Law of Large Numbers প্রমাণ করব