Variance আর concentration — Markov, Chebyshev আর Chernoff

১ · গড় যথেষ্ট নয় — variance আর standard deviation

কাল্পনিক অনলাইন দোকান বাজারঘর দুটি কুরিয়ার কোম্পানির মধ্যে একটি বাছবে। দুটিরই গড় দেরি ২ ঘণ্টা। প্রথমটি প্রতিদিন প্রায় ২ ঘণ্টাই দেরি করে, কখনো ১, কখনো ৩. দ্বিতীয়টি বেশিরভাগ দিন সময়মতো পৌঁছায়, কিন্তু মাঝে মাঝে ১০ ঘণ্টা দেরি করে। গড় এক হলেও গ্রাহকের অভিজ্ঞতা একেবারে আলাদা। পর্ব ৪০ “Random variable আর প্রত্যাশা — linearity-র জাদু”-এ আমরা গড় বা প্রত্যাশা E[X] শিখেছি; এই পর্বের প্রশ্ন হলো, মান গড়ের চারপাশে কতটা ছড়িয়ে থাকে, আর গড় থেকে অনেক দূরে যাওয়ার সম্ভাবনা কত।

বর্গ কেন? গড় থেকে বিচ্যুতি X − μ-এর গড় সবসময় 0 (linearity: E[X] − μ = 0), তাই যোগ আর বিয়োগ কাটাকাটি হয়ে যায়। বর্গ করলে সব বিচ্যুতি ধনাত্মক হয়, আর বড় বিচ্যুতি বেশি ওজন পায়। σ-এর একক X-এর এককের সমান (ঘণ্টা, টাকা, রান), তাই কথায় σ-ই বেশি ব্যবহার হয়; কিন্তু হিসাবে Var সহজ, কারণ এর বীজগণিত সুন্দর।

প্রমাণ: μ = E[X] লিখুন।

1. প্রতিটি ফলাফলে (X − μ)² = X² − 2μX + μ². — বীজগণিত
2. প্রত্যাশা নিলে E[(X − μ)²] = E[X²] − 2μE[X] + μ², কারণ প্রত্যাশা রৈখিক আর μ একটি ধ্রুবক। — linearity, পর্ব ৪০
3. E[X] = μ বসালে E[X²] − 2μ² + μ² = E[X²] − μ². — সরল করা
4. দ্বিতীয় দাবির জন্য: E[aX + b] = aμ + b, তাই (aX + b) − (aμ + b) = a(X − μ), আর তার বর্গের প্রত্যাশা a² E[(X − μ)²] = a² Var(X). ∎ — linearity

ফলটির মানে সহজ: সব মান একটি ধ্রুবক b দিয়ে সরালে ছড়ানো বদলায় না, আর একক বদলালে (মিনিট থেকে ঘণ্টা, a = 1/60) variance বদলায় a² গুণে। একটি সাবধানতা: E[X²] আর (E[X])² এক জিনিস নয়, আর তাদের পার্থক্যটিই variance. দুটি সমান হয় শুধু তখন, যখন X কার্যত একটি ধ্রুবক। নিচের stepper একটি ছক্কার variance দুই পথে বের করে।

1X ∈ {1, …, 6}, প্রতিটি 1/62E[X] = 21/6 = 7/23(x − 7/2)²: 6.25 2.25 0.25 …4Var = 17.5/6 = 35/12591/6 − 49/4 = 35/126σ = √(35/12) ≈ 1.708

২ · যোগফলের variance — pairwise independence-ই যথেষ্ট

প্রত্যাশার যোগ সবসময় চলে: E[X + Y] = E[X] + E[Y], স্বাধীনতা লাগে না। Variance-এর ক্ষেত্রে তা সত্য নয়। একটি ছক্কার মান X হলে X + X = 2X, আর উপপাদ্য ১.২ অনুযায়ী Var(2X) = 4 Var(X), 2 Var(X) নয়। দুই চলক একসঙ্গে ওঠানামা করলে ছড়ানো বাড়ে। এই একসঙ্গে ওঠানামা মাপে covariance:

Cov(X, Y) = E[(X − μ_X)(Y − μ_Y)] = E[XY] − E[X]E[Y]

উপপাদ্য ১.২-এর মতো বিস্তার করলেই পাওয়া যায় Var(X + Y) = Var(X) + Var(Y) + 2 Cov(X, Y). X আর Y স্বাধীন হলে E[XY] = E[X]E[Y] (পর্ব ৪০-এ প্রমাণিত), তাই Cov = 0. মজার কথা হলো, অনেক চলকের যোগফলে শুধু জোড়ায় জোড়ায় স্বাধীনতা লাগে।

প্রমাণ: μᵢ = E[Xᵢ], Dᵢ = Xᵢ − μᵢ, আর S = X₁ + … + Xₙ লিখুন।

1. Linearity-তে E[S] = μ₁ + … + μₙ, তাই S − E[S] = D₁ + … + Dₙ. — পর্ব ৪০
2. (D₁ + … + Dₙ)² = ∑ᵢ Dᵢ² + ∑_i≠j DᵢDⱼ; এখানে দ্বিতীয় যোগে প্রতিটি ক্রমসহ জোড়া (i, j) একবার। — বীজগণিত
3. প্রত্যাশা নিলে Var(S) = ∑ᵢ E[Dᵢ²] + ∑_i≠j E[DᵢDⱼ] = ∑ᵢ Var(Xᵢ) + ∑_i≠j Cov(Xᵢ, Xⱼ). — linearity, সংজ্ঞা
4. প্রতিটি cross term-এ শুধু দুটি চলক থাকে। Xᵢ আর Xⱼ স্বাধীন, তাই Cov(Xᵢ, Xⱼ) = E[XᵢXⱼ] − μᵢμⱼ = 0. — জোড়ার স্বাধীনতা
5. সব cross term 0, তাই Var(S) = ∑ Var(Xᵢ). ∎

ধাপ ৪-ই মূল কথা: প্রমাণে কখনো তিনটি চলক একসঙ্গে আসে না, তাই তিনটির যৌথ স্বাধীনতা (mutual independence) লাগে না। পর্ব ৩৯ “শর্তসাপেক্ষ সম্ভাবনা, independence আর Bayes-এর উপপাদ্য”-এর বিখ্যাত উদাহরণটি নিন: X, Y দুটি নিরপেক্ষ bit, আর Z = X ⊕ Y (XOR). তিনটি জোড়ায় জোড়ায় স্বাধীন, কিন্তু X আর Y জানলে Z পুরো জানা, তাই যৌথভাবে স্বাধীন নয়। তবু উপপাদ্য বলে Var(X + Y + Z) = 1/4 + 1/4 + 1/4 = 3/4. শুধু জোড়ার স্বাধীনতাই যথেষ্ট, এই তথ্যটি কম্পিউটার বিজ্ঞানে খুব কাজের: এলোমেলো bit কম খরচে বানানো যায়, কারণ পুরো স্বাধীনতার বদলে জোড়ার স্বাধীনতা পেতে অনেক কম এলোমেলো bit লাগে।

Binomial-এর variance: np(1 − p)

বাজারঘরের একটি চালানে n = 400টি পণ্য, প্রতিটি অন্যগুলো থেকে স্বাধীনভাবে p = 0.05 সম্ভাবনায় ত্রুটিপূর্ণ। ত্রুটিপূর্ণ পণ্যের সংখ্যা X-কে indicator-এর যোগ হিসেবে লিখুন: X = I₁ + … + Iₙ, যেখানে পণ্য i ত্রুটিপূর্ণ হলে Iᵢ = 1, না হলে 0 (পর্ব ৪০-এর কৌশল)। Iᵢ শুধু 0 বা 1, তাই Iᵢ² = Iᵢ, আর

Var(Iᵢ) = E[Iᵢ²] − (E[Iᵢ])² = p − p² = p(1 − p)

Iᵢ-গুলো স্বাধীন, তাই উপপাদ্য ২.১ অনুযায়ী Var(X) = np(1 − p). চালানে গড় ত্রুটি np = 20, variance 400 × 0.05 × 0.95 = 19, আর σ = √19 ≈ 4.36. এই প্রমাণে C(n, k)-এর কোনো যোগফল লাগল না (পর্ব ৩৪-এর identity দিয়েও একই উত্তর আসে, কিন্তু অনেক লম্বা পথে)। p = 1/2-এ p(1 − p) = 1/4, যা এর সর্বোচ্চ মান; কারণ p(1 − p) = 1/4 − (p − 1/2)². তাই যেকোনো p-তে np(1 − p) ≤ n/4, এই সীমাটি §৫-এ কাজে লাগবে।

এবার Python-এ সব দাবি exact ভগ্নাংশে মিলিয়ে নিন: ছক্কার variance দুই সূত্রে, দুটি স্বাধীন ছক্কার যোগ আর বিয়োগ, X + X, আর XOR উদাহরণ। শেষে একটি seeded simulation. প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from fractions import Fraction as F
from itertools import product
import random

def E(space, f):                  # space: list of equally likely outcomes
    return sum(F(f(w)) for w in space) / len(space)

def Var(space, f):
    m = E(space, f)
    return E(space, lambda w: (f(w) - m) ** 2)

die = list(range(1, 7))
print("E[X] =", E(die, lambda x: x), " E[X^2] =", E(die, lambda x: x * x))
print("Var by definition:", Var(die, lambda x: x),
      " by E[X^2]-E[X]^2:", E(die, lambda x: x * x) - E(die, lambda x: x) ** 2)

two = list(product(die, die))     # 36 outcomes of two independent dice
print("Var(X+Y) =", Var(two, lambda w: w[0] + w[1]),
      " Var(X-Y) =", Var(two, lambda w: w[0] - w[1]),
      " Var(X+X) =", Var(die, lambda x: 2 * x))

bits = list(product((0, 1), repeat=2))   # Z = X xor Y: pairwise independent
S = lambda w: w[0] + w[1] + (w[0] ^ w[1])
print("Var(X+Y+Z) =", Var(bits, S), " sum of variances =", 3 * F(1, 4))
P_all = F(sum(1 for w in bits if w[0] and w[1] and (w[0] ^ w[1])), 4)
print("P(X=Y=Z=1) =", P_all, "but P(X=1)P(Y=1)P(Z=1) = 1/8")

random.seed(41)                   # sample variance of 100000 rolls
rolls = [random.randint(1, 6) for _ in range(100_000)]
m = sum(rolls) / len(rolls)
v = sum((r - m) ** 2 for r in rolls) / len(rolls)
print(f"simulated mean {m:.4f}, variance {v:.4f};  exact 3.5000, {35/12:.4f}")

E[X] = 7/2  E[X^2] = 91/6
Var by definition: 35/12  by E[X^2]-E[X]^2: 35/12
Var(X+Y) = 35/6  Var(X-Y) = 35/6  Var(X+X) = 35/3
Var(X+Y+Z) = 3/4  sum of variances = 3/4
P(X=Y=Z=1) = 0 but P(X=1)P(Y=1)P(Z=1) = 1/8
simulated mean 3.4966, variance 2.9222;  exact 3.5000, 2.9167

৩ · Markov-এর অসমতা — শুধু গড় জেনে লেজের সীমা

বাজারঘরের ম্যানেজার জানেন শুধু একটি সংখ্যা: ডেলিভারির গড় দেরি ২ ঘণ্টা। দেরি কখনো ঋণাত্মক নয়। এটুকু জেনেই কি বলা যায়, ১০ ঘণ্টা বা তার বেশি দেরির সম্ভাবনা সর্বোচ্চ কত? হ্যাঁ: ২০%-এর বেশি নয়। কারণটি সহজ। যদি ২০%-এর বেশি অর্ডারে দেরি ≥ ১০ ঘণ্টা হতো, শুধু ওই অর্ডারগুলোই গড়ে 0.2 × 10 = 2 ঘণ্টার বেশি যোগ করত, আর বাকি অর্ডারের দেরি ঋণাত্মক হতে পারে না; তাহলে গড় ২-এর বেশি হতো। কোনো মানের অনেক বড় হওয়ার সম্ভাবনাকে বলে লেজের সম্ভাবনা (tail probability), আর এমন সীমা দেওয়া প্রথম হাতিয়ারটির নাম Markov-এর অসমতা.

প্রমাণ: I দিয়ে ঘটনা {X ≥ a}-এর indicator বোঝান: X ≥ a হলে I = 1, নইলে I = 0.

1. দাবি: প্রতিটি ফলাফলে a · I ≤ X. যদি X ≥ a, তাহলে বাঁ দিক a ≤ X. নইলে বাঁ দিক 0, আর 0 ≤ X, কারণ X অঋণাত্মক। — দুই ক্ষেত্র
2. প্রতিটি ফলাফলে যে অসমতা খাটে, তা প্রত্যাশাতেও খাটে (প্রত্যাশা অঋণাত্মক ওজনের যোগ), তাই a · E[I] ≤ E[X]. — প্রত্যাশার monotonicity
3. E[I] = P(X ≥ a) (পর্ব ৪০), তাই a · P(X ≥ a) ≤ E[X]; a > 0 দিয়ে ভাগ করলে দাবি। ∎ — indicator-এর প্রত্যাশা

খেয়াল করুন, ধাপ ১-এ X ≥ 0 শর্তটি ঠিক একবার লেগেছে। শর্তটি বাদ দিলে দাবি ভাঙে, §৯-এ একটি ভুল প্রমাণে তা দেখবেন। আরেকটি রূপ: t ≥ 1 হলে P(X ≥ t · E[X]) ≤ 1/t, অর্থাৎ অঋণাত্মক চলক গড়ের তিনগুণ ছাড়ানোর সম্ভাবনা সর্বোচ্চ ১/৩.

সীমাটি কি আরও ভালো করা যায়?

শুধু গড় জানা থাকলে না। X = 0 সম্ভাবনা 0.8-এ আর X = 10 সম্ভাবনা 0.2-এ নিন। তাহলে E[X] = 2 আর P(X ≥ 10) = 0.2 = 2/10, ঠিক Markov-এর সীমা। অর্থাৎ যে বিতরণে সমস্ত “ভর” হয় 0-তে, নয়তো ঠিক a-তে, সেখানে সমতা হয়। দ্বিতীয় কুরিয়ার কোম্পানিটি অনেকটা এমন। কিন্তু প্রথম কোম্পানির দেরি যদি সবসময় ১ থেকে ৩ ঘণ্টার মধ্যে থাকে, আসল সম্ভাবনা 0, আর Markov-এর 0.2 অনেক দুর্বল। আরও ভালো সীমা চাইলে আরও তথ্য লাগবে, যেমন variance.

Algorithm বিশ্লেষণে Markov একটি গুরুত্বপূর্ণ সেতু। একটি Las Vegas algorithm-এর (যা সবসময় ঠিক উত্তর দেয়, কিন্তু চলার সময় এলোমেলো) গড় সময় T হলে, 3T ধাপ পরে থামিয়ে দিলে ব্যর্থ হওয়ার সম্ভাবনা ≤ 1/3. এভাবে একটি “গড়ে দ্রুত” algorithm থেকে একটি “নির্দিষ্ট সময়ে শেষ হয়, কখনো কখনো ভুল” algorithm, অর্থাৎ Monte Carlo algorithm পাওয়া যায়। DSA কোর্সের পর্ব ৬১-এ এই দুই ধরনের algorithm কোডসহ আছে; এর গাণিতিক কাঠামো পর্ব ৪৩ “Probabilistic method আর randomized algorithm”-এ আসবে।

৪ · Chebyshev-এর অসমতা — variance দিয়ে আরও শক্ত সীমা

Markov-এর একটি সুন্দর কৌশল আছে: এটি যেকোনো অঋণাত্মক চলকে খাটে, তাই X-এর কোনো ফাংশনে বসিয়ে নতুন অসমতা পাওয়া যায়। (X − μ)² সবসময় অঋণাত্মক, আর তার প্রত্যাশা ঠিক variance. এই এক লাইনের ভাবনা থেকেই আসে Chebyshev-এর অসমতা.

প্রমাণ:

1. Y = (X − μ)² লিখুন। প্রতিটি ফলাফলে Y ≥ 0. — বর্গ অঋণাত্মক
2. t > 0 হলে |X − μ| ≥ t ঠিক তখনই, যখন (X − μ)² ≥ t², অর্থাৎ দুটি ঘটনা একই সেট। — উভয় পক্ষ অঋণাত্মক, বর্গ একমুখী
3. Y আর a = t²-এ Markov বসান: P(Y ≥ t²) ≤ E[Y]/t². — উপপাদ্য ৩.১
4. E[Y] = Var(X) = σ², তাই P(|X − μ| ≥ t) ≤ σ²/t². t = kσ বসালে দ্বিতীয় রূপ। ∎ — সংজ্ঞা ১.১

কোনো বিতরণ সম্পর্কে শুধু μ আর σ জানলেই বলা যায়: যেকোনো বিতরণে গড় থেকে 2σ বা বেশি দূরে থাকার সম্ভাবনা ≤ 1/4, 3σ বা বেশি দূরে ≤ 1/9. শুধু গড় জানলে Markov এক দিকের লেজ বাঁধে; variance জানলে Chebyshev দুই দিকের লেজই বাঁধে, আর দূরত্বের সঙ্গে সীমাটি 1/t² হারে কমে, Markov-এর 1/a-এর চেয়ে দ্রুত।

এই সীমাও আর ভালো করা যায় না, যদি শুধু μ আর σ জানা থাকে। k ≥ 1-এ X = −k, 0, +k নিন, সম্ভাবনা যথাক্রমে 1/(2k²), 1 − 1/k², 1/(2k²). তাহলে μ = 0, Var = k² · 1/k² = 1, আর P(|X| ≥ k) = 1/k², ঠিক সমান। তবে বেশিরভাগ বাস্তব বিতরণে, বিশেষ করে অনেক স্বাধীন চলকের যোগে, আসল লেজ Chebyshev-এর চেয়ে অনেক ছোট; ছবিতে আর stepper-এ সেটিই দেখুন।

1X = মাথা, n = 100, p = 1/22μ = np = 503σ² = np(1 − p) = 25, σ = 54P(|X − 50| ≥ 10) ≤ 25/1005P(41 ≤ X ≤ 59) ≥ 0.756আসল: 0.0569 আর 0.9431

৫ · বড় সংখ্যার দুর্বল নিয়ম — গড় কেন স্থির হয়

বাজারঘর জানতে চায় তার গুদামের একটি লাইনে ত্রুটির হার p কত। পুরো লাইন পরীক্ষা করা অসম্ভব, তাই এলোমেলোভাবে n-টি পণ্য পরীক্ষা করে ত্রুটিপূর্ণগুলোর অনুপাত নেওয়া হয়। এই অনুপাত কি p-এর কাছে থাকবে? থাকলে কত কাছে, আর কত নমুনায়? এর উত্তর দেয় বড় সংখ্যার নিয়ম (law of large numbers). এখানে আমরা এর দুর্বল রূপটি সম্পূর্ণ প্রমাণ করব, আর প্রমাণে Chebyshev ছাড়া কিছুই লাগবে না।

প্রমাণ:

1. Linearity-তে E[X̄] = (μ + … + μ)/n = μ. — পর্ব ৪০
2. চলকগুলো pairwise independent, তাই Var(X₁ + … + Xₙ) = nσ². — উপপাদ্য ২.১
3. Var(X̄) = Var((1/n)(X₁ + … + Xₙ)) = (1/n²) · nσ² = σ²/n. — উপপাদ্য ১.২, a = 1/n
4. X̄-এ Chebyshev বসালে P(|X̄ − μ| ≥ ε) ≤ (σ²/n)/ε². — উপপাদ্য ৪.১
5. ε আর σ স্থির রেখে n বাড়ালে σ²/(nε²) যেকোনো ধনাত্মক সংখ্যার চেয়ে ছোট হয়, তাই সম্ভাবনাটি 0-তে যায়। ∎

মূল কথা ধাপ ৩-এ: গড়ের variance σ²/n, তাই তার standard deviation σ/√n. নমুনা চারগুণ করলে গড়ের অনিশ্চয়তা অর্ধেক হয়, দশগুণ নয়। এই “√n-এর নিয়ম” পরিসংখ্যানের প্রায় প্রতিটি হিসাবে ফিরে আসে। পর্ব ৩৮ “বিচ্ছিন্ন সম্ভাবনা — sample space, event আর Laplace-এর সংজ্ঞা”-এ সম্ভাবনা আর আপেক্ষিক কম্পাঙ্কের যে সম্পর্কের কথা বলা হয়েছিল, এটি তার গাণিতিক রূপ: indicator-এর গড় মানে ঘটনাটি কত ভাগ সময় ঘটল, আর তা p-এর কাছে জমে। একটি শক্তিশালী রূপ (strong law) আছে, যা বলে প্রায় নিশ্চিতভাবে গড় μ-তে পৌঁছায়; তার প্রমাণ অসীম sample space-এর পরিমাপ-তত্ত্ব চায়, তাই এই কোর্সে শুধু নাম।

কত নমুনা লাগবে? ত্রুটির হার মাপা

প্রশ্ন: ত্রুটির হার p-কে ±0.05-এর মধ্যে মাপতে হবে, আর ভুল হওয়ার সম্ভাবনা যেন ≤ 0.05 হয়। Xᵢ = পণ্য i ত্রুটিপূর্ণ কি না (indicator), তাই σ² = p(1 − p) ≤ 1/4, আর p অজানা হলেও এই সীমা খাটে (§২)। Chebyshev থেকে:

P(|X̄ − p| ≥ 0.05) ≤ 1/(4n × 0.05²) ≤ 0.05 ⇔ n ≥ 2000

অর্থাৎ ২০০০টি পণ্য পরীক্ষা যথেষ্ট, লাইনে মোট পণ্য যতই হোক। §৬-এর Chernoff-ধাঁচের Hoeffding অসমতা দিয়ে একই নিশ্চয়তা আসে মাত্র ৭৩৮টি নমুনায়; দুই উত্তরই সঠিক, শুধু দ্বিতীয় সীমাটি বেশি শক্ত। দুটি শর্ত ভুলবেন না: নমুনা সত্যিই এলোমেলো আর স্বাধীন হতে হবে, আর পক্ষপাতদুষ্ট নমুনা (যেমন শুধু সকালের শিফটের পণ্য) বেশি সংখ্যায় নিলেও ঠিক হয় না; তখন গড় ভুল মানের দিকেই জমে।

নিচের ব্লক দুটি কাজ করে। প্রথমে p = 0.05 ধরে ১ লাখ পণ্যের একটি seeded সারিতে চলমান গড় ছাপে। তারপর ৪০০ পণ্যের ১০০০টি চালান simulate করে দেখে কত ভাগ চালানে ত্রুটির সংখ্যা গড় 20 থেকে 10 বা বেশি দূরে, আর তাকে exact মান ও Chebyshev-এর সীমার সঙ্গে মেলায়।

import random
from math import comb

p = 0.05                          # true defect rate of a batch line
random.seed(2026)
defects = 0
print("     n  defects  average  |avg - p|")
for i in range(1, 100_001):
    defects += random.random() < p
    if i in (10, 100, 1_000, 10_000, 100_000):
        avg = defects / i
        print(f"{i:6d}  {defects:7d}  {avg:.5f}  {abs(avg - p):.5f}")

# 1000 batches of n = 400: how often is |X - 20| >= 10 ?
n, runs = 400, 1000
random.seed(41)
far = 0
for _ in range(runs):
    X = sum(random.random() < p for _ in range(n))
    far += abs(X - 20) >= 10
exact = sum(comb(n, k) * p**k * (1 - p)**(n - k)
            for k in range(n + 1) if abs(k - 20) >= 10)
cheb = n * p * (1 - p) / 10**2
print(f"simulated {far / runs:.4f}  exact {exact:.4f}  Chebyshev bound {cheb:.4f}")

     n  defects  average  |avg - p|
    10        0  0.00000  0.05000
   100        4  0.04000  0.01000
  1000       50  0.05000  0.00000
 10000      496  0.04960  0.00040
100000     4994  0.04994  0.00006
simulated 0.0260  exact 0.0284  Chebyshev bound 0.1900

ভুল ধরুন: “গড় ফিরে আসবে, তাই এবার tail”

একজন বললেন: “একটি নিরপেক্ষ মুদ্রায় পরপর ৫বার head এসেছে। বড় সংখ্যার নিয়ম বলে head-এর অনুপাত 1/2-এ ফিরবে, তাই পরের টসে tail-এর সম্ভাবনা 1/2-এর বেশি।” এই চিন্তার নাম gambler's fallacy. টসগুলো স্বাধীন, তাই পরের টসে tail-এর সম্ভাবনা ঠিক 1/2, আগের ফল যা-ই হোক। নিয়মটি “ক্ষতিপূরণ” দিয়ে কাজ করে না, কাজ করে “পাতলা করে”: ৫টি বাড়তি head পরের n টসের পরেও গড়ে বাড়তিই থাকে, কিন্তু অনুপাতে তার প্রভাব 5/(n + 5), যা n বাড়লে 0-তে যায়। উপপাদ্য ৫.১ অনুপাতের কথা বলে, গণনার পার্থক্যের কথা নয়; আসলে head আর tail-এর সংখ্যার পার্থক্যের standard deviation √n হারে বাড়ে।

৬ · Chernoff bound — সূচকীয় হারে ছোট লেজ

Chebyshev শুধু variance ব্যবহার করে, তাই তার সীমা 1/t² হারে কমে। কিন্তু অনেকগুলো স্বাধীন 0/1 চলকের যোগে আমরা আরও অনেক কিছু জানি, আর তখন লেজ সূচকীয় (exponential) হারে ছোট হয়। এমন সব সীমাকে একসঙ্গে বলে concentration inequality: চলকটি তার গড়ের চারপাশে “ঘন হয়ে জমে” থাকে। সবচেয়ে পরিচিতটির নাম Chernoff bound. এর মূল কৌশল আবার Markov, এবার e^tX-এ বসিয়ে। E[e^tX]-কে বলে X-এর moment generating function.

প্রমাণ (ওপরের লেজ, সম্পূর্ণ): a = (1 + δ)μ আর যেকোনো t > 0 নিন।

1. e^tx ক্রমবর্ধমান, তাই X ≥ a ঠিক তখনই, যখন e^tX ≥ e^ta. — একমুখী ফাংশন
2. e^tX > 0, তাই Markov-এ P(X ≥ a) ≤ E[e^tX] / e^ta. — উপপাদ্য ৩.১
3. e^tX = e^tX₁ · … · e^tXₙ, আর স্বাধীন চলকের গুণফলের প্রত্যাশা প্রত্যাশার গুণফল, তাই E[e^tX] = ∏ E[e^tXᵢ]. — যৌথ স্বাধীনতা, পর্ব ৪০
4. E[e^tXᵢ] = (1 − pᵢ) · 1 + pᵢ e^t = 1 + pᵢ(e^t − 1) ≤ exp(pᵢ(e^t − 1)), কারণ সব বাস্তব x-এ 1 + x ≤ e^x. — e^x-এর উত্তলতা
5. গুণ করলে E[e^tX] ≤ exp(μ(e^t − 1)), তাই P(X ≥ a) ≤ exp(μ(e^t − 1) − t(1 + δ)μ). — সূচকের যোগ
6. t = ln(1 + δ) > 0 বাছুন: e^t − 1 = δ, আর ডান দিক e^δμ / (1 + δ)^(1+δ)μ, অর্থাৎ দাবিকৃত রূপ। ∎ — t বাছাই

সরল রূপ e^−δ²μ/3: প্রথম রূপের log হলো μ(δ − (1 + δ)ln(1 + δ)), তাই দেখাতে হবে যে 0 ≤ δ ≤ 1-এ f(δ) = (1 + δ)ln(1 + δ) − δ − δ²/3 ≥ 0. f(0) = 0, f′(δ) = ln(1 + δ) − 2δ/3, f′(0) = 0, আর f″(δ) = 1/(1 + δ) − 2/3, যা δ < 1/2-এ ধনাত্মক আর পরে ঋণাত্মক। তাই f′ প্রথমে বাড়ে, পরে কমে; আর f′(1) = ln 2 − 2/3 ≈ 0.026 > 0, তাই পুরো [0, 1]-এ f′ ≥ 0, ফলে f ≥ 0. ∎ (Calculus-এর এই একটি ধাপ বাদে প্রমাণটি পুরো বিচ্ছিন্ন।)

আরেকটি রূপ প্রায়ই সবচেয়ে সুবিধাজনক, যা Hoeffding-এর অসমতা নামে পরিচিত। এর প্রমাণ একই কাঠামোর (Markov-এ e^tX), কিন্তু একটি আলাদা লেমা চায় (Hoeffding's lemma); এখানে শুধু বিবৃতি দিচ্ছি, প্রমাণ বাদ।

§৫-এর নমুনার প্রশ্নে এটি বসান: 2e^{−2n(0.05)²} ≤ 0.05 হতে হলে n ≥ ln(40)/(2 × 0.0025) ≈ 737.8, তাই ৭৩৮টি নমুনা যথেষ্ট, যেখানে Chebyshev চেয়েছিল ২০০০. আর লক্ষ্য আরও কঠোর হলে পার্থক্য বিশাল: ভুলের সম্ভাবনা 0.05 থেকে 0.0001-এ নামালে Chebyshev-এর n ৫০০ গুণ বাড়ে, কিন্তু Hoeffding-এর n বাড়ে শুধু log(1/ভুলের সম্ভাবনা) হারে, তিনগুণেরও কম। মেশিন লার্নিংয়ে “কত ডেটায় শেখা নির্ভরযোগ্য” প্রশ্নে এই log-হারই মূল চাবি; Machine Learning কোর্সের পর্ব ৩-এ PAC learning-এর হিসাবে Hoeffding এভাবেই আসে।

৭ · কোন bound কত শক্ত — exact লেজের সঙ্গে তুলনা

চারটি সীমা হাতে আছে। একই প্রশ্নে সবগুলো বসিয়ে exact উত্তরের সঙ্গে মেলালে বোঝা যায় কোনটি কী দেয়। প্রশ্ন: ১০০টি নিরপেক্ষ টসে মাথা অন্তত a, অর্থাৎ P(X ≥ a). Exact উত্তর C(100, k)-এর যোগফল দিয়ে, ভগ্নাংশে, কোনো আসন্ন মান ছাড়াই।

from fractions import Fraction as F
from math import comb, exp

n, p = 100, F(1, 2)               # X = number of heads in 100 fair flips
mu, var = n * p, n * p * (1 - p)  # 50 and 25

def exact_tail(a):                # P(X >= a), exact
    return sum(comb(n, k) for k in range(a, n + 1)) * p**n

print("   a     exact   Markov  Chebyshev  Chernoff  Hoeffding")
for a in (55, 60, 70, 80):
    d = (a - mu) / mu             # a = (1 + d) mu
    markov = mu / a
    cheb = min(1, var / (a - mu) ** 2)
    chern = (exp(d) / (1 + d) ** (1 + d)) ** mu
    hoeff = exp(-2 * n * ((a - mu) / n) ** 2)
    ex = float(exact_tail(a))
    print(f"{a:4d}  {ex:.2e}  {float(markov):.3f}  {float(cheb):9.4f}"
          f"  {float(chern):.2e}   {hoeff:.2e}")

two_sided = 2 * exact_tail(60)        # P(|X - 50| >= 10), by symmetry
print(f"P(|X - 50| >= 10) = {float(two_sided):.4f}  Chebyshev: <= 0.25")

   a     exact   Markov  Chebyshev  Chernoff  Hoeffding
  55  1.84e-01  0.909     1.0000  7.85e-01   6.07e-01
  60  2.84e-02  0.833     0.2500  3.91e-01   1.35e-01
  70  3.93e-05  0.714     0.0625  2.86e-02   3.35e-04
  80  5.58e-10  0.625     0.0278  5.00e-04   1.52e-08
P(|X - 50| >= 10) = 0.0569  Chebyshev: <= 0.25

টেবিলে Hoeffding গুণনীয় Chernoff-কে হারিয়েছে, কারণ p = 1/2. বিরল ঘটনায় উল্টোটি হয়। বাজারঘরের চালানে (n = 400, p = 0.05, μ = 20) P(X ≥ 30) নিন: exact 0.0190, Markov 0.667, Chebyshev 0.19, গুণনীয় Chernoff (δ = 0.5) 0.115, তার সরল রূপ e^−5/3 ≈ 0.189, অথচ Hoeffding e^{−2·400·0.025²} = e^−0.5 ≈ 0.607. Hoeffding শুধু জানে মান [0, 1]-এ, আর ধরে নেয় সবচেয়ে খারাপ variance; গুণনীয় রূপ μ ছোট হওয়ার সুবিধা নেয়। তাই সীমা বাছাইয়ের প্রশ্নটি “কোনটি সেরা” নয়, “আমার কাছে কী তথ্য আছে, আর ঘটনাটি বিরল কি না”।

৮ · Amplification — বারবার চালিয়ে ভুল কমানো

একটি randomized algorithm প্রতিবার ২/৩ সম্ভাবনায় ঠিক “হ্যাঁ/না” উত্তর দেয়। ৩৩% ভুল কোনো কাজের নয় মনে হতে পারে। কিন্তু algorithm-টি k বার, প্রতিবার নতুন এলোমেলো সংখ্যা দিয়ে স্বাধীনভাবে চালিয়ে যে উত্তর বেশিবার এসেছে, সেটি নিলে (majority vote) ভুল দ্রুত কমে। ভুল কমানোর এই কৌশলের নাম amplification.

প্রমাণ:

1. Xᵢ = 1 যদি i-তম চালনা ঠিক, নইলে 0. Xᵢ-গুলো যৌথভাবে স্বাধীন, কারণ প্রতিবার নতুন এলোমেলো সংখ্যা। X̄ = ঠিক উত্তরের অনুপাত, আর q = E[X̄] ≥ 2/3. — indicator, linearity
2. Majority ভুল মানে ঠিক উত্তর অর্ধেকের কম: X̄ < 1/2, ফলে X̄ − q < 1/2 − 2/3 = −1/6. — k বিজোড়, সমতা হয় না
3. Hoeffding-এ (p-এর জায়গায় q) ε = 1/6: সম্ভাবনা ≤ e^−2k/36 = e^−k/18. — উপপাদ্য ৬.২
4. e^−k/18 ≤ η ⇔ k ≥ 18 ln(1/η). ∎

Chebyshev দিয়েও একটি সীমা আসে, তবে অনেক দুর্বল: ঠিক উত্তরের সংখ্যার variance k · (2/3)(1/3) = 2k/9, আর ভুল হতে হলে সংখ্যাটি গড় 2k/3 থেকে অন্তত k/6 দূরে যেতে হয়, তাই ভুল ≤ (2k/9)/(k/6)² = 8/k. ১০ লাখে একবার ভুলের জন্য Chebyshev চায় k = 80 লাখ, Hoeffding চায় k = 249, আর exact হিসাব বলে 193 যথেষ্ট। নিচের stepper ছোট k-তে exact ভুল হাতে বের করে।

1k = 1: ভুল = 1/32k = 3: ≤ 1 ঠিক → 7/273k = 5: ≤ 2 ঠিক → 17/814k = 25, 101: 0.0415, 0.000275Chebyshev: ≤ 8/k6Hoeffding: ≤ e^(−k/18)

from fractions import Fraction as F
from math import comb, exp
import random

def majority_error(k):            # each run correct with prob 2/3, k odd
    bad = sum(comb(k, j) * 2**j for j in range((k + 1) // 2))   # j correct
    return F(bad, 3**k)           # fewer than half correct

print("  k   exact error  Chebyshev 8/k  Hoeffding e^(-k/18)")
for k in (1, 3, 5, 9, 25, 51, 101, 193):
    err = majority_error(k)
    print(f"{k:3d}   {float(err):.3e}    {min(1, 8 / k):.3e}    {exp(-k / 18):.3e}")
print("exact for k = 3:", majority_error(3), "  k = 5:", majority_error(5))

k = 1
while majority_error(k) > F(1, 10**6):
    k += 2
print("smallest odd k with error <= 1e-6:", k)

random.seed(41)                   # simulate k = 25 runs, 20000 times
trials, wrong = 20_000, 0
for _ in range(trials):
    correct = sum(random.random() < 2 / 3 for _ in range(25))
    wrong += correct <= 12
print(f"k = 25 simulated {wrong / trials:.4f}  exact {float(majority_error(25)):.4f}")

  k   exact error  Chebyshev 8/k  Hoeffding e^(-k/18)
  1   3.333e-01    1.000e+00    9.460e-01
  3   2.593e-01    1.000e+00    8.465e-01
  5   2.099e-01    1.000e+00    7.575e-01
  9   1.448e-01    8.889e-01    6.065e-01
 25   4.151e-02    3.200e-01    2.494e-01
 51   6.888e-03    1.569e-01    5.882e-02
101   2.724e-04    7.921e-02    3.657e-03
193   9.027e-07    4.145e-02    2.205e-05
exact for k = 3: 7/27   k = 5: 17/81
smallest odd k with error <= 1e-6: 193
k = 25 simulated 0.0428  exact 0.0415

এক দিকের ভুল: Miller–Rabin

কিছু algorithm-এর ভুল শুধু এক দিকে হয়। পর্ব ২৫-এর Miller–Rabin পরীক্ষা “যৌগিক” বললে তা নিশ্চিত সত্য; ভুল হতে পারে শুধু একটি বিজোড় যৌগিক সংখ্যাকে “সম্ভবত মৌলিক” বলায়, আর প্রতিটি এলোমেলো base-এ সেই সম্ভাবনা ≤ 1/4. এখানে majority লাগে না: k-টি স্বাধীন base-এর একটিও যৌগিকতা ধরলে উত্তর “যৌগিক”, আর সবগুলো ব্যর্থ হওয়ার সম্ভাবনা স্বাধীনতার গুণনের নিয়মে ≤ (1/4)^k. k = 20-এ এটি ≤ 4⁻²⁰ ≈ 9.1 × 10⁻¹³. এক দিকের ভুলে amplification তাই আরও সস্তা: ভুল প্রতি চালনায় নির্দিষ্ট গুণে কমে, কোনো concentration bound ছাড়াই।

সামনের ঝলক: hash bucket-এর ভার

n-টি অর্ডার আইডি n-টি hash bucket-এ এলোমেলোভাবে পড়লে প্রতিটি bucket-এ গড়ে ১টি আইডি। কিন্তু সবচেয়ে ভারী bucket-এ কতটি? প্রতিটি bucket-এর ভার স্বাধীন 0/1 চলকের যোগ, তাই Chernoff তার লেজ বাঁধে; তারপর n-টি bucket-এর ওপর union bound (পর্ব ৩৮-এর Boole-এর অসমতা) দিলে দেখা যায়, উচ্চ সম্ভাবনায় কোনো bucket-এই O(log n)-এর বেশি আইডি পড়ে না। আরও সূক্ষ্ম উত্তর Θ(log n / log log n), আর পুরো আলোচনা পর্ব ৪২ “Birthday paradox, hash collision আর balls-into-bins”-এ। Hash table-এর কোড আর load factor DSA কোর্সের পর্ব ৩২-এ আছে।

৯ · পরীক্ষার অঙ্ক আর একটি ভুল প্রমাণ

বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর লিখিত পরীক্ষায় এই পর্বের ধাঁচে যে অঙ্ক আসে, তার কয়েকটি পূর্ণ সমাধান। প্রতিটি সংখ্যা scratch-এ Python-এর Fraction দিয়ে মেলানো।

অঙ্ক ১: ৬০০ বার ছক্কা

একটি নিরপেক্ষ ছক্কা ৬০০ বার ছোড়া হলো; X = কতবার 6 এল। E[X], Var(X) বের করুন, আর Chebyshev দিয়ে P(|X − 100| ≥ 20)-এর সীমা দিন।

1. X binomial, n = 600, p = 1/6. E[X] = 600/6 = 100.
2. Var(X) = 600 × (1/6) × (5/6) = 250/3 ≈ 83.33.
3. Chebyshev: P(|X − 100| ≥ 20) ≤ (250/3)/400 = 5/24 ≈ 0.208. (Exact মান প্রায় 0.0325.)

অঙ্ক ২: ঘণ্টায় অর্ডার

বাজারঘরে ঘণ্টায় অর্ডারের সংখ্যা X-এর গড় 50. (ক) শুধু এটুকু জেনে P(X ≥ 100)-এর সীমা কত? (খ) যদি Var(X) = 25 জানা থাকে?

1. (ক) X ≥ 0, তাই Markov: P(X ≥ 100) ≤ 50/100 = 1/2.
2. (খ) X ≥ 100 হলে |X − 50| ≥ 50, তাই Chebyshev: P(X ≥ 100) ≤ 25/50² = 1/100. বাড়তি তথ্য (variance) সীমাকে ৫০ গুণ শক্ত করেছে।

অঙ্ক ৩: নমুনার আকার

দেরিতে পৌঁছানো অর্ডারের অনুপাত ±0.02-এর মধ্যে মাপতে হবে, ভুলের সম্ভাবনা ≤ 0.01. Chebyshev আর Hoeffding অনুযায়ী কত নমুনা যথেষ্ট?

1. Chebyshev, σ² ≤ 1/4: 1/(4n × 0.02²) ≤ 0.01 ⇔ n ≥ 1/(4 × 0.0004 × 0.01) = 62,500.
2. Hoeffding: 2e^{−2n(0.02)²} ≤ 0.01 ⇔ n ≥ ln(200)/(2 × 0.0004) ≈ 6622.9, তাই n = 6623.
3. একই নিশ্চয়তায় Hoeffding প্রায় সাড়ে নয় গুণ কম নমুনা চায়।

প্রমাণের ভুল ধরুন: “Markov সব চলকে খাটে”

একজন লিখলেন: “দাবি: যেকোনো random variable X আর a > 0-তে P(X ≥ a) ≤ E[X]/a. প্রমাণ: I = {X ≥ a}-এর indicator. তাহলে a · I ≤ X, কারণ I = 1 হলে X ≥ a. প্রত্যাশা নিলে a · P(X ≥ a) ≤ E[X]. ∎” পড়ে ভুলটি নিজে খুঁজুন।

ভুল কোথায়: a · I ≤ X দুই ক্ষেত্রে দেখাতে হয়, আর প্রমাণটি শুধু I = 1-এর ক্ষেত্র দেখেছে। I = 0 হলে দাবিটি 0 ≤ X, যা X ঋণাত্মক হতে পারলে মিথ্যা। Counterexample: একটি দিনের লাভ X = −3 বা +3, প্রতিটি 1/2 সম্ভাবনায়। তাহলে E[X] = 0, আর “Markov” বলত P(X ≥ 3) ≤ 0, অথচ আসল মান 1/2. ঠিক সংস্করণে শর্ত X ≥ 0 লাগে; ঋণাত্মক মান থাকলে প্রথমে X − m-এর মতো একটি অঋণাত্মক চলকে নিন (m = X-এর ক্ষুদ্রতম মান), বা |X|, (X − μ)², e^tX-এর মতো চলকে Markov বসান, ঠিক যেমন Chebyshev আর Chernoff করে।

১০ · AI-এর যুগে — সম্ভাবনার সীমা আর প্রমাণ যাচাই

সম্ভাবনার অসমতায় AI সহকারী প্রায়ই একটি সুন্দর, আত্মবিশ্বাসী উত্তর দেয়, যার ভুল লুকিয়ে থাকে কোনো বাদ পড়া শর্তে বা একটি ছোট ধাপে। এই পর্বের বিষয়ে কয়েকটি ভুল নিয়মিত দেখা যায়:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• প্রতিটি অসমতার শর্ত (অঋণাত্মকতা, স্বাধীনতার ধরন, মানের পরিসর) প্রশ্নে সত্যি খাটে কি না মিলিয়েছি
• ছোট ক্ষেত্রে exact মান Fraction দিয়ে বের করে দেখেছি সীমাটি তার ওপরে কি না
• Variance-এর হিসাবে cross term বা covariance বাদ পড়েনি তা পরীক্ষা করেছি
• একটি seeded simulation চালিয়ে মিলিয়েছি, কিন্তু simulation-কে প্রমাণ ভাবিনি
• “সম্ভাবনা = x” আর “সম্ভাবনা ≤ x” আলাদা করে পড়েছি
• উদ্ধৃত সাল, নাম আর বইয়ের তথ্য বিশ্বস্ত উৎসে মিলিয়েছি

সম্ভাবনার সীমা যাচাইয়ের সবচেয়ে সস্তা উপায় হলো exact মান পাশে রাখা। ছোট n-এ C(n, k)-এর যোগ এক সেকেন্ডেই হয়; AI-এর দেওয়া সীমা যদি কোথাও exact মানের নিচে নামে, তবে প্রমাণে নিশ্চিত ভুল আছে, আর সেই ধাপটিই খুঁজতে হবে।