Probability — অনিশ্চয়তা নিয়ে হিসাব করা

আগে এটা বুঝি

Combinatorics বলে কতগুলো সম্ভাবনা আছে। কিন্তু engineering-এর আসল প্রশ্নগুলো একটু ভিন্ন:

Hash table-এ একটা lookup-এ গড়ে কতগুলো probe লাগবে?
Quicksort-এর প্রত্যাশিত running time কত?
৯৯.৯% uptime-এর তিনটা service চেইনে বসালে মোট uptime কত?
একটা load balancer কতটা অসম ভার তৈরি করবে?
আমার monitoring alert যখন বাজে, সত্যিই সমস্যা হওয়ার সম্ভাবনা কত?

শেষ প্রশ্নটার উত্তর অধিকাংশ প্রকৌশলী ভুল দেন — আর ভুলটা এত সাধারণ যে এর একটা নাম আছে: base rate fallacy।

Probability এমন একটা বিষয় যেখানে অন্তর্জ্ঞান নিয়মিতভাবে ব্যর্থ হয়। কিন্তু গণিতটা সরল, আর সেটা জানলে আপনি এমন সিদ্ধান্ত নিতে পারবেন যা বেশিরভাগ মানুষ পারে না।

মূল ধারণা

ভিত্তি — তিনটা জিনিস

Sample space Ω — সব সম্ভাব্য ফলাফলের set।

Event E ⊆ Ω — ফলাফলের একটা উপসেট।

Probability function P : events → [0,1] যা তিনটা নিয়ম মানে (Kolmogorov’s axioms):

১.  P(E) ≥ 0                              অ-ঋণাত্মক
২.  P(Ω) = 1                              মোট নিশ্চয়তা
৩.  E ∩ F = ∅  ⟹  P(E ∪ F) = P(E) + P(F)  বিচ্ছিন্ন হলে যোগ

Event মানে set — তাই set algebra সরাসরি খাটে

গত লেসনগুলোর কাজ এখানে ফল দেয়:

Logic	Set	Probability
`A ∧ B`	`A ∩ B`	“দুটোই ঘটে”
`A ∨ B`	`A ∪ B`	“অন্তত একটা ঘটে”
`¬A`	`A'`	`P(A') = 1 − P(A)`

আর inclusion–exclusion সরাসরি প্রযোজ্য:

$P(A \cup B) = P(A) + P(B) - P(A \cap B)$

নতুন কিছু শিখতে হচ্ছে না — শুধু একই কাঠামোয় সংখ্যা বসানো হচ্ছে।

সব ফলাফল সমসম্ভাব্য হলে (uniform), probability মানে শুধু গোনা:

$P(E) = \frac{|E|}{|\Omega|}$

তখন probability = combinatorics ÷ combinatorics। এই কারণেই গত লেসনটা আগে দরকার ছিল।

Conditional probability

B ঘটেছে জেনে A-এর সম্ভাবনা:

$P(A \mid B) = \frac{P(A \cap B)}{P(B)} \qquad (P(B) > 0)$

অন্তর্জ্ঞান: B ঘটেছে জানার পর আপনার sample space সংকুচিত হয়ে B হয়ে গেছে। এখন A-এর অনুপাত সেই ছোট জগতে মাপছেন।

আগে:                          B ঘটেছে জানার পর:

┌─────────── Ω ───────────┐    ┌──── B ────┐
│   ┌───A───┐             │    │  ┌─A∩B─┐  │
│   │  ┌────┼──B────┐     │    │  │     │  │
│   │  │A∩B │       │     │ →  │  │     │  │
│   └──┼────┘       │     │    │  └─────┘  │
│      └────────────┘     │    └───────────┘
└─────────────────────────┘
P(A) = |A|/|Ω|                 P(A|B) = |A∩B|/|B|

Conditioning মানে জগৎ ছোট করা — আর নতুন জগতে অনুপাত মাপা।

Multiplication rule (উল্টে লেখা):

$P(A \cap B) = P(A \mid B)\, P(B) = P(B \mid A)\, P(A)$

Independence

A আর B স্বাধীন যদি একটার ঘটা অন্যটার সম্ভাবনা বদলায় না:

$P(A \mid B) = P(A) \iff P(A \cap B) = P(A)\,P(B)$

Independence অনুমান করা সবচেয়ে সাধারণ ভুল

Engineering-এ আমরা প্রায়ই independence ধরে নিই কারণ তাতে হিসাব সহজ হয়। কিন্তু বাস্তবে জিনিসগুলো সম্পর্কিত থাকে।

উদাহরণ: তিনটা server, প্রতিটার ব্যর্থতার সম্ভাবনা ১%। সবগুলো একসাথে fail হওয়ার সম্ভাবনা?

Independent ধরলে: 0.01³ = 10⁻⁶ — দশ লক্ষে একবার।

কিন্তু যদি তিনটাই একই rack-এ থাকে, একই power supply-তে? তখন একটা power failure তিনটাকেই নেয়। প্রকৃত সম্ভাবনা হয়তো 0.005 — ৫০০০ গুণ বেশি।

২০১৭-র AWS S3 outage, ২০২১-এর Facebook outage — দুটোতেই “স্বাধীন” ধরে নেওয়া উপাদানগুলো একই সাধারণ কারণে একসাথে ব্যর্থ হয়েছিল।

এই কারণেই cloud provider-রা availability zone আলাদা রাখে — correlation ভাঙার জন্য, সংখ্যা বাড়ানোর জন্য নয়।

Bayes’ theorem

$P(A \mid B) = \frac{P(B \mid A)\, P(A)}{P(B)}$

Denominator সাধারণত law of total probability দিয়ে খোলা হয়:

$P(B) = P(B \mid A)P(A) + P(B \mid A')P(A')$

কেন এটা এত গুরুত্বপূর্ণ: এটা আপনাকে দিক উল্টাতে দেয়।

আপনি সাধারণত জানেন P(লক্ষণ | রোগ) — পরীক্ষার নির্ভুলতা। কিন্তু আপনার দরকার P(রোগ | লক্ষণ) — পরীক্ষা positive এলে সত্যিই রোগ থাকার সম্ভাবনা।

এই দুইটা সম্পূর্ণ আলাদা সংখ্যা, আর গুলিয়ে ফেলাটাই base rate fallacy।

ভেতরে কী ঘটছে

Base rate fallacy — একটা alert-এর গল্প

আপনার একটা monitoring system আছে:

সত্যিকারের সমস্যা হলে ৯৯% ক্ষেত্রে alert দেয় (true positive rate)
সমস্যা না থাকলে ১% ক্ষেত্রে ভুল alert দেয় (false positive rate)
বাস্তবে প্রতি ১০,০০০ চেকের মধ্যে ১ বার সত্যিকারের সমস্যা হয়

Alert বাজল। সত্যিই সমস্যা হওয়ার সম্ভাবনা কত?

অধিকাংশ মানুষ বলে “৯৯%”। সঠিক উত্তর ১% -এর নিচে।

হিসাব — ১০,০০,০০০ চেক কল্পনা করুন:

	সংখ্যা
সত্যিকারের সমস্যা	100
— এর মধ্যে alert বাজল (৯৯%)	99
সমস্যা নেই	999,900
— এর মধ্যে ভুল alert (১%)	9,999
মোট alert	10,098

$P(\text{সমস্যা} \mid \text{alert}) = \frac{99}{10{,}098} \approx 0.98\%$

১০০টা alert-এর মধ্যে ৯৯টা মিথ্যা।

Bayes দিয়ে একই হিসাব:

$P(S \mid A) = \frac{0.99 \times 0.0001}{0.99 \times 0.0001 + 0.01 \times 0.9999} = \frac{0.000099}{0.010098} \approx 0.0098$

এটাই alert fatigue-এর গাণিতিক মূল

Engineer-রা alert উপেক্ষা করতে শেখে — এবং সেটা যুক্তিসঙ্গত আচরণ, অলসতা নয়। যখন ৯৯% alert মিথ্যা, তখন প্রতিটা alert তদন্ত করা সময়ের অপচয়।

সমাধান “আরো শৃঙ্খলা” নয়। সমাধান গণিত বদলানো:

False positive rate কমান। ১% থেকে ০.০১%-এ নামালে precision ৫০% হয়ে যায় (৯৯টা সত্য বনাম ১০০টা মিথ্যা)।
Base rate বাড়ান। সবকিছুতে alert না দিয়ে শুধু উচ্চ-ঝুঁকির অবস্থায় দিন।
একাধিক সংকেত মিলান। স্বাধীন দুইটা সংকেত একসাথে হলে posterior অনেক বেড়ে যায়।
Symptom-এ alert দিন, cause-এ নয় — “user-facing latency বেড়েছে” (বিরল, গুরুত্বপূর্ণ) বনাম “CPU ৮০%” (সাধারণ, প্রায়ই নিরীহ)।

Google-এর SRE বই এই যুক্তিটাই দেয়, আর তাদের নিয়ম: প্রতিটা page-যোগ্য alert-কে actionable ও urgent হতে হবে।

একই গণিত প্রযোজ্য: spam filter, intrusion detection, চিকিৎসা পরীক্ষা, fraud detection, আর যেকোনো binary classifier-এ।

Machine learning-এ এটাকে বলা হয় precision:

$\text{precision} = \frac{TP}{TP + FP}$

আর সেই কারণেই imbalanced dataset-এ accuracy একটা অকেজো metric — ৯৯.৯৯% সমস্যা-মুক্ত হলে “সবসময় ‘সমস্যা নেই’ বলো” classifier-এর accuracy ৯৯.৯৯%।

Random variable ও expectation

একটা random variable X হলো একটা function Ω → ℝ — প্রতিটা ফলাফলকে একটা সংখ্যা দেয়।

Expectation (গড়):

$E[X] = \sum_{x} x \cdot P(X = x)$

Linearity of expectation — সবচেয়ে শক্তিশালী হাতিয়ার

$E[X + Y] = E[X] + E[Y]$

এটা সবসময় সত্য — X আর Y স্বাধীন না হলেও।

এই একটা বৈশিষ্ট্যই expectation-কে এত ব্যবহারযোগ্য করে, কারণ variance-এ এটা খাটে না (সেখানে independence লাগে)।

উদাহরণ ১ — hash table-এ collision সংখ্যা:

n টা key, m টা bucket, uniform hashing। প্রত্যাশিত colliding জোড়ার সংখ্যা?

প্রতিটা জোড়া (i,j)-এর জন্য একটা indicator:

$X_{ij} = \begin{cases} 1 & \text{যদি key } i \text{ ও } j \text{ একই bucket-এ} \\ 0 & \text{নাহলে}\end{cases}$

$E[X_{ij}] = P(\text{একই bucket}) = \frac{1}{m}$

মোট জোড়া C(n,2), তাই:

$E[\text{collision}] = \binom{n}{2} \cdot \frac{1}{m} = \frac{n(n-1)}{2m}$

n = 1000, m = 1000 হলে প্রায় ৫০০টা collision — যদিও load factor মাত্র ১.০!

এটাই birthday paradox, expectation-এর ভাষায়।

উদাহরণ ২ — coupon collector:

n ধরনের coupon, প্রতিবার একটা random। সব ধরন সংগ্রহ করতে প্রত্যাশিত কতবার লাগবে?

i ধরন ইতিমধ্যে থাকলে, নতুন একটা পাওয়ার সম্ভাবনা (n−i)/n। Geometric distribution অনুযায়ী প্রত্যাশিত অপেক্ষা n/(n−i)।

$E[T] = \sum_{i=0}^{n-1} \frac{n}{n-i} = n\sum_{k=1}^{n}\frac{1}{k} = n H_n \approx n \ln n$

n = 100 → প্রায় ৫১৯ বার।

CS-এ কোথায়: cache warming, random sampling-এ সব partition ছোঁয়া, distributed system-এ gossip protocol-এর convergence time।

Randomized quicksort

Quicksort-এর worst case O(n²) — যদি pivot সবসময় সবচেয়ে ছোট বা বড় হয়। Random pivot নিলে প্রত্যাশিত সময় O(n log n)।

প্রমাণ (indicator + linearity):

z₁ \< z₂ \< … \< zₙ sorted ক্রম। Indicator:

$X_{ij} = 1 \iff z_i \text{ ও } z_j \text{ কখনো তুলনা হয়}$

মোট তুলনা X = Σᵢ Σⱼ Xᵢⱼ।

মূল পর্যবেক্ষণ: zᵢ আর zⱼ তুলনা হয় কেবল যদি তাদের মধ্যকার {zᵢ, …, zⱼ} set থেকে প্রথম যে pivot বাছা হয় সেটা zᵢ বা zⱼ হয়।

কেন? যদি মাঝের কেউ আগে pivot হয়, তাহলে zᵢ আর zⱼ আলাদা partition-এ চলে যায় — আর কখনো তুলনা হবে না।

সেই set-এ j − i + 1 টা element, তার মধ্যে ২টা অনুকূল:

$P(X_{ij} = 1) = \frac{2}{j - i + 1}$

$E[X] = \sum_{i=1}^{n-1}\sum_{j=i+1}^{n} \frac{2}{j-i+1} \le \sum_{i=1}^{n} 2H_n \approx 2n\ln n$

অর্থাৎ O(n log n) প্রত্যাশিত ∎

Randomization কোথায় কোথায় সমস্যা সমাধান করে

Quicksort-এর pivotworst case input-নির্ভর নয় করে দেয়
Hash seed randomizationhash-flooding DoS আটকায়
Skip listbalanced tree-র সরল বিকল্প
Bloom filterসামান্য ভুলের বিনিময়ে বিশাল জায়গা সাশ্রয়
Load balancer-এর two choiceslog n → log log n
Exponential backoff + jitterretry storm ভাঙে
Consensus-এ random timeoutRaft-এ split vote ভাঙে

Variance ও tail bound

Expectation বলে গড় কত। কিন্তু কতটা বিচ্যুতি হতে পারে?

$\text{Var}[X] = E[(X - E[X])^2] = E[X^2] - (E[X])^2$

Markov’s inequality (শুধু অ-ঋণাত্মক X-এ):

$P(X \ge a) \le \frac{E[X]}{a}$

Chebyshev’s inequality:

$P(|X - E[X]| \ge k\sigma) \le \frac{1}{k^2}$

Chernoff bound (স্বাধীন indicator-দের যোগে) — অনেক শক্তিশালী, exponential decay:

$P(X \ge (1+\delta)\mu) \le e^{-\delta^2\mu/3}$

কেন tail bound গুরুত্বপূর্ণ

“গড়ে ১০০ ms” যথেষ্ট তথ্য নয়। ব্যবহারকারী p99 latency অনুভব করে।

একটা request যদি ১০টা service-এ যায়, আর প্রতিটার p99 = ১০০ ms, তাহলে অন্তত একটা ধীর হওয়ার সম্ভাবনা:

$1 - 0.99^{10} \approx 9.6\%$

অর্থাৎ ১০টা request-এর একটায় p99-স্তরের latency। এটাই “tail at scale” সমস্যা (Dean & Barroso-র বিখ্যাত পেপার)।

সমাধান: hedged request (একই request দুই জায়গায় পাঠিয়ে প্রথম উত্তর নেওয়া), যা tail নাটকীয়ভাবে কমায়। Level 9-এ দেখব।

উদাহরণ

Availability — কেন 9-গুলো গুণ হয়

তিনটা service চেইনে, প্রতিটার availability ৯৯.৯%:

$A_{\text{total}} = 0.999^3 = 0.997 = 99.7\%$

Availability	বছরে downtime
99%	3.65 দিন
99.9%	8.77 ঘণ্টা
99.99%	52.6 মিনিট
99.999%	5.26 মিনিট

তিনটা ৯৯.৯% service চেইনে = ৯৯.৭% = বছরে ২৬ ঘণ্টা downtime। প্রতিটা আলাদাভাবে ৮.৭৭ ঘণ্টা হলেও।

Redundancy উল্টো দিকে কাজ করে:

দুইটা সমান্তরাল service (একটা কাজ করলেই যথেষ্ট):

$A = 1 - (1 - 0.999)^2 = 1 - 10^{-6} = 99.9999\%$

দুইটা ৯৯.৯% থেকে ৯৯.৯৯৯৯% — তিনটা বাড়তি নাইন।

কিন্তু শুধু যদি ব্যর্থতাগুলো স্বাধীন হয়

উপরের হিসাবটা P(A ∩ B) = P(A)P(B) ধরে নিয়েছে।

বাস্তবে দুইটা replica প্রায়ই একই জিনিস ভাগ করে:

একই datacenter, একই power
একই software version — একই bug
একই deployment pipeline — একই খারাপ config
একই certificate — একই দিনে মেয়াদ শেষ

Correlated failure। ২০২১-এর Facebook outage-এ backbone router-এর একটা config change সব datacenter একসাথে বিচ্ছিন্ন করে দিয়েছিল — redundancy থাকা সত্ত্বেও, কারণ config সবখানে একই ছিল।

তাই প্রকৃত সূত্র:

$P(\text{দুটোই fail}) = P(A) \cdot P(B \mid A)$

আর P(B | A) প্রায়ই P(B)-এর চেয়ে অনেক বড়।

Engineering-এর উপসংহার: redundancy-র মূল্য নির্ভর করে correlation ভাঙার উপর — সংখ্যা বাড়ানোর উপর নয়। ভিন্ন AZ, ভিন্ন provider, staged rollout, ভিন্ন certificate — এগুলোই P(B|A) কমায়।

Load balancing — power of two choices

n টা ball, n টা bin-এ random ফেললে সবচেয়ে ভরা bin-এ প্রত্যাশিত কতগুলো?

$\Theta\!\left(\frac{\log n}{\log\log n}\right)$

n = 10⁶ হলে প্রায় ৬–৮টা — গড় ১ হলেও।

এখন একটা ছোট পরিবর্তন: দুইটা random bin দেখুন, কম ভরাটায় ফেলুন।

$\Theta(\log\log n)$

n = 10⁶ হলে প্রায় ৩টা।

log n / log log n থেকে log log n — নাটকীয় উন্নতি, শুধু একটা বাড়তি probe-এ।

কেন এত বড় পার্থক্য: একটা bin-কে খুব ভরা হতে হলে এখন পরপর অনেকবার “দুইটাই ভরা” ঘটতে হবে — সেই সম্ভাবনা দ্বিগুণ exponential হারে কমে।

বাস্তবে: NGINX-এর least_conn, Envoy-র default load balancer, আর বহু distributed cache ঠিক এই কৌশল ব্যবহার করে।

Bloom filter — সম্ভাবনার বিনিময়ে জায়গা

m bit, k টা hash function, n টা element।

একটা নির্দিষ্ট bit একটা নির্দিষ্ট hash দ্বারা সেট না হওয়ার সম্ভাবনা 1 − 1/m। n element × k hash পরে:

$P(\text{bit} = 0) = \left(1 - \frac{1}{m}\right)^{kn} \approx e^{-kn/m}$

False positive হয় যখন k টা bit-ই সেট পাওয়া যায়:

$P(\text{FP}) \approx \left(1 - e^{-kn/m}\right)^k$

Optimal k (calculus দিয়ে):

$k^* = \frac{m}{n}\ln 2 \implies P(\text{FP}) = 2^{-k^*} \approx 0.6185^{m/n}$

bit/element	optimal `k`	false positive
4	3	14.7%
8	6	2.16%
10	7	0.82%
16	11	0.046%
24	17	0.0025%

১০ bit প্রতি element-এ ০.৮% false positive — আর এটা element-এর আকার নির্বিশেষে। ১০০-byte string হোক বা ১ MB blob, ১০ bit।

তুলনায় একটা hash set-এ প্রতি element-এ কমপক্ষে ৬৪ bit (pointer)

ডেটা নিজে।

দাম: false positive সম্ভব (কখনো “আছে” বলবে যখন নেই), কিন্তু false negative কখনো নয়। আর element মুছে ফেলা যায় না।

ব্যবহার: Cassandra ও LevelDB-তে disk read এড়াতে, CDN-এ “এই URL কি কখনো দেখেছি”, browser-এ malicious URL তালিকা, আর spell checker-এ।

Level 8-এ আমরা Bloom filter নিজে বানাব।

নিজে চালিয়ে দেখুন

EXPERIMENT

Base rate fallacy — নিজে সংখ্যা দেখুন

Python 3· ১০ মিনিট

def bayes(prior, tpr, fpr):
    """
    prior : ঘটনাটা ঘটার আগাম সম্ভাবনা (base rate)
    tpr   : true positive rate  = P(alert | সমস্যা)
    fpr   : false positive rate = P(alert | সমস্যা নেই)
    """
    p_alert = tpr * prior + fpr * (1 - prior)
    return (tpr * prior) / p_alert if p_alert else 0.0


print(f"{'base rate':>12} {'TPR':>6} {'FPR':>7} {'P(সমস্যা|alert)':>18} {'মিথ্যা alert':>14}")
print("─" * 62)

scenarios = [
    ("সাধারণ সমস্যা",   0.10,    0.99, 0.01),
    ("মাঝারি",          0.01,    0.99, 0.01),
    ("বিরল",            0.001,   0.99, 0.01),
    ("খুব বিরল",        0.0001,  0.99, 0.01),
    ("বিরল, ভালো FPR",  0.0001,  0.99, 0.0001),
    ("বিরল, চমৎকার",    0.0001,  0.99, 0.00001),
]

for name, prior, tpr, fpr in scenarios:
    p = bayes(prior, tpr, fpr)
    print(f"{name:>12} {tpr:>6.2f} {fpr:>7.5f} {p:>17.2%} {1-p:>13.1%}")

Output:

   base rate    TPR     FPR    P(সমস্যা|alert)   মিথ্যা alert
──────────────────────────────────────────────────────────────
সাধারণ সমস্যা   0.99 0.01000            91.67%          8.3%
      মাঝারি   0.99 0.01000            50.00%         50.0%
        বিরল   0.99 0.01000             9.02%         91.0%
    খুব বিরল   0.99 0.01000             0.98%         99.0%
বিরল, ভালো FPR   0.99 0.00010            49.75%         50.2%
  বিরল, চমৎকার   0.99 0.00001            90.83%          9.2%

দুইটা লক্ষণীয় জিনিস:

১. TPR প্রায় অপ্রাসঙ্গিক। ৯৯% থেকে ১০০% করলেও বিশেষ পরিবর্তন হয় না।

২. FPR সবকিছু নির্ধারণ করে। ১% থেকে ০.০০১%-এ নামালে precision ১% থেকে ৯১% হয়ে যায়।

নিজে যাচাই করুন — TPR বদলে দেখুন:

print("\nTPR বদলালে (base rate 0.0001, FPR 0.01):")
for tpr in [0.80, 0.90, 0.99, 0.999, 1.0]:
    print(f"  TPR={tpr:.3f} → precision {bayes(0.0001, tpr, 0.01):.3%}")

print("\nFPR বদলালে (base rate 0.0001, TPR 0.99):")
for fpr in [0.01, 0.001, 0.0001, 0.00001]:
    print(f"  FPR={fpr:.5f} → precision {bayes(0.0001, 0.99, fpr):.2%}")

Engineering-এর উপসংহার: alert tuning-এ “আরো sensitive করি” প্রায় সবসময় ভুল দিক। Specific করা — অর্থাৎ FPR কমানো — একমাত্র কার্যকর পথ।

এটা কী প্রমাণ করে

একটা 99% নির্ভুল পরীক্ষা বিরল ঘটনার ক্ষেত্রে প্রায় সম্পূর্ণ অকেজো হতে পারে — আর alert threshold ঠিক করার সময় এই হিসাবটাই করতে হয়।

EXPERIMENT

Power of two choices — নিজে measure করুন

Python 3· ১৫ মিনিট

import random, math
from collections import Counter

def one_choice(n, m=None):
    """n টা ball, m টা bin-এ — প্রতিবার একটা random bin"""
    m = m or n
    bins = [0] * m
    for _ in range(n):
        bins[random.randrange(m)] += 1
    return max(bins)

def two_choices(n, m=None, d=2):
    """d টা random bin দেখে সবচেয়ে কম ভরাটায় ফেলুন"""
    m = m or n
    bins = [0] * m
    for _ in range(n):
        picks = [random.randrange(m) for _ in range(d)]
        best = min(picks, key=lambda i: bins[i])
        bins[best] += 1
    return max(bins)


print(f"{'n':>9} {'1 choice':>10} {'2 choices':>11} {'3 choices':>11} "
      f"{'log n/loglog n':>16} {'log log n':>11}")
print("─" * 74)

for n in [100, 1000, 10_000, 100_000, 1_000_000]:
    trials = 5 if n <= 100_000 else 2
    a = sum(one_choice(n)   for _ in range(trials)) / trials
    b = sum(two_choices(n)  for _ in range(trials)) / trials
    c = sum(two_choices(n, d=3) for _ in range(trials)) / trials
    ln = math.log(n)
    pred1 = ln / math.log(ln)
    pred2 = math.log(ln)
    print(f"{n:>9,} {a:>10.1f} {b:>11.1f} {c:>11.1f} {pred1:>16.1f} {pred2:>11.1f}")

সাধারণ ফলাফল:

        n   1 choice   2 choices   3 choices   log n/loglog n   log log n
──────────────────────────────────────────────────────────────────────────
      100        4.4         3.0         2.4              3.0         1.5
    1,000        5.4         3.0         3.0              3.7         1.9
   10,000        7.0         4.0         3.0              4.1         2.2
  100,000        8.2         4.0         3.0              4.5         2.4
1,000,000        9.4         4.0         3.0              4.7         2.6

লক্ষ্য করুন:

1 choice: n ১০ গুণ বাড়লে max প্রায় ১ করে বাড়ে (log-এর মতো)
2 choices: n ১০,০০০ গুণ বাড়লেও max প্রায় স্থির (৩→৪)
3 choices: আরো সামান্য ভালো, কিন্তু রিটার্ন কমে আসছে

শেষ পয়েন্টটা গুরুত্বপূর্ণ: d = 1 থেকে d = 2 -তে লাফ বিশাল, কিন্তু d = 2 থেকে d = 3 -তে সামান্য। তাই বাস্তবে প্রায় সবসময় d = 2 ব্যবহার হয় — সর্বোচ্চ লাভ, সর্বনিম্ন খরচ।

নিজে চেষ্টা করুন: load factor বদলে দেখুন (m = n/2, m = 2n) — pattern টিকে থাকে কি?

এটা কী প্রমাণ করে

একটা মাত্র বাড়তি random probe সবচেয়ে ভরা bin-এর load-কে log n / log log n থেকে log log n-এ নামায় — তাত্ত্বিক ফলটা কোডে সরাসরি দেখা যায়।

নিজে বানান

BUILD IT

Monte Carlo Toolkit

Python · ●●●○○

একটা সাধারণ simulation runner লিখুন যা confidence interval দেয়
Birthday, coupon collector আর quicksort — তত্ত্বের সাথে মেলান
Availability calculator বানান, correlation সহ
Bloom filter-এর false positive rate তাত্ত্বিক বনাম পরিমাপকৃত

import random, math, statistics
from collections import Counter


def monte_carlo(experiment, trials=20_000, confidence=0.95):
    """
    experiment: () -> float
    ফেরত দেয় mean আর confidence interval
    """
    samples = [experiment() for _ in range(trials)]
    mean = statistics.fmean(samples)
    if trials \< 2:
        return mean, 0.0
    stderr = statistics.stdev(samples) / math.sqrt(trials)
    z = 1.96 if confidence == 0.95 else 2.576
    return mean, z * stderr


def report(name, experiment, theory=None, trials=20_000):
    mean, ci = monte_carlo(experiment, trials)
    line = f"{name:<34} simulate = {mean:>10.4f} ± {ci:.4f}"
    if theory is not None:
        ok = abs(mean - theory) <= max(ci * 2, abs(theory) * 0.02)
        line += f"   theory = {theory:>10.4f}  {'মিলেছে' if ok else 'গরমিল'}"
    print(line)


# ── ১. Birthday ─────────────────────────────────────────────
def birthday_trial(k=23, space=365):
    seen = set()
    for _ in range(k):
        v = random.randrange(space)
        if v in seen: return 1.0
        seen.add(v)
    return 0.0

def birthday_theory(k=23, space=365):
    p = 1.0
    for i in range(k): p *= (space - i) / space
    return 1 - p

report("P(birthday collision, k=23)", birthday_trial, birthday_theory())


# ── ২. Coupon collector ─────────────────────────────────────
def coupon_trial(n=50):
    seen, draws = set(), 0
    while len(seen) \< n:
        seen.add(random.randrange(n)); draws += 1
    return draws

H = lambda n: sum(1/k for k in range(1, n+1))
report("Coupon collector, n=50", coupon_trial, 50 * H(50), trials=5000)


# ── ৩. Hash collision সংখ্যা ────────────────────────────────
def collision_trial(n=1000, m=1000):
    c = Counter(random.randrange(m) for _ in range(n))
    return sum(v * (v - 1) // 2 for v in c.values())

report("Colliding pairs (n=m=1000)", collision_trial,
       1000 * 999 / 2 / 1000, trials=2000)


# ── ৪. Randomized quicksort-এর তুলনা সংখ্যা ─────────────────
def qs_compares(a):
    if len(a) <= 1: return 0
    p = random.choice(a)
    lo = [x for x in a if x \< p]
    eq = [x for x in a if x == p]
    hi = [x for x in a if x > p]
    return (len(a) - 1) + qs_compares(lo) + qs_compares(hi)

def qs_trial(n=500):
    return qs_compares(list(range(n)))

report("Quicksort compares (n=500)", qs_trial, 2 * 500 * math.log(500),
       trials=400)


# ── ৫. Availability, correlation সহ ─────────────────────────
def availability(components, mode="series", correlation=0.0):
    """
    components : প্রতিটার availability-র list
    mode       : 'series' (সব লাগবে) বা 'parallel' (একটা হলেই হয়)
    correlation: 0 = স্বাধীন, 1 = সম্পূর্ণ সম্পর্কিত
    """
    if mode == "series":
        indep = math.prod(components)
        worst = min(components)               # সম্পূর্ণ সম্পর্কিত হলে
        return indep + correlation * (worst - indep)
    else:
        fail_indep = math.prod(1 - a for a in components)
        fail_worst = min(1 - a for a in components)
        fail = fail_indep + correlation * (fail_worst - fail_indep)
        return 1 - fail

def downtime(a):
    mins = (1 - a) * 365.25 * 24 * 60
    if mins \< 60:    return f"{mins:.1f} মিনিট/বছর"
    if mins \< 1440:  return f"{mins/60:.1f} ঘণ্টা/বছর"
    return f"{mins/1440:.1f} দিন/বছর"

print("\n── Availability " + "─" * 50)
three = [0.999] * 3
print(f"  চেইনে ৩টা (স্বাধীন)      : {availability(three):.6f}  {downtime(availability(three))}")
print(f"  সমান্তরাল ২টা (স্বাধীন)  : {availability([0.999]*2, 'parallel'):.6f}  "
      f"{downtime(availability([0.999]*2, 'parallel'))}")
print("\n  correlation বাড়লে সমান্তরাল redundancy কীভাবে ক্ষয় হয়:")
for c in [0.0, 0.1, 0.3, 0.5, 0.9, 1.0]:
    a = availability([0.999]*2, "parallel", correlation=c)
    print(f"    ρ={c:.1f} → {a:.6f}   {downtime(a)}")


# ── ৬. Bloom filter ─────────────────────────────────────────
class BloomFilter:
    def __init__(self, n, bits_per_element=10):
        self.m = n * bits_per_element
        self.k = max(1, round(bits_per_element * math.log(2)))
        self.bits = bytearray((self.m + 7) // 8)

    def _hashes(self, item):
        h1 = hash((item, 0x9E3779B9)) % self.m
        h2 = (hash((item, 0x85EBCA6B)) % (self.m - 1)) + 1
        return [(h1 + i * h2) % self.m for i in range(self.k)]

    def add(self, item):
        for h in self._hashes(item):
            self.bits[h >> 3] |= 1 \<\< (h & 7)

    def __contains__(self, item):
        return all(self.bits[h >> 3] >> (h & 7) & 1 for h in self._hashes(item))


print("\n── Bloom filter " + "─" * 50)
print(f"{'bits/elem':>10} {'k':>3} {'তাত্ত্বিক FP':>13} {'পরিমাপকৃত':>12}")
N = 20_000
for bpe in [4, 8, 10, 16]:
    bf = BloomFilter(N, bpe)
    for i in range(N): bf.add(f"present-{i}")
    fp = sum(1 for i in range(N) if f"absent-{i}" in bf) / N
    theory = (1 - math.exp(-bf.k * N / bf.m)) ** bf.k
    print(f"{bpe:>10} {bf.k:>3} {theory:>12.4%} {fp:>12.4%}")

নিজে বাড়ান:

report() -এ hypothesis test যোগ করুন — গরমিলটা কি statistically significant, নাকি শুধু noise?
Coupon collector-এর variance বের করুন এবং Chebyshev bound-এর সাথে তুলনা করুন
Bloom filter-এ counting variant যোগ করুন (delete সমর্থনের জন্য)
two_choices -এর সাথে consistent hashing তুলনা করুন
একটা retry simulator লিখুন — fixed backoff বনাম exponential বনাম exponential + jitter, আর thundering herd মাপুন

বাস্তব সিস্টেমে

Probability যেখানে সিদ্ধান্ত নেয়

Hash table-এর load factor। Java-র HashMap ০.৭৫-এ resize করে, Python-এর dict ০.৬৬-এ। এই সংখ্যাগুলো probability বিশ্লেষণ থেকে আসা — collision-এর প্রত্যাশিত সংখ্যা আর memory overhead-এর মধ্যে ভারসাম্য।

Exponential backoff with jitter। সব client একই সময়ে retry করলে thundering herd। AWS-এর “full jitter” সুপারিশ: sleep = random(0, min(cap, base × 2^attempt))। Random না থাকলে retry-গুলো সিঙ্ক্রোনাইজ হয়ে যায়।

Raft-এর election timeout। প্রতিটা node [150, 300] ms থেকে random timeout নেয়। Deterministic হলে সব node একসাথে candidate হয়ে split vote হতো, আর নির্বাচন কখনো শেষ হতো না। Randomization এখানে correctness-এর জন্য, performance-এর জন্য নয়।

Sampling-ভিত্তিক profiling। perf প্রতিটা instruction গোনে না — নির্দিষ্ট বিরতিতে stack sample নেয়। যথেষ্ট sample-এ বণ্টনটা সঠিক আসে, কিন্তু overhead ১০০ গুণ কম। Level 11-এ দেখব।

Distributed tracing-এর sampling। ১০০% trace রাখা ব্যয়বহুল। তাই head-based (১% request) বা tail-based (সব error + ধীর request) sampling। কোন কৌশল কখন — সেটা probability-র প্রশ্ন।

Cardinality estimation। HyperLogLog 1.5 KB-তে বিলিয়ন distinct element গুনতে পারে ~২% ত্রুটিতে। ভিত্তি: random hash-এর leading zero-র সর্বোচ্চ সংখ্যা distinct count-এর logarithm নির্দেশ করে। Redis-এর PFCOUNT এটাই।

Query planner-এর cost model। PostgreSQL histogram আর most-common-value তালিকা রেখে selectivity অনুমান করে। WHERE x = 5 কতগুলো row দেবে — সেটা একটা probability estimate, আর সেই estimate-এর ভুলই বেশিরভাগ খারাপ query plan-এর কারণ।

Chaos engineering। Netflix-এর Chaos Monkey random instance মেরে ফেলে। যুক্তি: correlated failure-এর সম্ভাবনা শূন্য নয়, তাই সেটা নিয়ন্ত্রিত পরিবেশে ঘটানো ভালো — production-এ আকস্মিকভাবে ঘটার চেয়ে।

A/B testing। দুইটা variant-এর পার্থক্য কি বাস্তব, নাকি random ওঠানামা? উত্তর দেয় hypothesis testing, আর ভুল বিশ্লেষণে (peeking, multiple comparison) ব্যাপক ভুল সিদ্ধান্ত হয়।

যে ভুলগুলো সবাই করে

“Random মানে uniform — সব সমানভাবে ছড়াবে।”

Random বণ্টন গুচ্ছ (clump) তৈরি করে — আর সেটাই স্বাভাবিক।

n টা ball n টা bin-এ ফেললে প্রত্যাশিত খালি bin:

$n\left(1 - \frac{1}{n}\right)^n \approx \frac{n}{e} \approx 0.37n$

৩৭% bin সম্পূর্ণ খালি থাকবে, যদিও গড়ে প্রতিটায় ১টা করে থাকার কথা।

এই কারণেই:

Spotify-র shuffle “random” ছিল, কিন্তু ব্যবহারকারীরা অভিযোগ করত একই শিল্পীর গান পরপর আসছে। Spotify শেষে কম random algorithm বানায় যা বেশি random মনে হয় — ইচ্ছাকৃতভাবে ছড়িয়ে দেয়।
Random load balancing অসম load তৈরি করে, তাই power-of-two choices বা consistent hashing লাগে।
“Random” test data প্রায়ই edge case ঢাকে না, কারণ গুচ্ছ হয়ে যায়।

Uniform distribution আর uniform outcome এক জিনিস নয়।

“৯৯% নির্ভুল পরীক্ষা মানে positive এলে ৯৯% নিশ্চিত।”

এটাই base rate fallacy, আর এটা প্রকৌশলী ও চিকিৎসক — দুই দলই নিয়মিত করেন।

P(alert | সমস্যা) আর P(সমস্যা | alert) সম্পূর্ণ আলাদা সংখ্যা।

দুইটার সম্পর্ক Bayes দিয়ে, আর সেখানে base rate নির্ধারক ভূমিকা রাখে।

একটা স্মরণীয় উপমা: “৯৯% নির্ভুল ভূমিকম্প ভবিষ্যদ্বাণী যন্ত্র” বানানো তুচ্ছ — শুধু সবসময় “ভূমিকম্প হবে না” বলুন। ভূমিকম্প বিরল, তাই আপনি ৯৯.৯% সময় ঠিক থাকবেন। কিন্তু যন্ত্রটা সম্পূর্ণ অকেজো।

সবসময় জিজ্ঞেস করুন: base rate কত?

“প্রত্যাশিত মান মানে 'সাধারণত যা হয়'।”

Expectation একটা গড়, আর গড় প্রায়ই অসম্ভব বা অপ্রতিনিধিত্বমূলক।

উদাহরণ ১: একটা ছক্কার প্রত্যাশিত মান ৩.৫ — যা কখনো ওঠে না।

উদাহরধ ২ — heavy tail: একটা service-এর latency distribution:

৯৯% request : ১০ ms
১%  request : ১০,০০০ ms
E[latency] = 0.99 × 10 + 0.01 × 10000 = 109.9 ms

গড় ১১০ ms, কিন্তু কোনো request-ই ১১০ ms নেয় না। ৯৯% নেয় ১০ ms, ১% নেয় ১০ সেকেন্ড।

এই কারণেই latency-তে গড় প্রায় অকেজো metric। p50, p95, p99, p999 দেখতে হয় — বণ্টনের আকারটা দেখতে হয়, একটা সংখ্যা নয়।

উদাহরণ ৩ — St. Petersburg paradox: একটা খেলার প্রত্যাশিত পুরস্কার অসীম, তবু কেউ বেশি টাকা দিয়ে খেলবে না। কারণ variance অসীম, আর প্রায় সব ক্ষেত্রেই পুরস্কার ছোট।

নিয়ম: expectation-এর পাশে সবসময় variance বা percentile দেখুন।

“স্বাধীন ঘটনার সম্ভাবনা গুণ করলেই হলো।”

সূত্রটা ঠিক — কিন্তু independence অনুমানটাই প্রায়ই ভুল।

$P(A \cap B) = P(A)P(B) \qquad \text{কেবল যদি স্বাধীন হয়}$

সাধারণ রূপ:

$P(A \cap B) = P(A) \cdot P(B \mid A)$

যেখানে এই ভুলটা ব্যয়বহুল হয়:

২০০৮-এর আর্থিক সংকট। Mortgage-backed security-র ঝুঁকি মডেলে ধরে নেওয়া হয়েছিল বিভিন্ন অঞ্চলের mortgage default স্বাধীন। বাস্তবে একটা জাতীয় মন্দা সবগুলোকে একসাথে টেনে নামায়। P(সব fail) অনুমান করা হয়েছিল প্রায় শূন্য; বাস্তবে হয়েছিল ~১।

RAID array। একই batch-এর ডিস্কগুলোর ব্যর্থতা সম্পর্কিত — একই উৎপাদন ত্রুটি, একই বয়স, একই তাপমাত্রা। তাই একটা ডিস্ক fail হওয়ার পর rebuild-এর সময় দ্বিতীয়টা fail হওয়ার সম্ভাবনা স্বাভাবিকের চেয়ে অনেক বেশি — আর সেটাই RAID-5 থেকে RAID-6-এ সরার কারণ।

Certificate expiry। সব service একই certificate ব্যবহার করলে, একদিনেই সব একসাথে ব্যর্থ হয়।

প্রশ্নটা সবসময় করুন: “এই দুইটা জিনিস কি কোনো সাধারণ কারণ ভাগ করে?” ভাগ করলে independence ভেঙে গেছে।

বুঝেছেন কি না দেখুন

আপনার service-এর p99 latency ১০০ ms। একটা user request ৫টা এমন service-এ যায় (sequential)। User-এর অন্তত একটা p99-স্তরের delay দেখার সম্ভাবনা কত?

প্রয়োগ

প্রতিটা service স্বাধীনভাবে ১% সম্ভাবনায় ধীর।

$P(\text{কোনোটাই ধীর নয়}) = 0.99^5 = 0.951$

$P(\text{অন্তত একটা ধীর}) = 1 - 0.951 = 4.9\%$

২০টা request-এর একটায় কেউ না কেউ p99-এ পড়ে।

সংখ্যাটা service সংখ্যার সাথে দ্রুত বাড়ে:

Services	P(অন্তত একটা p99)	কার্যকর percentile
1	1.0%	p99
5	4.9%	~p95
10	9.6%	~p90
50	39.5%	~p60
100	63.4%	~p37

১০০টা service-এ ৬৩% request কোনো না কোনো p99 hit করে।

এটাই Dean & Barroso-র “The Tail at Scale” পেপারের মূল বক্তব্য: scale-এ tail latency common case হয়ে যায়।

প্রশমনের কৌশল:

কৌশল	কীভাবে কাজ করে
Hedged request	৯৫তম percentile পার হলে দ্বিতীয় replica-তে পাঠান, প্রথম উত্তর নিন
Tied request	দুইটাতে একসাথে পাঠান, একটা শুরু করলে অন্যটা বাতিল
Parallel fan-out	sequential-এর বদলে সমান্তরাল — তখন `max` লাগে, `sum` নয়
Micro-partition	ছোট কাজে ভাগ করে ধীর node থেকে দ্রুত সরানো
Tail-tolerant design	সব উত্তরের অপেক্ষা না করে partial result

Hedged request-এর গণিত সুন্দর: p95-এ hedge করলে মাত্র ৫% বাড়তি load, কিন্তু p99 নাটকীয়ভাবে কমে — কারণ দুইটাই ধীর হওয়ার সম্ভাবনা 0.01 × 0.01 = 0.0001।

Google-এর রিপোর্ট অনুযায়ী এই কৌশলে তাদের একটা service-এ p99 ১৮০ ms থেকে ৭৪ ms-এ নেমেছিল, মাত্র ২% বাড়তি load-এ।

Linearity of expectation ব্যবহার করে বের করুন: n টা key m টা bucket-এ uniform hashing করলে প্রত্যাশিত খালি bucket সংখ্যা কত?

যুক্তি

Indicator: প্রতিটা bucket j-এর জন্য

$X_j = \begin{cases} 1 & \text{যদি bucket } j \text{ খালি} \\ 0 & \text{নাহলে}\end{cases}$

একটা নির্দিষ্ট key bucket j-তে না যাওয়ার সম্ভাবনা 1 − 1/m। n টা key স্বাধীনভাবে:

$E[X_j] = P(X_j = 1) = \left(1 - \frac{1}{m}\right)^n$

Linearity দিয়ে যোগ:

$E[\text{খালি}] = \sum_{j=1}^{m} E[X_j] = m\left(1 - \frac{1}{m}\right)^n$

n = m হলে:

$m\left(1 - \frac{1}{m}\right)^m \xrightarrow{m \to \infty} \frac{m}{e} \approx 0.368m$

৩৭% bucket খালি, যদিও load factor ঠিক ১।

সংখ্যা দিয়ে যাচাই:

`n/m`	খালি bucket
0.5	60.7%
1.0	36.8%
2.0	13.5%
3.0	5.0%

কেন এই হিসাব গুরুত্বপূর্ণ:

X_j-রা স্বাধীন নয় — একটা bucket খালি হলে অন্যগুলোয় বেশি key যায়। তবু linearity খাটে, কারণ linearity-র জন্য independence লাগে না।

Independence ধরে হিসাব করতে গেলে জটিল multinomial লাগত। Linearity দিয়ে দুই লাইনে হয়ে গেল।

ব্যবহারিক তাৎপর্য: এই ৩৭% খালি bucket মানে memory অপচয়। এই কারণেই hash table-এ:

Open addressing-এ load factor ০.৭-০.৯ রাখা হয় (কম অপচয়, কিন্তু clustering বাড়ে)
Chaining-এ ১.০ পর্যন্ত চলে (খালি bucket-এ শুধু একটা null pointer)
Robin Hood hashing বা cuckoo hashing দিয়ে আরো উঁচু load factor সম্ভব

Level 6-এ আমরা এই trade-off গুলো measure করব।

আপনার team চায় ৯৯.৯৯% availability। বর্তমান architecture-এ ৪টা component চেইনে, প্রতিটা ৯৯.৯%। কী করবেন?

ডিজাইন

বর্তমান অবস্থা:

$A = 0.999^4 = 0.996 = 99.6\%$

বছরে ৩৫ ঘণ্টা downtime। লক্ষ্য ৯৯.৯৯% = ৫২ মিনিট। ৪০ গুণ উন্নতি দরকার।

বিকল্প ১ — প্রতিটা component উন্নত করুন।

চেইনে ৪টা মিলে ৯৯.৯৯% পেতে প্রতিটার দরকার:

$A_{\text{each}} = 0.9999^{1/4} = 0.999975 = 99.9975\%$

বছরে ১৩ মিনিট প্রতি component। প্রায় অসম্ভব ব্যয়বহুল — ৯৯.৯ থেকে ৯৯.৯৯৭৫-এ যাওয়া মানে প্রতিটা component-এ তিনগুণ প্রকৌশল বিনিয়োগ।

বিকল্প ২ — Redundancy যোগ করুন।

প্রতিটা component-এর ২টা করে replica (স্বাধীন ধরে):

$A_{\text{pair}} = 1 - 0.001^2 = 0.999999$ $A_{\text{total}} = 0.999999^4 = 0.999996 = 99.9996\%$

লক্ষ্য অতিক্রম — বছরে ২ মিনিট।

বিকল্প ৩ — চেইন ছোট করুন।

৪টার বদলে ২টা component (দুইটা merge করে):

$0.999^2 = 0.998 = 99.8\%$

সাহায্য করে, কিন্তু যথেষ্ট নয়।

বিকল্প ৪ — graceful degradation।

কোন component গুলো সত্যিই critical? যদি একটা component ব্যর্থ হলে সীমিত সেবা দেওয়া যায়, তাহলে সেটা আর চেইনে নেই।

আগে:  A → B → C → D           সব লাগবে
পরে:  A → B → (C বা fallback) → D

প্রায়ই সবচেয়ে সস্তা ও কার্যকর পথ।

সুপারিশ — ২ ও ৪ একসাথে, কিন্তু correlation নিয়ে সতর্ক।

Redundancy-র হিসাবটা independence ধরে নিয়েছে। বাস্তবে নিশ্চিত করতে হবে:

প্রয়োজন	কেন
ভিন্ন availability zone	power/network correlation ভাঙে
Staged rollout	একই bug সবখানে একসাথে যাবে না
ভিন্ন certificate/মেয়াদ	একদিনে সব expire নয়
স্বাধীন monitoring	monitoring নিজেই SPOF নয়
Load balancer-ও redundant	নাহলে সেটাই নতুন SPOF

আর সবচেয়ে গুরুত্বপূর্ণ প্রশ্ন — dependency গুলো কি ধরা হয়েছে?

আপনার ৪টা component হয়তো একই database, একই DNS, একই auth service ব্যবহার করে। সেগুলোও চেইনে আছে, শুধু diagram-এ নেই।

বাস্তবতা যাচাই: ৯৯.৯৯% মানে সব কিছু মিলিয়ে ৫২ মিনিট — deployment, database migration, certificate rotation, cloud provider-এর নিজের outage সহ। AWS EC2-র SLA নিজেই ৯৯.৯৯%।

তাই প্রশ্নটা করা উচিত: ৯৯.৯৯% কি সত্যিই দরকার, নাকি ৯৯.৯% + দ্রুত recovery যথেষ্ট? MTTR কমানো প্রায়ই MTBF বাড়ানোর চেয়ে সস্তা।

Level 9 আর Level 12-এ আমরা এই নকশাগুলো বিস্তারিত দেখব।

একটা load balancer ১০০০ request ১০টা server-এ random বণ্টন করে। প্রত্যাশিত সর্বোচ্চ load কত, আর সেটা কি সমস্যা?

প্রয়োগ

প্রতিটা server-এ প্রত্যাশিত 1000/10 = 100 request।

প্রতিটা server-এর load একটা binomial random variable:

$X \sim \text{Binomial}(n=1000,\ p=0.1)$ $\mu = 100, \qquad \sigma = \sqrt{np(1-p)} = \sqrt{90} \approx 9.5$

Normal approximation-এ ১০টা server-এর সর্বোচ্চ প্রায় μ + 1.5σ থেকে μ + 2σ:

$\text{max} \approx 100 + 2 \times 9.5 \approx 119$

গড়ের চেয়ে প্রায় ২০% বেশি।

এটা কি সমস্যা?

সাধারণত না — ২০% imbalance বেশিরভাগ system সহ্য করে। তবে দুইটা ক্ষেত্রে সমস্যা:

১. Server যদি ক্ষমতার কাছাকাছি চলে। ১০০ request-এ যদি CPU ৮৫% হয়, তাহলে ১১৯-এ ১০০% — আর তখন latency exponentially বাড়ে (queueing theory)।

২. Request-এর খরচ অসম হলে। ১১৯টা request-এর মধ্যে যদি কয়েকটা ভারী হয়, তখন imbalance আরো বাড়ে।

Server সংখ্যা বাড়লে relative imbalance কমে:

$\frac{\sigma}{\mu} = \frac{\sqrt{np(1-p)}}{np} = \sqrt{\frac{1-p}{np}}$

Servers	Request/server	σ	relative
10	100	9.5	9.5%
100	10	3.0	30%
1000	1	1.0	100%

উল্টো ফল! Server বাড়লে relative imbalance বাড়ে, কারণ প্রতিটায় কম request।

এই কারণেই বড় fleet-এ pure random যথেষ্ট নয়।

ভালো বিকল্প:

কৌশল	সুবিধা	অসুবিধা
Round-robin	নিখুঁত ভারসাম্য	request খরচ অসম হলে ব্যর্থ
Least connections	প্রকৃত load দেখে	সব server-এর state জানতে হয়
Power of two choices	প্রায় নিখুঁত, সস্তা	২টা probe
Consistent hashing	cache locality রাখে	ভারসাম্য কম ভালো
+ bounded load	দুটোর সমন্বয়	জটিলতা

আগের experiment-এ দেখেছি power-of-two-choices-এ সর্বোচ্চ load প্রায় স্থির থাকে — এটাই বেশিরভাগ আধুনিক proxy-র default।

কেন Raft-এ election timeout random রাখা হয়? Deterministic হলে কী ভুল হতো?

যুক্তি

Deterministic timeout-এর সমস্যা — split vote-এর অসীম চক্র।

ধরুন সব node-এর timeout ঠিক ১৫০ ms। Leader fail করল।

t = 150ms : সব node একসাথে timeout করল
            সব node candidate হলো
            সব node নিজেকে ভোট দিল
            কেউ majority পেল না  →  split vote
t = 300ms : সব node আবার একসাথে timeout
            আবার split vote
...অসীম পুনরাবৃত্তি

Cluster চিরকাল leaderless থাকতে পারে। এটা তাত্ত্বিক সমস্যা নয় — symmetric protocol-এ এটা বাস্তবেই ঘটে।

Random timeout কীভাবে ভাঙে:

প্রতিটা node [150, 300] ms থেকে uniform random বাছে।

প্রথম যে node timeout করে সে candidate হয়, ভোট চায়, আর সাধারণত অন্যরা তখনো timeout করেনি — তাই তারা ভোট দেয়।

দুইটা node প্রায় একসাথে timeout করার সম্ভাবনা:

RPC round trip ~10 ms ধরলে, দুইটা node-এর timeout 10 ms-এর মধ্যে পড়ার সম্ভাবনা প্রায় 10/150 ≈ 6.7%।

তাই ~৯৩% ক্ষেত্রে প্রথম চেষ্টাতেই leader নির্বাচিত হয়। Split vote হলেও পরের রাউন্ডে আবার random — তাই ব্যর্থতার সম্ভাবনা exponentially কমে:

$P(\text{k রাউন্ডে ব্যর্থ}) \approx 0.067^k$

৩ রাউন্ডে 3 × 10⁻⁴।

Randomization symmetry ভাঙে

এটা randomization-এর একটা গভীর ব্যবহার: symmetric অবস্থা ভাঙা।

Deterministic distributed algorithm-এ symmetric configuration থেকে বেরোনো প্রায়ই অসম্ভব — সব node একই কোড চালাচ্ছে, একই তথ্য দেখছে, তাই একই সিদ্ধান্ত নেবে।

Randomness হলো একমাত্র জিনিস যা তাদের আলাদা করে।

আরো মৌলিক একটা ফল আছে: FLP impossibility theorem (১৯৮৫) প্রমাণ করে যে asynchronous system-এ একটাও node fail করতে পারলে কোনো deterministic consensus algorithm সবসময় termination নিশ্চিত করতে পারে না।

Raft সেই সীমা অতিক্রম করে randomization দিয়ে — safety সবসময় রক্ষা করে (কখনো দুইটা leader নয়), কিন্তু liveness শুধু probabilistic (প্রায় নিশ্চিতভাবে একটা leader হবে, কিন্তু নির্দিষ্ট সময়সীমা নেই)।

Timeout range নির্বাচনের নিয়ম:

$\text{broadcastTime} \ll \text{electionTimeout} \ll \text{MTBF}$

খুব ছোট হলে: অপ্রয়োজনীয় নির্বাচন, leader বারবার বদলায়
খুব বড় হলে: leader fail করলে দীর্ঘ downtime
Range খুব সরু হলে: split vote বাড়ে

Raft পেপারের সুপারিশ: 150–300 ms, যেখানে RPC latency 0.5–20 ms।

Level 9-এ আমরা Raft implement করব এবং এই timeout গুলো নিয়ে পরীক্ষা করব।

এরপর কী

Probability দিয়ে আমরা অনিশ্চয়তা নিয়ে হিসাব করতে শিখলাম।

পরের লেসনে graph theory — এই কারিকুলামের সবচেয়ে বেশি ব্যবহৃত গাণিতিক কাঠামো। Relation-এর লেসনে আমরা graph-এর স্বাদ পেয়েছি; এবার পুরোটা: path, cycle, tree, connectivity, bipartite, planar, coloring।

Network topology, dependency, compiler-এর control flow, filesystem, social network, distributed system — সব জায়গায় graph। আর সেই সাথে আসবে BFS, DFS, shortest path আর MST-র গাণিতিক ভিত্তি, যা Level 6-এ algorithm হিসেবে ফিরে আসবে।

Probability — অনিশ্চয়তা নিয়ে হিসাব করা

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

মূল ধারণা

ভিত্তি — তিনটা জিনিস

Conditional probability

Independence

Bayes’ theorem

ভেতরে কী ঘটছে

Base rate fallacy — একটা alert-এর গল্প

Random variable ও expectation

Linearity of expectation — সবচেয়ে শক্তিশালী হাতিয়ার

Randomized quicksort

Variance ও tail bound

উদাহরণ

Availability — কেন 9-গুলো গুণ হয়

Load balancing — power of two choices

Bloom filter — সম্ভাবনার বিনিময়ে জায়গা

নিজে চালিয়ে দেখুন

Base rate fallacy — নিজে সংখ্যা দেখুন

Power of two choices — নিজে measure করুন

নিজে বানান

Monte Carlo Toolkit

বাস্তব সিস্টেমে

Probability যেখানে সিদ্ধান্ত নেয়

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী

আরও পড়ুন

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

◔আগে এটা বুঝিWhy this matters

◆মূল ধারণাCore concept

ভিত্তি — তিনটা জিনিস

Conditional probability

Independence

Bayes’ theorem

⚙ভেতরে কী ঘটছেUnder the hood

Base rate fallacy — একটা alert-এর গল্প

Random variable ও expectation

Linearity of expectation — সবচেয়ে শক্তিশালী হাতিয়ার

Randomized quicksort

Variance ও tail bound

▶উদাহরণExample

Availability — কেন 9-গুলো গুণ হয়

Load balancing — power of two choices

Bloom filter — সম্ভাবনার বিনিময়ে জায়গা

⌘নিজে চালিয়ে দেখুনExperiment

Base rate fallacy — নিজে সংখ্যা দেখুন

Power of two choices — নিজে measure করুন

⚒নিজে বানানBuild it yourself

Monte Carlo Toolkit

◉বাস্তব সিস্টেমেReal-world usage

Probability যেখানে সিদ্ধান্ত নেয়

⚠যে ভুলগুলো সবাই করেMisconceptions

?বুঝেছেন কি না দেখুনCheck understanding

→এরপর কীNext step

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

ভেতরে কী ঘটছে

উদাহরণ

নিজে চালিয়ে দেখুন

নিজে বানান

বাস্তব সিস্টেমে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী