Random variable আর প্রত্যাশা — linearity-র জাদু

১ · Random variable — ফলাফল থেকে সংখ্যা

কাল্পনিক অনলাইন দোকান বাজারঘর প্রতিদিন সকালে একটি ভ্যানে ১০টি পার্সেল পাঠায়। দিনের শেষে ম্যানেজার জানতে চান না যে ঠিক কোন কোন পার্সেল দেরিতে পৌঁছেছে; তিনি জানতে চান কয়টি দেরিতে পৌঁছেছে। পুরো দিনের ফলাফল একটি লম্বা বিবরণ (প্রথম পার্সেল সময়মতো, দ্বিতীয়টি দেরিতে, …), কিন্তু তাঁর দরকার একটি সংখ্যা। ফলাফল থেকে সংখ্যা বানানোর এই নিয়মটিই random variable.

পর্ব ৩৮ “বিচ্ছিন্ন সম্ভাবনা — sample space, event আর Laplace-এর সংজ্ঞা”-এ একটি পরীক্ষার সব সম্ভাব্য ফলাফলের সেটকে বলা হয়েছে sample space Ω, আর প্রতিটি ফলাফল ω-এর সম্ভাবনা P(ω) ≥ 0, যাদের যোগফল 1. এই পর্বে Ω সবসময় সসীম বা গণনাযোগ্য (countable), অর্থাৎ বিচ্ছিন্ন।

সবচেয়ে ছোট উদাহরণ: একটি মুদ্রা দুবার ছোড়া, Ω = {HH, HT, TH, TT}, প্রতিটির সম্ভাবনা 1/4. X = মোট head-এর সংখ্যা। তাহলে X(HH) = 2, X(HT) = X(TH) = 1, X(TT) = 0. preimage গুনলে P(X = 0) = 1/4, P(X = 1) = 2/4 = 1/2, P(X = 2) = 1/4. খেয়াল করুন, X one-to-one নয়: দুটি আলাদা ফলাফল একই মান 1 পায়, আর সেই কারণেই মান 1-এর সম্ভাবনা বেশি।

দুটি সহজ তথ্য, যা প্রতিটি pmf মেনে চলে: (১) p_X(x) ≥ 0, আর (২) সব x-এর ওপর ∑ p_X(x) = 1. দ্বিতীয়টির প্রমাণ: “X = x” event-গুলো আলাদা x-এর জন্য পরস্পর বিচ্ছিন্ন, আর মিলে পুরো Ω, কারণ প্রতিটি ω ঠিক একটি মানে যায় (ফাংশনের সংজ্ঞা)। তাই তাদের সম্ভাবনার যোগফল P(Ω) = 1. ফাংশন হওয়ার শর্তটিই এখানে কাজ করছে: একটি ফলাফল দুটি মান পেলে যোগফল 1 ছাড়িয়ে যেত।

একই Ω-এর ওপর অনেক random variable থাকতে পারে। দুটি ছক্কা ছুড়লে (৩৬টি সমান সম্ভাব্য ফলাফল) S = যোগফল, M = বড়টি, D = পার্থক্য, সবই আলাদা ফাংশন। পর্ব ৩৮-এর সেই সতর্কবাণী এখানেও খাটে: S-এর মান ১১টি (2 থেকে 12), কিন্তু তারা সমান সম্ভাব্য নয়; সমান সম্ভাব্য হলো ৩৬টি ফলাফল। random variable-এর মানগুলো গুনে Laplace-এর সংজ্ঞা লাগালে ভুল হয়; গুনতে হয় preimage-এর ফলাফল। দুটি চলক X, Y থেকে নতুন চলক বানানো যায়: X + Y, XY, X², max(X, Y), কারণ এগুলো ω ধরে ধরে সংজ্ঞায়িত, যেমন (X + Y)(ω) = X(ω) + Y(ω).

২ · চারটি মৌলিক বণ্টন — Bernoulli, uniform, binomial আর geometric

বিচ্ছিন্ন গণিতে আর algorithm বিশ্লেষণে বারবার চারটি বণ্টন ফিরে আসে। চারটিই গণনা থেকে সরাসরি বের হয়; কোনো ক্যালকুলাস লাগে না।

প্রমাণ:

1. একটি ফলাফল হলো দৈর্ঘ্য n-এর একটি S/F (সাফল্য/ব্যর্থতা) সারি। চেষ্টাগুলো স্বাধীন, তাই একটি নির্দিষ্ট সারির সম্ভাবনা প্রতিটি ঘরের সম্ভাবনার গুণফল। — স্বাধীনতার সংজ্ঞা (পর্ব ৩৯-এ বিস্তারিত)
2. যে সারিতে ঠিক k-টি S, তার সম্ভাবনা p^k(1 − p)^n−k, কোন ঘরে S বসল তার ওপর নির্ভর করে না। — গুণফলে ক্রম বদলায় না
3. ঠিক k-টি S-এর সারি কয়টি? n-টি ঘর থেকে S-এর k-টি ঘর বাছাই: C(n, k)টি (পর্ব ৩৩)। — combination
4. আলাদা সারিগুলো পরস্পর বিচ্ছিন্ন ফলাফল, তাই তাদের সম্ভাবনা যোগ হয়: C(n, k) p^k(1 − p)^n−k. — সম্ভাবনার যোগের axiom
5. যাচাই: সব k-এর যোগ = (p + (1 − p))ⁿ = 1ⁿ = 1, binomial theorem অনুযায়ী (পর্ব ৩৪)। ∎ — binomial theorem

নামটির উৎসও এটি: pmf-গুলো হলো (p + q)ⁿ-এর বিস্তারের পদ, q = 1 − p. স্বাধীনতার শর্তটি জরুরি। একটি ২০টি পণ্যের লট থেকে, যার ৪টি ত্রুটিপূর্ণ, ফেরত না রেখে ৫টি তুললে ত্রুটিপূর্ণের সংখ্যা binomial নয়; প্রতিটি তোলা আগেরটির ওপর নির্ভর করে, আর সেখানে hypergeometric সূত্র C(4, k)C(16, 5 − k)/C(20, 5) খাটে (পর্ব ৩৮)। §৮-এর অঙ্কে দেখবেন, স্বাধীনতা না থাকলেও সেখানকার প্রত্যাশা একই সহজ কৌশলে বের হয়।

প্রমাণ: “X = k” ঘটে ঠিক তখন, যখন প্রথম k − 1টি চেষ্টা ব্যর্থ আর k-তমটি সফল; স্বাধীনতায় এর সম্ভাবনা (1 − p)^k−1p. যোগফল যাচাই: q = 1 − p ধরলে ∑_k≥1 q^k−1p = p · 1/(1 − q) = p/p = 1, কারণ 0 ≤ q < 1 হলে গুণোত্তর ধারা অভিসারী (পর্ব ১৭)। ∎ বাজারঘরের উদাহরণ: একজন গ্রাহক বাসায় থাকেন সম্ভাবনা 4/5, আর প্রতিটি ডেলিভারি চেষ্টা আলাদা দিনে, স্বাধীন। তাহলে তৃতীয় চেষ্টায় প্রথম সফল ডেলিভারির সম্ভাবনা (1/5)² · (4/5) = 4/125.

এবার Python-এ binomial-এর নিখুঁত pmf (Fraction দিয়ে) আর একটি seed দেওয়া simulation পাশাপাশি দেখা যাক। বাজারঘরের ভ্যানে ১০টি পার্সেল, প্রতিটি স্বাধীনভাবে 1/5 সম্ভাবনায় দেরিতে পৌঁছায়। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

import random
from fractions import Fraction
from math import comb

n, p = 10, Fraction(1, 5)          # 10 parcels, each late with probability 1/5
pmf = {k: comb(n, k) * p**k * (1 - p)**(n - k) for k in range(n + 1)}
print("sum of pmf:", sum(pmf.values()))
print("E[X] by definition:", sum(k * q for k, q in pmf.items()), "  n*p =", n * p)

random.seed(40)
trials = 20000
counts = [0] * (n + 1)
for _ in range(trials):
    late = sum(random.random() < 0.2 for _ in range(n))
    counts[late] += 1

print(" k   exact    simulated")
for k in range(6):
    print(f"{k:2d}  {float(pmf[k]):.4f}   {counts[k] / trials:.4f}")
tail = sum(pmf[k] for k in range(6, n + 1))
print(f"6+  {float(tail):.4f}   {sum(counts[6:]) / trials:.4f}")
mean = sum(k * c for k, c in enumerate(counts)) / trials
print(f"average late parcels in the simulation: {mean:.4f}")

sum of pmf: 1
E[X] by definition: 2   n*p = 2
 k   exact    simulated
 0  0.1074   0.1104
 1  0.2684   0.2650
 2  0.3020   0.3013
 3  0.2013   0.2008
 4  0.0881   0.0909
 5  0.0264   0.0255
6+  0.0064   0.0063
average late parcels in the simulation: 1.9990

৩ · প্রত্যাশা — ভারযুক্ত গড়, আর যখন গড় অসীম

বাজারঘরের ম্যানেজার যদি একশো দিন ধরে প্রতিদিনের দেরির সংখ্যা লেখেন, তার গড় প্রায় 2 আসবে; উপরের simulation-এ এসেছে 1.999. দীর্ঘ মেয়াদে এই গড় কোথায় থিতু হয়, তা আগে থেকেই pmf থেকে বের করা যায়। প্রতিটি মানকে তার সম্ভাবনা দিয়ে গুণ করে যোগ করলেই হয়, ঠিক যেমন পরীক্ষার গড় নম্বর হিসাবে প্রতিটি নম্বরকে সেই নম্বর পাওয়া শিক্ষার্থীর অনুপাত দিয়ে গুণ করা হয়।

দুটি রূপ কেন সমান? দ্বিতীয় যোগফলে ω-গুলোকে X-এর মান ধরে দলে ভাগ করুন। যে দলে X(ω) = x, সেখানে প্রতিটি পদ x · P(ω), আর দলের মোট x · P(X = x). সব দল যোগ করলে প্রথম রূপ। ধনাত্মক পদের অসীম যোগফলে বা absolutely convergent যোগফলে এমন পুনর্বিন্যাস বৈধ; শর্তটি সেই জন্যই। প্রথম রূপ হিসাবের জন্য সুবিধাজনক, দ্বিতীয় রূপ প্রমাণের জন্য, যা §৪-এ দেখবেন।

কয়েকটি সরাসরি হিসাব:

• ছক্কা: E[X] = (1 + 2 + 3 + 4 + 5 + 6)/6 = 21/6 = 7/2. খেয়াল করুন, 3.5 কখনো ছক্কায় ওঠে না; প্রত্যাশিত মান মানে “সম্ভাব্য মান” নয়, দীর্ঘ মেয়াদের গড়।
• Bernoulli(p): E[X] = 0 · (1 − p) + 1 · p = p.
• {1, …, n}-এ uniform: E[X] = (1 + 2 + … + n)/n = (n + 1)/2, Gauss-এর যোগফল দিয়ে (পর্ব ১৭)।
• Binomial: সংজ্ঞা ধরে ∑ k C(n, k) p^k(1 − p)^n−k হিসাব করা যায় (k C(n, k) = n C(n − 1, k − 1) identity দিয়ে), কিন্তু §৪-এ এর চেয়ে অনেক সহজ পথ আছে। উত্তর np.

প্রমাণ (perturbation, পর্ব ১৭-এর কৌশল): q = 1 − p ধরুন, 0 ≤ q < 1.

1. E[X] = ∑_k≥1 k q^k−1p = p · S, যেখানে S = 1 + 2q + 3q² + 4q³ + …. — সংজ্ঞা
2. S অভিসারী: k q^k−1-এর পরপর দুই পদের অনুপাত (k + 1)q/k → q < 1, তাই ratio test অনুযায়ী ধারাটি অভিসারী। — ratio test
3. qS = q + 2q² + 3q³ + …. পদে পদে বিয়োগ করলে S − qS = 1 + q + q² + q³ + … = 1/(1 − q). — অভিসারী ধারার পদে পদে বিয়োগ
4. তাই S(1 − q) = 1/(1 − q), অর্থাৎ S = 1/(1 − q)² = 1/p². — বীজগণিত
5. E[X] = p · 1/p² = 1/p. ∎

অর্থ খুব স্বাভাবিক: গ্রাহক বাসায় থাকার সম্ভাবনা 4/5 হলে গড়ে 5/4 চেষ্টা লাগে; সম্ভাবনা 1/6 হলে (যেমন ছক্কায় ছয়) গড়ে ৬টি ছোড়া। নিচের stepper p = 1/2 নিয়ে ধারাটি ধাপে ধাপে যোগ করে আর perturbation-এ বন্ধ রূপে পৌঁছায়।

1P(X = k) = (1/2)^k2k = 1, 2: 1/2 + 2/43k = 3, 4: + 3/8 + 4/164k = 5, 6, 7 → 247/1285S − qS = 1 + q + q² + …6E = p · 1/p² = 1/p = 2

যখন প্রত্যাশা অসীম — St Petersburg paradox

একটি চিন্তা-পরীক্ষা: মুদ্রা ছুড়তে থাকুন যতক্ষণ না প্রথম head আসে; head যদি k-তম ছোড়ায় আসে, পুরস্কার 2^k পয়েন্ট। প্রত্যাশিত পুরস্কার = ∑ 2^k · 2^−k = 1 + 1 + 1 + … = ∞. অথচ বাস্তবে প্রায় সব খেলাতেই পুরস্কার ছোট: অর্ধেক সময় মাত্র 2 পয়েন্ট। এটিই St Petersburg paradox, যার ইতিহাস ভাবনার প্রশ্নে আছে। গাণিতিক শিক্ষা দুটি: (১) প্রত্যাশা একটি অসীম যোগফল, যা অভিসারী না-ও হতে পারে, তাই সংজ্ঞায় শর্তটি অলংকার নয়; (২) পুরস্কারের ভাণ্ডার সীমিত হলে ছবি বদলে যায়। ভাণ্ডারে সর্বোচ্চ 2²⁰ = 10,48,576 পয়েন্ট থাকলে প্রত্যাশা মাত্র 21 (প্রথম ২০টি পদে 20, বাকি সব মিলে 1; scratch-এ Fraction দিয়ে যাচাই করা)।

৪ · Linearity of expectation — স্বাধীনতা ছাড়াই যোগ

এই পর্বের কেন্দ্রীয় উপপাদ্য, linearity of expectation, দেখতে খুব নিরীহ, কিন্তু ব্যবহারে প্রায় জাদুর মতো। এর শক্তি একটি বাক্যে: যোগফলের প্রত্যাশা প্রত্যাশার যোগফল, চলকগুলো একে অপরের ওপর যত নির্ভরশীলই হোক।

প্রমাণ:

1. aX + bY একটি random variable, যার মান (aX + bY)(ω) = aX(ω) + bY(ω). — ফাংশনের যোগ
2. E[aX + bY] = ∑_ω (aX(ω) + bY(ω)) P(ω). যোগফলটি absolutely convergent, কারণ |aX(ω) + bY(ω)| ≤ |a||X(ω)| + |b||Y(ω)| আর ডান দিকের দুটি যোগফল সসীম। — সংজ্ঞা ৩.১-এর দ্বিতীয় রূপ, তুলনা
3. Absolutely convergent যোগফলকে পদে পদে ভাগ করা যায়: = a ∑_ω X(ω)P(ω) + b ∑_ω Y(ω)P(ω). — যোগফলের রৈখিকতা
4. = a E[X] + b E[Y]. ∎ — সংজ্ঞা ৩.১

প্রমাণে কোথাও P(X = x, Y = y)-এর মতো যৌথ সম্ভাবনা আসেনি। কারণটি গভীর: প্রত্যাশাকে ω-এর ওপর যোগফল হিসেবে লিখলে প্রতিটি ω-তে X আর Y-এর মান শুধু দুটি সংখ্যা, আর সংখ্যার যোগ সবসময় রৈখিক। নির্ভরশীলতা প্রভাব ফেলে কোন ω কত সম্ভাবনা পায় তাতে, কিন্তু সেই একই P(ω) দুই দিকেই বসে। আসলে এটি পর্ব ৩৭-এর double counting-এর ভাষায় একটি “সারি ধরে না গুনে কলাম ধরে গোনা”।

Indicator random variable — event থেকে সংখ্যা

দুটি মিলিয়ে একটি সর্বজনীন কৌশল তৈরি হয়। “কয়টি জিনিস ঘটল” ধরনের যেকোনো সংখ্যা X-কে লিখুন X = I₁ + I₂ + … + I_n, যেখানে I_i হলো “i-তম জিনিসটি ঘটল”-এর indicator. তাহলে linearity অনুযায়ী

E[X] = P(A₁) + P(A₂) + … + P(A_n)

X-এর পুরো pmf জানার দরকার নেই; প্রতিটি ছোট event-এর সম্ভাবনা জানলেই যথেষ্ট। প্রথম প্রয়োগ: binomial-এর প্রত্যাশা। X = মোট সাফল্য = I₁ + … + I_n, যেখানে I_i হলো i-তম চেষ্টা সফল হওয়ার indicator, E[I_i] = p. তাই E[X] = np, এক লাইনে। Code ব্লকে সংজ্ঞা ধরে পাওয়া 2 = 10 × 1/5 এখন প্রমাণিত।

আরও একটি উদাহরণ, যেখানে স্বাধীনতা নেই। একটি মুদ্রা ১০ বার ছুড়লে পরপর দুটি head (“HH”, পরস্পর জড়িয়ে থাকলেও আলাদা গুনে) গড়ে কয়বার আসে? i = 1, …, 9-এর জন্য J_i = “i-তম আর (i + 1)-তম ছোড়া দুটিই head”. J₁ আর J₂ স্বাধীন নয় (দুটিতেই দ্বিতীয় ছোড়া আছে), কিন্তু linearity-র তাতে কিছু যায় আসে না: E = 9 × 1/4 = 9/4. ২¹⁰ = 1024টি ফলাফল ধরে scratch-এ গুনেও ঠিক 9/4 এসেছে।

৫ · Indicator-এর জাদু — fixed point আর record

এলোমেলো permutation-এ fixed point

বাজারঘরের অফিসে n জন কর্মী সকালে নিজের নামের ট্যাগ লাগানো একই রকম ব্যাগ জমা রাখেন। সন্ধ্যায় ট্যাগগুলো খুলে গেছে, আর ব্যাগগুলো এলোমেলোভাবে ফেরত দেওয়া হলো (সব n! বিন্যাস সমান সম্ভাব্য)। গড়ে কতজন নিজের ব্যাগ ফেরত পাবেন? গণিতের ভাষায়: এলোমেলো permutation π-তে fixed point (যেখানে π(i) = i) গড়ে কয়টি?

প্রমাণ:

1. X = fixed point-এর সংখ্যা = I₁ + … + I_n, যেখানে I_i = 1 যদি π(i) = i. — indicator-এ ভাঙা
2. π(i) = i এমন permutation গুনুন: i-কে নিজের জায়গায় রেখে বাকি n − 1টি উপাদান যেকোনোভাবে, তাই (n − 1)!টি। — গুণের নিয়ম
3. E[I_i] = P(π(i) = i) = (n − 1)!/n! = 1/n. — লেমা ৪.৩, Laplace
4. E[X] = n · 1/n = 1. ∎ — উপপাদ্য ৪.১

I_i-গুলো স্বাধীন নয়: n − 1 জন নিজের ব্যাগ পেলে শেষজনও পাবেন। তবু উত্তর বের হলো, কারণ linearity-তে স্বাধীনতা লাগে না। উল্টো দিকে, X-এর পুরো pmf বের করা অনেক কঠিন; “একজনও নিজের ব্যাগ না পাওয়া” (derangement)-এর সম্ভাবনা পর্ব ৪৯ “Inclusion–exclusion আর derangement”-এ প্রমাণ হবে, আর সেটি দ্রুত 1/e ≈ 0.3679-এর দিকে যায়। নিচের stepper n = 3-এ সব ৬টি permutation ধরে indicator-গুলো গোনে।

1π = 123 → I = 1,1,1 → X = 32π = 132 → I = 1,0,0 → X = 13π = 213 → I = 0,0,1 → X = 14π = 231 → I = 0,0,0 → X = 05π = 312 → I = 0,0,0 → X = 06π = 321 → I = 0,1,0 → X = 17E[X] = 6/6 = 3 · 2/6 = 1

Record বা left-to-right maximum

বাজারঘর একজন ডেলিভারি ম্যানেজার নিয়োগ দেবে। n জন প্রার্থী এলোমেলো ক্রমে সাক্ষাৎকারে আসেন, আর নীতি হলো: যে প্রার্থী এ পর্যন্ত দেখা সবার চেয়ে ভালো, তাঁকে সঙ্গে সঙ্গে সাময়িক নিয়োগ দেওয়া (algorithm বইয়ে এটি “hiring problem” নামে পরিচিত)। গড়ে কতবার নিয়োগ হবে? সংখ্যার একটি সারিতে যে উপাদান তার আগের সবার চেয়ে বড়, তাকে বলে left-to-right maximum বা record.

প্রমাণ: R_k = 1 যদি k-তম অবস্থানের উপাদান প্রথম k-টির মধ্যে সবচেয়ে বড়। প্রথম k-টি উপাদান কোন সেট থেকে এল, তা যা-ই হোক, সেই k-টির সব k! ক্রম সমান সম্ভাব্য, তাই তাদের বৃহত্তমটি k-টি অবস্থানের যেকোনোটিতে থাকার সম্ভাবনা সমান: P(R_k = 1) = 1/k. Linearity অনুযায়ী E[record] = ∑_k=1ⁿ 1/k = H_n. ∎ পর্ব ১৭-এ দেখেছেন H_n প্রায় ln n + 0.5772, তাই ১০০ জন প্রার্থীতে গড়ে মাত্র H₁₀₀ ≈ 5.19 বার নিয়োগ। একই যুক্তি algorithm-এ দেখায়, একটি এলোমেলো array-তে “এ পর্যন্ত সর্বোচ্চ” চলকটি গড়ে মাত্র H_n বার আপডেট হয়।

এবার দুটি উপপাদ্যই brute force-এ মেলানো যাক: n ≤ 8-এ সব permutation ধরে নিখুঁত গড় (৮! = 40,320টি পর্যন্ত), আর n = 52-এ seed দেওয়া shuffle. Python-এর random.shuffle ভেতরে Fisher–Yates ব্যবহার করে, যা সব বিন্যাস সমান সম্ভাব্য করে (পর্ব ৩৬-এ প্রমাণ)।

import random
from fractions import Fraction
from itertools import permutations

def fixed(p):                      # number of i with p[i] == i
    return sum(1 for i, v in enumerate(p) if i == v)

def records(p):                    # left-to-right maxima
    r, best = 0, -1
    for v in p:
        if v > best:
            r, best = r + 1, v
    return r

def H(n):
    return sum(Fraction(1, k) for k in range(1, n + 1))

print(" n  E[fixed]  P(no fixed)  E[records]  = H_n?")
for n in range(1, 9):
    perms = list(permutations(range(n)))
    N = len(perms)
    ef = Fraction(sum(fixed(p) for p in perms), N)
    p0 = Fraction(sum(1 for p in perms if fixed(p) == 0), N)
    er = Fraction(sum(records(p) for p in perms), N)
    print(f"{n:2d}  {str(ef):>7}  {float(p0):10.4f}  {str(er):>10}  {er == H(n)}")

random.seed(40)
n, trials = 52, 10000
a = list(range(n))
total = 0
for _ in range(trials):
    random.shuffle(a)
    total += fixed(a)
print(f"n = 52, simulated E[fixed]: {total / trials:.4f}")

 n  E[fixed]  P(no fixed)  E[records]  = H_n?
 1        1      0.0000           1  True
 2        1      0.5000         3/2  True
 3        1      0.3333        11/6  True
 4        1      0.3750       25/12  True
 5        1      0.3667      137/60  True
 6        1      0.3681       49/20  True
 7        1      0.3679     363/140  True
 8        1      0.3679     761/280  True
n = 52, simulated E[fixed]: 1.0100

৬ · Coupon collector — সবগুলো পেতে কত সময়

বাজারঘর একটি প্রচারণায় প্রতিটি অর্ডারের সঙ্গে n রকম নকশার একটি স্টিকার দেয়, প্রতিবার n রকমের যেকোনোটি সমান সম্ভাবনায়, আগের অর্ডার থেকে স্বাধীনভাবে। একজন গ্রাহক সব n রকম সংগ্রহ করতে চান। গড়ে কয়টি অর্ডার লাগবে? এটি বিখ্যাত coupon collector problem. একই প্রশ্ন কম্পিউটার বিজ্ঞানে বারবার আসে: এলোমেলো test input দিয়ে n-টি শাখার সবকটি ছুঁতে কত input লাগে, বা এলোমেলো hash-এ n-টি bucket-এর প্রতিটিতে অন্তত একটি key পড়তে কয়টি key লাগে।

প্রমাণ:

1. সংগ্রহকে n-টি ধাপে ভাগ করুন। ধাপ i (i = 1, …, n) শুরু হয় যখন ঠিক i − 1 রকম নকশা হাতে আছে, আর শেষ হয় যখন i-তম নতুন নকশা আসে। T_i = ধাপ i-তে অর্ডারের সংখ্যা, তাহলে T = T₁ + … + T_n. — ভাগ করা
2. ধাপ i-তে প্রতিটি অর্ডার নতুন নকশা দেয় যদি তা বাকি n − i + 1 রকমের একটি হয়: সম্ভাবনা p_i = (n − i + 1)/n, প্রতিবার স্বাধীনভাবে। — uniform আর স্বাধীন অর্ডার
3. তাই T_i হলো প্রথম সাফল্য পর্যন্ত চেষ্টার সংখ্যা: T_i ~ Geometric(p_i), আর উপপাদ্য ৩.২ অনুযায়ী E[T_i] = 1/p_i = n/(n − i + 1). — geometric বণ্টন
4. Linearity: E[T] = ∑_i=1ⁿ n/(n − i + 1). j = n − i + 1 বসালে j চলে n থেকে 1, তাই E[T] = n ∑_j=1ⁿ 1/j = n H_n. ∎ — উপপাদ্য ৪.১, index shift

এখানে T_i-গুলো আসলে স্বাধীনও, তবে প্রমাণে তা লাগেনি; প্রত্যাশার জন্য linearity-ই যথেষ্ট। প্রমাণের ভেতরের গল্পটি শিক্ষণীয়: প্রথম কয়েকটি নকশা খুব দ্রুত আসে, কিন্তু শেষ নকশাটির জন্য গড়ে পুরো n-টি অর্ডার অপেক্ষা করতে হয়, আর শেষের আগেরটির জন্য n/2. মোট সময়ের বড় অংশ যায় শেষ কয়েকটি নকশায়। নিচের stepper n = 4-এ ধাপগুলো দেখায়।

1ধাপ 1: নতুন 4/4 → গড় 12ধাপ 2: নতুন 3/4 → গড় 4/33ধাপ 3: নতুন 2/4 → গড় 24ধাপ 4: নতুন 1/4 → গড় 45মোট 25/3 = 4 · H₄ ≈ 8.33

এবার simulation: n = 4, 10, 50 আর 64 (বাংলাদেশের ৬৪ জেলার নামে ৬৪ রকম স্টিকার ধরুন), প্রতিটিতে ২,০০০ জন কাল্পনিক গ্রাহক।

import random
from fractions import Fraction

def H(n):
    return sum(Fraction(1, k) for k in range(1, n + 1))

def collect(n):                    # orders until all n sticker designs seen
    seen, orders = set(), 0
    while len(seen) < n:
        seen.add(random.randrange(n))
        orders += 1
    return orders

stages = [Fraction(4, 4 - i) for i in range(4)]
print("n = 4 stage waits:", [str(s) for s in stages], " sum =", sum(stages))

random.seed(40)
print("  n   n*H_n exact   simulated mean   min   max")
for n in (4, 10, 50, 64):
    runs = [collect(n) for _ in range(2000)]
    mean = sum(runs) / len(runs)
    print(f"{n:3d}   {float(n * H(n)):10.2f}   {mean:14.2f}   {min(runs):3d}   {max(runs):3d}")

n = 4 stage waits: ['1', '4/3', '2', '4']  sum = 25/3
  n   n*H_n exact   simulated mean   min   max
  4         8.33             8.23     4    36
 10        29.29            29.17    10    82
 50       224.96           225.95   100   583
 64       303.61           307.65   147   826

৭ · Randomized quicksort আর E[XY]-এর নিয়ম

Quicksort-এ তুলনার প্রত্যাশিত সংখ্যা

Randomized quicksort প্রতিটি ধাপে বর্তমান অংশ থেকে uniform এলোমেলোভাবে একটি pivot বাছে, বাকি প্রতিটি উপাদানকে pivot-এর সঙ্গে তুলনা করে ছোট আর বড় দুই দলে ভাগ করে, তারপর দুই দলে একই কাজ করে। কোড আর পূর্ণ আলোচনা DSA কোর্সের পর্ব ২২ আর পর্ব ৬১-এ আছে; এখানে শুধু গণিতের কাঠামোটি, যা পুরোপুরি indicator আর linearity.

প্রমাণের রূপরেখা: সাজানো ক্রমে key-গুলো z₁ < z₂ < … < z_n.

1. দুটি key কেবল তখনই তুলনা হয়, যখন একটি pivot; তুলনার পর pivot আর কোনো দলে থাকে না, তাই প্রতিটি জোড়া সর্বোচ্চ একবার তুলনা হয়। ফলে C = ∑_i<j X_ij, যেখানে X_ij হলো “z_i আর z_j তুলনা হলো”-এর indicator. — indicator-এ ভাঙা
2. Z_ij = {z_i, …, z_j}, মোট j − i + 1টি key. এই সেট থেকে কোনো pivot না বাছা পর্যন্ত সবগুলো একই দলে থাকে। প্রথম যে pivot এই সেট থেকে আসে, সেটি z_i বা z_j হলে দুজনের তুলনা হয়; মাঝের কেউ হলে দুজন আলাদা দলে চলে যায়, আর কখনো তুলনা হয় না। — ক্ষেত্রভাগ
3. প্রতিটি pivot বর্তমান অংশে uniform, আর বর্তমান অংশে পুরো Z_ij আছে; তাই Z_ij থেকে প্রথম বাছা key সেটের j − i + 1টির যেকোনোটি সমান সম্ভাবনায়। P(X_ij = 1) = 2/(j − i + 1). — প্রতিসাম্য
4. Linearity: E[C] = ∑_i<j 2/(j − i + 1). d = j − i ধরে সাজালে প্রতিটি d-এর n − d জোড়া, আর বীজগণিতে যোগফলটি 2(n + 1)H_n − 4n হয় (scratch-এ n ≤ 30-এ Fraction-এ মেলানো)। প্রতিটি i-এর ভেতরের যোগ 2(1/2 + … + 1/n) < 2H_n, তাই E[C] < 2nH_n. ∎

প্রত্যাশা এখানে অ্যালগরিদমের নিজের মুদ্রার ওপর, ইনপুটের ওপর নয়: সাজানো, উল্টো বা যেকোনো শত্রুতাপূর্ণ ইনপুটেই একই গড়। ধাপ ৩-এর প্রতিসাম্য যুক্তিটি নিচের ব্লকে n = 7-এ সব জোড়ার জন্য নিখুঁতভাবে হিসাব করে যাচাই করা হয়েছে, তারপর বড় n-এ simulation.

import random
from fractions import Fraction as Fr
from math import log

def H(n):
    return sum(Fr(1, k) for k in range(1, n + 1))

def p_compared(i, j, lo, hi):      # exact, ranks lo..hi still together
    total = Fr(0)
    for piv in range(lo, hi + 1):
        if piv in (i, j):
            total += 1
        elif piv < i:
            total += p_compared(i, j, piv + 1, hi)
        elif piv > j:
            total += p_compared(i, j, lo, piv - 1)
    return total / (hi - lo + 1)   # pivot strictly between: never compared

print("P(z_i, z_j compared) = 2/(j-i+1) for n = 7:",
      all(p_compared(i, j, 1, 7) == Fr(2, j - i + 1)
          for i in range(1, 8) for j in range(i + 1, 8)))

def compares(a):                   # randomized quicksort, distinct keys
    if len(a) <= 1:
        return 0
    pivot = random.choice(a)
    return (len(a) - 1 + compares([x for x in a if x < pivot])
            + compares([x for x in a if x > pivot]))

random.seed(40)
print("    n   exact E   simulated   2n ln n")
for n, runs in ((10, 2000), (100, 500), (1000, 100)):
    exact = float(2 * (n + 1) * H(n) - 4 * n)
    sim = sum(compares(list(range(n))) for _ in range(runs)) / runs
    print(f"{n:5d}  {exact:8.1f}  {sim:9.1f}  {2 * n * log(n):8.1f}")

P(z_i, z_j compared) = 2/(j-i+1) for n = 7: True
    n   exact E   simulated   2n ln n
   10      24.4       24.5      46.1
  100     647.9      646.3     921.0
 1000   10985.9    11014.4   13815.5

গুণের নিয়ম: E[XY] কখন E[X]E[Y]

দুটি random variable X, Y-কে independent (স্বাধীন) বলে, যদি সব x, y-এর জন্য P(X = x, Y = y) = P(X = x) P(Y = y). (Event-এর স্বাধীনতার পূর্ণ আলোচনা পর্ব ৩৯ “শর্তসাপেক্ষ সম্ভাবনা, independence আর Bayes-এর উপপাদ্য”-এ।)

প্রমাণ:

1. Ω-কে (X, Y)-এর মানজোড়া ধরে দলে ভাগ করলে E[XY] = ∑_{x, y} xy · P(X = x, Y = y); সংজ্ঞা ৩.১-এর মতো একই দলভাগ যুক্তি। — দলে ভাগ
2. স্বাধীনতায় = ∑_x ∑_y x P(X = x) · y P(Y = y). — স্বাধীনতার সংজ্ঞা
3. ভেতরের যোগে x P(X = x) ধ্রুবক, তাই = ∑_x x P(X = x) · (∑_y y P(Y = y)) = E[X] · E[Y]. Absolute convergence-এর জন্য একই হিসাব |x||y| দিয়ে করলে সসীম ফল আসে, তাই সাজানো বৈধ। ∎ — যোগফলের গুণনীয়ক বের করা

স্বাধীনতা ছাড়া এটি ভাঙে। একটি মুদ্রা ছুড়ে X = Y = head-এর indicator নিন। তখন XY = X² = X, তাই E[XY] = 1/2, অথচ E[X]E[Y] = 1/4. উল্টোটাও সত্য নয়: E[XY] = E[X]E[Y] হলেই চলক স্বাধীন হয় না। X যদি {−1, 0, 1}-এ uniform আর Y = X², তাহলে E[XY] = E[X³] = 0 = E[X] · E[Y], কিন্তু P(X = 0, Y = 0) = 1/3, যেখানে P(X = 0)P(Y = 0) = 1/9. Y পুরোপুরি X দিয়ে ঠিক হয়, তবু গুণের নিয়ম খেটে গেছে। এই ধরনের জোড়াকে বলে uncorrelated কিন্তু dependent; এর পরিমাপ covariance পর্ব ৪১-এর বিষয়।

৮ · পরীক্ষার অঙ্ক আর প্রত্যাশার একটি ভুল যুক্তি

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

অঙ্ক ১: লটে ত্রুটিপূর্ণ পণ্য (binomial)

একটি কারখানার প্রতিটি পণ্য স্বাধীনভাবে 1/10 সম্ভাবনায় ত্রুটিপূর্ণ। বাজারঘর ১২টির একটি বাক্স পায়। (ক) প্রত্যাশিত ত্রুটিপূর্ণ সংখ্যা, (খ) একটিও ত্রুটিপূর্ণ না থাকার সম্ভাবনা, (গ) সর্বোচ্চ একটি ত্রুটিপূর্ণ থাকার সম্ভাবনা কত?

1. X ~ Bin(12, 1/10), তাই E[X] = 12 × 1/10 = 1.2.
2. P(X = 0) = (9/10)¹² ≈ 0.2824.
3. P(X ≤ 1) = (9/10)¹² + 12 × (1/10) × (9/10)¹¹ ≈ 0.2824 + 0.3766 = 0.6590.

অঙ্ক ২: ফেরত না রেখে তোলা (স্বাধীনতা ছাড়া linearity)

২০টি পণ্যের একটি লটে ৪টি ত্রুটিপূর্ণ। মান-পরীক্ষক এলোমেলোভাবে, ফেরত না রেখে, ৫টি তোলেন। নমুনায় ত্রুটিপূর্ণের প্রত্যাশিত সংখ্যা কত?

1. I_k = “k-তম তোলা পণ্যটি ত্রুটিপূর্ণ”, k = 1, …, 5. প্রতিসাম্যে প্রতিটি তোলা আলাদাভাবে দেখলে ২০টির যেকোনোটি সমান সম্ভাবনায়, তাই P(I_k = 1) = 4/20 = 1/5.
2. I_k-গুলো স্বাধীন নয় (প্রথমটি ত্রুটিপূর্ণ হলে দ্বিতীয়টির সম্ভাবনা 3/19), কিন্তু linearity-তে লাগে না: E[X] = 5 × 1/5 = 1.
3. যাচাই: hypergeometric pmf C(4, k)C(16, 5 − k)/C(20, 5) ধরে ∑ k · P(X = k) হিসাব করলেও ঠিক 1. আর P(X = 0) = C(16, 5)/C(20, 5) = 4368/15504 ≈ 0.2817.

অঙ্ক ৩: দুটি ছক্কা

দুটি ছক্কা ছুড়লে (ক) যোগফলের প্রত্যাশা, (খ) বড়টির (M) pmf আর প্রত্যাশা কত?

1. (ক) Linearity: E[S] = 7/2 + 7/2 = 7. ৩৬টি ঘর গোনার দরকারই নেই।
2. (খ) M ≤ k মানে দুটি ছক্কাই ≤ k: P(M ≤ k) = k²/36, তাই P(M = k) = (k² − (k − 1)²)/36 = (2k − 1)/36, k = 1, …, 6.
3. E[M] = ∑ k(2k − 1)/36 = (1 + 6 + 15 + 28 + 45 + 66)/36 = 161/36 ≈ 4.47.

যুক্তির ভুল ধরুন: “গড় সময় জানলে গড় গতিও জানা”

একজন লিখলেন: “X ~ Geometric(1/2) হলো একটি কাজ শেষ হতে কয়টি চেষ্টা লাগে। E[X] = 2. প্রতি চেষ্টায় কাজের হার 1/X, তাই প্রত্যাশিত হার E[1/X] = 1/E[X] = 1/2. ∎” পড়ে ভুলটি নিজে খুঁজুন।

ভুল কোথায়: linearity শুধু রৈখিক ফাংশনের (aX + b) জন্য; 1/X রৈখিক নয়, তাই E[1/X] = 1/E[X] কোনো উপপাদ্য নয়। সংজ্ঞা ধরে হিসাব: E[1/X] = ∑_k≥1 (1/k)(1/2)^k = ln 2 ≈ 0.6931, যা 0.5 নয় (ধারাটি ln(1/(1 − x))-এর বিস্তার, x = 1/2; scratch-এ ৬০টি পদে মেলানো)। একই ধরনের ভুল E[X²] = (E[X])²: ছক্কায় E[X²] = 91/6 ≈ 15.17, অথচ (7/2)² = 12.25. পার্থক্যটিই পর্ব ৪১-এর variance. সাধারণ নিয়ম: অরৈখিক ফাংশন g-এর জন্য E[g(X)] = ∑ g(x) P(X = x) সংজ্ঞা থেকে হিসাব করুন; g(E[X]) বসিয়ে দেবেন না।

৯ · AI-এর যুগে — প্রত্যাশার হিসাব আর প্রমাণ যাচাই

প্রত্যাশার প্রশ্নে AI সহকারী প্রায়ই সুন্দর একটি সূত্র লিখে দেয়, কিন্তু ভুল লুকিয়ে থাকে শর্তে, রূপে বা একটি অসতর্ক “তাই”-তে। এই পর্বের বিষয়ে কয়েকটি ভুল নিয়মিত দেখা যায়:

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

• ছোট n-এ সব ফলাফল ধরে Fraction-এ নিখুঁত গড় হিসাব করে মিলিয়েছি
• Seed দেওয়া simulation চালিয়ে দেখেছি গড়টি কাছাকাছি আসে কি না
• প্রতিটি “স্বাধীন” দাবি সত্যি কি না, আর সেটি আদৌ দরকার কি না যাচাই করেছি
• কোনো অরৈখিক ফাংশনের প্রত্যাশা g(E[X]) দিয়ে বসানো হয়নি, দেখেছি
• অসীম যোগফল অভিসারী কি না, আর বণ্টনের কোন রূপ, তা মিলিয়েছি
• উদ্ধৃত ইতিহাস, সাল বা বইয়ের নাম বিশ্বস্ত উৎসে মিলিয়েছি

প্রত্যাশার দাবি পরীক্ষার সবচেয়ে সস্তা উপায় দুটি একসঙ্গে: ছোট ক্ষেত্রে নিখুঁত গণনা আর বড় ক্ষেত্রে seed দেওয়া simulation. দুটি মিললে আত্মবিশ্বাস বাড়ে; না মিললে প্রমাণের যে ধাপে স্বাধীনতা বা রৈখিকতা ধরে নেওয়া হয়েছে, সেখানেই প্রথমে খুঁজুন।