144 — Expected Value Problems¶

Probability জোড়ার প্রথমটা — আর এটাই সম্ভবত এই level-এর সবচেয়ে interview-আত্মীয় idea (probability question-এ linearity of expectation একটা common pattern)। মূল চমক: expectation যোগে ভাঙা যায়, ঘটনাগুলো পরস্পর-নির্ভর হলেও! মনে রাখো, এই level সামগ্রিকভাবে CP-leaning, interview-এর জন্য optional (repo-র plan অনুযায়ী) — তবে এই একটা idea ব্যতিক্রম, কাজে লাগবে।

Source¶

Original source: Classic probability — linearity of expectation (dice, coupon collector)
Platform: Classic probability (related practice: USACO Guide — https://usaco.guide/)
Topic: Math-based programming fundamentals → Level 11: Hard Mixed CP Patterns
Difficulty: Medium
Pattern: linearity of expectation (ভাঙো-যোগ করো)
Basic idea inherited from: 052 (probability basics)

1. Problem in simple words¶

"Expected value" মানে গড়ে কত — যদি একটা random পরীক্ষা বহুবার চালাও, ফলাফলের গড় কত হবে। দুটো classic প্রশ্ন দিয়ে শিখব:

Dice: দুটো ন্যায্য ছক্কা একসাথে ফেললে যোগফলের গড় কত? (উত্তর 7)
Coupon collector: n রকম আলাদা coupon, প্রতিবার uniformly random একটা পাও — সব কয়টা জোগাড় করতে গড়ে কতবার নিতে হবে? (n = 4 হলে গড়ে 8.33 বার)

দেখতে আলাদা, কিন্তু দুটোরই সমাধান একই অস্ত্রে: linearity of expectation — মোট প্রশ্নকে ছোট টুকরোয় ভেঙে প্রতিটার গড় আলাদা বের করে যোগ করা।

Interview-পথে থাকলেও এই idea-টা শিখে রাখো; বাকি CP-material পরে।

2. What is the math idea?¶

মূল ধারণা linearity of expectation:

E[X + Y] = E[X] + E[Y]      — সবসময়, এমনকি X, Y dependent হলেও!
E[X1 + X2 + ... + Xn] = E[X1] + E[X2] + ... + E[Xn]

এটাই probability-র সবচেয়ে underrated অস্ত্র। সাধারণত যোগফলের distribution বের করা কঠিন (convolution লাগে), কিন্তু expectation-এ সেই কষ্ট নেই — শুধু প্রতিটা অংশের গড় আলাদা বের করে যোগ করো। আর সবচেয়ে বড় কথা — অংশগুলো পরস্পর-নির্ভর হলেও সূত্রটা খাটে। এটাই অনেক জটিল-দেখতে probability problem-কে এক লাইনে মিটিয়ে দেয়।

3. Which basic idea does this inherit from?¶

দাঁড়িয়ে আছে probability basics (problem 052)-এর উপর — যেখানে শিখেছিলে একটা ঘটনার সম্ভাবনা, আর expectation-এর সংজ্ঞা (E[X] = Σ মান × সম্ভাবনা)।

নতুন যেটা যোগ হলো: সেই সংজ্ঞা সরাসরি না খাটিয়ে ভেঙে-যোগ করার কৌশল। 052-এ একটা random variable-এর গড় বের করতে; এখানে একটা জটিল random variable-কে সরল indicator/ধাপের যোগফল হিসেবে লিখে প্রতিটার গড় আলাদা বের করি। এই "ভাঙো-যোগ করো" চিন্তাই পরের problem 145 (probability DP)-এর সাথে জোড়া — যেখানে ভাঙা সরাসরি না গেলে DP লাগে।

4. Real-life analogy¶

ভাবো তুমি একটা দীর্ঘ road trip-এর মোট খরচ গড়ে কত হবে জানতে চাও। পুরো trip-এর খরচ একসাথে অনুমান করা কঠিন; কিন্তু তুমি ভাঙো — তেল গড়ে কত, খাবার গড়ে কত, টোল গড়ে কত — প্রতিটার গড় আলাদা বের করে যোগ করো। মোট গড় খরচ = অংশগুলোর গড়ের যোগফল।

মজার ব্যাপার — তেল আর খাবারের খরচ পরস্পর-নির্ভর হতে পারে (বেশি চালালে দুটোই বাড়ে), কিন্তু গড় যোগ করতে এতে কিছু আসে যায় না। ঠিক তেমনি, যত জটিল random ফলাফলই হোক, তাকে সরল টুকরোয় ভেঙে প্রতিটার গড় যোগ করলেই মোট গড় — dependence নিয়ে মাথা ঘামানোর দরকার নেই।

5. Visual explanation¶

Coupon collector-এ মোট draw-কে ধাপে ভাঙা:

n = 4 coupon — কত draw-এ সব জোগাড়?

ধাপ T_k = (k-1)টা পাওয়ার পর k-তম নতুন coupon পেতে কত draw

T_1: হাতে 0, যেকোনোটাই নতুন   ->  নতুন পাওয়ার সম্ভাবনা 4/4 = 1     -> E = 1
T_2: হাতে 1, নতুন চাই 3টার এক ->  সম্ভাবনা 3/4               -> E = 4/3
T_3: হাতে 2, নতুন চাই 2টার এক ->  সম্ভাবনা 2/4               -> E = 4/2 = 2
T_4: হাতে 3, নতুন চাই 1টা     ->  সম্ভাবনা 1/4               -> E = 4/1 = 4

মোট E = E[T_1] + E[T_2] + E[T_3] + E[T_4]
      = 1 + 4/3 + 2 + 4 = 8.333...

(প্রতিটা T_k হলো geometric: সম্ভাবনা p হলে গড় 1/p)

লক্ষ করো — পুরো প্রক্রিয়ার জটিল distribution লাগল না; শুধু 4টা সরল গড় যোগ করলাম।

6. Example input and output¶

সমস্যা                          উত্তর       কীভাবে
----------------------------------------------------------------
1টা ছক্কার গড়                   3.5         (1+2+3+4+5+6)/6
2টা ছক্কার যোগফলের গড়           7.0         3.5 + 3.5 (linearity)
3টা ছক্কার যোগফলের গড়           10.5        3 × 3.5
coupon collector n = 2          3.0         2·(1 + 1/2)
coupon collector n = 4          8.333...    4·(1 + 1/2 + 1/3 + 1/4)

মূল sanity check: coupon collector n = 2 → প্রথম draw-এ নতুন নিশ্চিত (1 draw), তারপর দ্বিতীয়টা পেতে গড়ে 2 draw — মোট 3। হাতে মেলে।

7. Brute force thinking¶

Linearity না জানলে — সরাসরি simulation (Monte Carlo): বহুবার পরীক্ষা চালিয়ে ফলাফলের গড় নাও।

import random


def coupon_collector_sim(n, trials=200000):
    total = 0
    for _ in range(trials):
        seen = set()
        draws = 0
        while len(seen) < n:
            seen.add(random.randrange(n))
            draws += 1
        total += draws
    return total / trials

এটা মোটামুটি ঠিক উত্তরের কাছাকাছি দেয় (n=4-এ ~8.33), আর আমাদের সূত্র যাচাইয়ের ভালো মাপকাঠি। কিন্তু এটা শুধুই আনুমানিক — নিখুঁত নয়।

8. Why brute force may be slow¶

Simulation-এর দুটো সমস্যা — ধীর আর অনিখুঁত:

trials = 1000     ->  দ্রুত, কিন্তু উত্তর অস্থির (±0.2 এদিক-ওদিক)
trials = 10^7     ->  নিখুঁত হতে থাকে, কিন্তু ধীর
নিখুঁত উত্তর      ->  simulation দিয়ে কখনো ঠিক 8.333... পাবে না

প্রতিটা trial-এ আবার ভেতরে loop (সব coupon না পাওয়া পর্যন্ত)। মূল সমস্যা — আমরা একটা আনুমানিক উত্তরের জন্য বিশাল compute খরচ করছি, অথচ linearity দিয়ে নিখুঁত উত্তর এক লাইনে পাওয়া যায়।

9. Better thinking¶

মূল insight: মোট random পরিমাণকে সরল টুকরোর যোগফল হিসেবে লেখো, প্রতিটার গড় আলাদা বের করো, যোগ করো।

Dice: সব ছক্কার যোগফল = X₁ + X₂ + ...; প্রতিটা E[Xᵢ] = 3.5, তাই মোট = 3.5 × ছক্কার সংখ্যা। (ছক্কাগুলো independent লাগেও না, যদিও এখানে আছে।)
Coupon collector: মোট draw = T₁ + T₂ + ... + Tₙ, যেখানে Tₖ = (k−1)টা পাওয়ার পর নতুন একটা পেতে draw। নতুন পাওয়ার সম্ভাবনা p = (n−k+1)/n, তাই E[Tₖ] = n/(n−k+1) (geometric)। যোগ করলে n·(1 + 1/2 + ... + 1/n)।

কোনো distribution নয়, কোনো simulation নয় — শুধু গড়ের যোগ।

10. Thinking tweak¶

এক লাইনের "আহা": "মোট/গড় কত" প্রশ্ন দেখলেই ভাবো — এটাকে কি সরল টুকরোর যোগফল হিসেবে লেখা যায়? পারলে প্রতিটার গড় আলাদা নাও আর যোগ করো; dependence নিয়ে মাথাই ঘামিও না।

সবচেয়ে বড় ফাঁদ: linearity-র জন্য independence খোঁজা (concept-notes mistake #6)। অনেকে ভাবে "ঘটনাগুলো independent না, তাই যোগ করা যাবে না" — ভুল! E[X+Y] = E[X]+E[Y] সবসময় সত্য। এই ভুল ভেবে সহজ problem-কে কঠিন বানিয়ে ফেলা খুব common।

11. Step-by-step dry run¶

Coupon collector n = 3 হাতে চালাই (linearity দিয়ে):

ভাঙা: মোট draw = T₁ + T₂ + T₃।
T₁: হাতে 0 coupon, যেকোনোটাই নতুন → সম্ভাবনা 3/3 = 1 → E[T₁] = 1/1 = 1।
T₂: হাতে 1 coupon, নতুন চাই বাকি 2টার একটা → সম্ভাবনা 2/3 → E[T₂] = 3/2 = 1.5।
T₃: হাতে 2 coupon, নতুন চাই বাকি 1টা → সম্ভাবনা 1/3 → E[T₃] = 3/1 = 3।
যোগ: E[মোট] = 1 + 1.5 + 3 = 5.5। (= 3·(1 + 1/2 + 1/3) = 3 × 1.8333 = 5.5 ✓)।

12. Python solution¶

def dice_sum_expectation(num_dice, faces=6):
    """num_dice টা faces-মুখী ন্যায্য ছক্কার যোগফলের expected value।"""
    single = (faces + 1) / 2              # এক ছক্কার গড়
    return num_dice * single              # linearity: শুধু গুণ


def coupon_collector(n):
    """n রকম coupon সব জোগাড় করতে গড়ে কত draw — linearity-তে।"""
    # মোট = Σ T_k, E[T_k] = n / (n - k + 1)
    return sum(n / (n - k + 1) for k in range(1, n + 1))


# --- যাচাইয়ের জন্য নিখুঁত DP (linearity ছাড়া অন্য পথে) ---
def coupon_collector_exact_dp(n):
    """E_k = k distinct থেকে n distinct-এ যেতে গড় draw; recurrence দিয়ে।"""
    E = [0.0] * (n + 1)
    for k in range(n - 1, -1, -1):
        # E_k = 1 + (k/n)·E_k + ((n-k)/n)·E_{k+1}  =>  সমাধান করে:
        E[k] = (1 + (n - k) / n * E[k + 1]) / ((n - k) / n)
    return E[0]


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert dice_sum_expectation(1) == 3.5
assert dice_sum_expectation(2) == 7.0           # linearity: 3.5 + 3.5
assert dice_sum_expectation(3) == 10.5

assert abs(coupon_collector(2) - 3.0) < 1e-9    # 2·(1 + 1/2)
assert abs(coupon_collector(4) - 8.3333333) < 1e-6

# linearity-র উত্তর আর স্বাধীন DP-র উত্তর মেলে (দুই পথ এক গন্তব্য)
for n in range(1, 8):
    assert abs(coupon_collector(n) - coupon_collector_exact_dp(n)) < 1e-9, n

# coupon_collector(n) = n·H_n যাচাই (harmonic)
def harmonic(n):
    return sum(1 / i for i in range(1, n + 1))
for n in range(1, 8):
    assert abs(coupon_collector(n) - n * harmonic(n)) < 1e-9, n

print(dice_sum_expectation(2))          # 7.0
print(round(coupon_collector(4), 4))    # 8.3333
print(round(coupon_collector(3), 4))    # 5.5
print("সব test pass!")

13. Line-by-line explanation¶

    single = (faces + 1) / 2
    return num_dice * single

এক ন্যায্য ছক্কার গড় (1+2+...+6)/6 = 3.5, বা সাধারণভাবে (faces+1)/2। Linearity-র দরুন num_diceটা ছক্কার যোগফলের গড় শুধু এই গড়কে গুণ করলেই পাওয়া যায় — convolution লাগে না।

    return sum(n / (n - k + 1) for k in range(1, n + 1))

Coupon collector-এর হৃদয়। k-তম নতুন coupon পেতে geometric, সম্ভাবনা (n−k+1)/n, গড় তার উল্টো n/(n−k+1)। সব k-এর জন্য যোগ করি — এটাই n·(1 + 1/2 + ... + 1/n)।

def coupon_collector_exact_dp(n):
    E[k] = (1 + (n - k) / n * E[k + 1]) / ((n - k) / n)

স্বাধীন যাচাই — E_k = 1 + (k/n)E_k + ((n-k)/n)E_{k+1} recurrence সমাধান করে (এক draw সবসময়, k/n সম্ভাবনায় একই state-এ ফেরা, (n-k)/n সম্ভাবনায় এগোনো)। linearity-র সূত্র ঠিক কিনা এ দিয়ে মিলিয়ে দেখি।

বাকি assert গুলো তিনভাবে যাচাই: (১) dice/coupon-এর জানা মান, (২) linearity vs স্বাধীন DP, (৩) n·Hₙ সূত্র। সব মিললে সব test pass!।

14. Output walkthrough¶

চালালে ছাপবে:

7.0
8.3333
5.5
সব test pass!

প্রথম লাইন 2টা ছক্কার যোগফলের গড় → 7.0 (3.5+3.5)। দ্বিতীয় coupon collector n=4 → 8.3333। তৃতীয় n=3 → 5.5 (dry run-এর মান)। তার আগের সব assert চুপচাপ pass করেছে — linearity-র উত্তর স্বাধীন DP আর n·Hₙ-এর সাথে হুবহু মেলে। সবশেষে সব test pass!।

15. Time complexity¶

Dice: O(1) — শুধু একটা গুণ। Coupon collector: O(n) — nটা ধাপের গড় যোগ করা। simulation ছিল O(trials × n) আর তাও আনুমানিক; linearity নিখুঁত উত্তর O(n)-এ।

16. Space complexity¶

O(1) — দুটো সূত্রেই গুটিকয় variable, কোনো array লাগে না (যোগফল চলতে চলতে জমে)। যাচাইয়ের DP O(n) নেয়, কিন্তু আসল সমাধান O(1)।

17. Common mistakes¶

Independence খোঁজা — linearity-র জন্য independence লাগে না; এটা ভুলে সহজ problem কঠিন বানানো খুব common (concept-notes mistake #6)।
যোগফলের distribution বের করতে যাওয়া — গড় চাইলে distribution লাগে না; সরাসরি E যোগ করো।
Geometric-এর গড় ভুল — সম্ভাবনা p-এর geometric-এর গড় 1/p; উল্টে p ভাবলে coupon collector ভুল।
Coupon collector-এ index উল্টে ফেলা — k-তম নতুন পেতে সম্ভাবনা (n−k+1)/n (যত বেশি পেয়েছ, নতুন পাওয়া তত কঠিন)।
Simulation-কে নিখুঁত ভাবা — Monte Carlo সবসময় আনুমানিক; নিখুঁত উত্তর চাইলে সূত্র লাগবে।

18. Harder problems that inherit this idea¶

USACO Guide — Expected Value (https://usaco.guide/) — linearity-র নানা প্রয়োগ ও অনুশীলন।
Codeforces — probabilities / expected value tag (https://codeforces.com/problemset?tags=probabilities) — indicator-ভাঙার নানা problem।
LeetCode — Soup Servings (https://leetcode.com/problems/soup-servings/) — expectation/probability চিন্তা (যদিও DP-ঘেঁষা — 145-এর সেতু)।

19. Pattern learned¶

Linearity of expectation — E[X+Y] = E[X]+E[Y] সবসময় (dependence লাগে না)। "মোট/গড় কত" প্রশ্নকে indicator/ধাপের যোগফলে ভেঙে প্রতিটার গড় আলাদা বের করে যোগ করো — distribution বা simulation ছাড়াই নিখুঁত উত্তর।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "'গড়ে কত' প্রশ্ন = linearity of expectation — মোটকে সরল টুকরোয় ভাঙো, প্রতিটার গড় নাও, যোগ করো। dependence খুঁজতে যেও না, লাগে না। coupon collector = n·Hₙ, dice = 3.5 × সংখ্যা।"

পরের ধাপ → 145 — Probability DP (যখন linearity-তে ভাঙা যায় না, তখন state-এ probability বওয়া)। শিকড় → 052 — Probability Basics।

ফিরে দেখা: এই level-এর map → ../README.md · চিন্তার ছাঁচ → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি করা হয়নি — বরং "CP-style pattern" / "common interview pattern" বলা হয়েছে।