Expectation

প্রত্যাশিত মান

একটা random variable-এর গড় মান, `E[X] = Σ x·P(X=x)`। Linearity of expectation — `E[X+Y] = E[X]+E[Y]` — independence ছাড়াই খাটে, আর সেটাই একে এত শক্তিশালী করে।

also: expected value, mean

Linearity of expectation সবসময় সত্য — X আর Y স্বাধীন না হলেও। Variance-এ এটা খাটে না; expectation-এ খাটে। এই একটা বৈশিষ্ট্যই বহু কঠিন গণনা তুচ্ছ করে দেয়।

কৌশল — indicator variable:

যা গুনতে চান তাকে indicator-এ ভাঙুন
E[Xᵢ] = P(Xᵢ = 1)
Linearity দিয়ে যোগ করুন

Independence নিয়ে ভাবতেই হয় না।

উদাহরণ — hash collision: n key, m bucket। প্রতিটা জোড়ার collide করার সম্ভাবনা 1/m, জোড়া সংখ্যা C(n,2):

E[collision] = C(n,2)/m = n(n−1)/2m

n = m = 1000 → প্রায় ৫০০টা collision, load factor ১.০ হলেও।

Randomized quicksort-এর O(n log n) প্রমাণ একই কৌশলে — Xᵢⱼ = 1 যদি zᵢ আর zⱼ তুলনা হয়। P(Xᵢⱼ=1) = 2/(j−i+1)। যোগ করলে 2n ln n। কোনো recurrence solve করতে হয় না, আর Xᵢⱼ-রা স্বাধীন না হওয়া সত্ত্বেও কাজ করে।

সতর্কতা: expectation প্রায়ই “সাধারণত যা হয়” নয়। একটা ছক্কার প্রত্যাশিত মান ৩.৫ — যা কখনো ওঠে না।