Birthday paradox, hash collision আর balls-into-bins

১ · জন্মদিনের সমস্যা — ২৩ জনেই অর্ধেকের বেশি

বাজারঘরের অফিসে ২৩ জন কর্মী। কেউ জিজ্ঞেস করলেন, “এখানে দুজনের জন্মদিন একই হওয়ার সম্ভাবনা কত?” বেশিরভাগ মানুষ অনুমান করেন খুব কম, হয়তো ৫ বা ১০ শতাংশ, কারণ বছরে দিন ৩৬৫টি আর মানুষ মাত্র ২৩ জন। আসল উত্তর ৫০ শতাংশের বেশি। এই অবাক করা ফলটির নাম birthday paradox. এটি আসলে কোনো যুক্তির বিরোধ নয়, শুধু আমাদের অনুমানের ভুল, তাই অনেকে একে birthday problem বলেন।

অনুমান ভুল হয় কারণ মন অজান্তে প্রশ্নটিকে বদলে ফেলে: “আমার জন্মদিনে আর কারও জন্মদিন পড়বে কি?” সেটি সত্যিই কম সম্ভাব্য। কিন্তু আসল প্রশ্ন যেকোনো দুজন নিয়ে, আর ২৩ জন থেকে জোড়া বানানো যায় C(23, 2) = 253টি। প্রতিটি জোড়ার মিলের সুযোগ ছোট, কিন্তু সুযোগের সংখ্যা মানুষের সংখ্যার বর্গের মতো বাড়ে। পর্ব ৩২-এ দেখেছিলাম, মিল নিশ্চিত করতে ৩৬৭ জন লাগে (২৯ ফেব্রুয়ারিসহ)। এই পর্বের প্রশ্ন অন্য: নিশ্চয়তা নয়, সম্ভাবনা।

মডেল: কী ধরে নিচ্ছি

গণিত করতে হলে পরীক্ষাটিকে স্পষ্ট করতে হয়। পর্ব ৩৮ “বিচ্ছিন্ন সম্ভাবনা — sample space, event আর Laplace-এর সংজ্ঞা”-র ভাষায়, আমরা তিনটি জিনিস ধরে নিচ্ছি: (১) বছর n = 365 দিনের, ২৯ ফেব্রুয়ারি বাদ; (২) প্রত্যেকের জন্মদিন n-টি দিনের যেকোনোটি সমান সম্ভাবনায়; (৩) একজনের জন্মদিন অন্যজনের ওপর নির্ভর করে না (যমজ নেই)। তাহলে k জনের জন্মদিনের তালিকা (d₁, …, d_k) হলো একটি ফল, আর sample space Ω = {1, …, n}^k, যার আকার n^k (পর্ব ৩১-এর গুণের নিয়ম)। প্রতিটি ফল সমান সম্ভাব্য, তাই একটি ঘটনার সম্ভাবনা = তার ফলের সংখ্যা ÷ n^k.

প্রমাণ:

1. ঘটনা A = “অন্তত দুজনের জন্মদিন একই”। এর complement A^c = “সবার জন্মদিন আলাদা”। P(A) = 1 − P(A^c). — complement-এর নিয়ম; ঘটনা সেট, তাই পর্ব ১৫-এর complement
2. A^c-এর ফল হলো এমন তালিকা, যার k-টি মান সব আলাদা। প্রথমজনের n বিকল্প, দ্বিতীয়জনের n − 1, …, k-তম জনের n − k + 1. মোট n(n − 1)⋯(n − k + 1) = P(n, k)টি। — গুণের নিয়ম, পর্ব ৩৩-এর k-permutation
3. সব ফল সমান সম্ভাব্য, তাই P(A^c) = P(n, k)/n^k. প্রতিটি গুণনীয়ককে n দিয়ে ভাগ করলে (n − i)/n = 1 − i/n, i = 0, …, k − 1. — Laplace-এর সংজ্ঞা
4. k > n হলে P(n, k)-এ শূন্য গুণনীয়ক আসে (n − n = 0), তাই P(A^c) = 0, যা pigeonhole-এর সঙ্গে মেলে। ∎

সূত্রটির একটি “গল্প” আছে, যা stepper-এ দেখবেন: মানুষ একজন একজন করে ঘরে ঢোকেন। i জন ঢোকার পর (সবার জন্মদিন আলাদা থাকলে) i-টি দিন “দখল” হয়েছে, তাই পরের জনের মিল এড়ানোর সম্ভাবনা (n − i)/n. সবগুলো গুণ করলেই সূত্র।

1k=1: P(সব আলাদা) = 12k=2: × 364/365 = 0.997263k=3: × 363/365 = 0.991804k=4: × 362/365 = 0.983645k=5: × 361/365 = 0.972866… k=23: × 343/365 = 0.49270

২ · আসন্নমান e^{−k(k−1)/2n} আর √n-এর নিয়ম

নির্ভুল সূত্রটি গুণফল, তাই বড় n-এ (যেমন n = 2⁶⁴) মাথায় হিসাব করা যায় না, আর “কত k-এ অর্ধেক?” প্রশ্নের উত্তর সরাসরি বেরোয় না। দরকার একটি সহজ সূত্র। মূল হাতিয়ার একটি অসমতা, যা পুরো পর্বে বারবার লাগবে। এখানে e ≈ 2.71828 হলো স্বাভাবিক লগারিদমের ভিত্তি, আর e^x = exp(x).

প্রমাণ:

1. f(x) = e^−x − (1 − x) সংজ্ঞায়িত করুন। f(0) = 1 − 1 = 0. — সরাসরি বসানো
2. f′(x) = 1 − e^−x. x > 0 হলে e^−x < 1, তাই f′ > 0; x < 0 হলে e^−x > 1, তাই f′ < 0. — derivative-এর চিহ্ন
3. অর্থাৎ f বাঁ দিক থেকে 0 পর্যন্ত কমে, তারপর বাড়ে; সবচেয়ে ছোট মান f(0) = 0. তাই সব x-এ f(x) ≥ 0, আর x ≠ 0-এ কঠোরভাবে বড়। ∎

ছোট x-এ e^−x = 1 − x + x²/2 − ⋯, তাই পার্থক্য প্রায় x²/2, খুবই ছোট। জন্মদিনের গুণনীয়কগুলোতে x = i/n, যা ছোট; তাই অসমতাটি প্রায় সমতা।

প্রমাণ (নিচের সীমা):

1. উপপাদ্য ১.১: P(সব আলাদা) = ∏_i=1^k−1 (1 − i/n). (i = 0-এর গুণনীয়ক 1, বাদ দেওয়া যায়।)
2. লেমা ২.১-এ প্রতিটি গুণনীয়ক 1 − i/n ≤ e^−i/n, আর সব গুণনীয়ক অঋণাত্মক (k ≤ n ধরে; k > n হলে P(মিল) = 1, দাবি এমনিই সত্য)। অঋণাত্মক সংখ্যার অসমতা গুণ করা যায়। — লেমা ২.১
3. তাই P(সব আলাদা) ≤ e^{−(1 + 2 + ⋯ + (k−1))/n} = e^{−k(k−1)/2n}. — e^ae^b = e^a+b, আর পর্ব ১৭-এর 1 + ⋯ + (k − 1) = k(k − 1)/2
4. complement নিলে P(মিল) ≥ 1 − e^{−k(k−1)/2n}. ∎

প্রমাণ (উপরের সীমা): জোড়া {a, b}-এর জন্য ঘটনা E_ab = “a আর b-এর মান সমান”, P(E_ab) = n/n² = 1/n. “কোনো মিল” = সব E_ab-এর union, আর union bound (Boole-এর অসমতা, পর্ব ৩৮-এ প্রমাণিত) বলে union-এর সম্ভাবনা ≤ আলাদা সম্ভাবনার যোগফল = C(k, 2)/n. ∎

k = 23, n = 365-এ k(k − 1)/2n = 253/365 ≈ 0.69315, যা প্রায় হুবহু ln 2 ≈ 0.69315! তাই নিচের সীমা 1 − e^−0.69315 ≈ 0.50000, আর নির্ভুল মান 0.50730. উপরের সীমা 0.6932, দুর্বল; k বাড়লে তা 1 ছাড়িয়ে যায় (k = 40-এ 2.137), তখন কোনো তথ্য দেয় না। মনে রাখার মতো ফল হলো নিচের সীমা থেকে আসা “অর্ধেকের নিয়ম”: e^{−k(k−1)/2n} = 1/2 বসালে k(k − 1) = 2n ln 2, অর্থাৎ

k_½ ≈ √(2n ln 2) ≈ 1.1774 √n.

n = 365-এ 1.1774 × 19.105 ≈ 22.49, তাই ২৩ জন। আরেকটি পরিচিত মাপ: প্রথম মিল আসা পর্যন্ত গড়ে কতজন লাগে? উত্তর প্রায় √(πn/2) + 2/3; n = 365-এ scratch-এ নির্ভুল হিসাবে 24.62 জন। পর্ব ২৫-এর Pollard rho ঠিক এই √p-যুক্তিতে চলে। সারকথা: n-টি সম্ভাব্য মানে মিল আসে মোটামুটি √n-টি নমুনায়, n/2-তে নয়।

এবার Python-এ নির্ভুল মান (Fraction দিয়ে, কোনো গোলমাল ছাড়া), আসন্নমান, union bound আর একটি seed-দেওয়া simulation পাশাপাশি দেখা যাক। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

import math, random
from fractions import Fraction
random.seed(42)

def p_exact(k, n=365):
    """P(at least two of k people share a birthday), exact."""
    no = Fraction(1)
    for i in range(k):
        no *= Fraction(n - i, n)          # person i+1 avoids i used days
    return 1 - no

def p_sim(k, n=365, trials=2000):
    hits = 0
    for _ in range(trials):
        days = [random.randrange(n) for _ in range(k)]
        hits += len(set(days)) < k        # some day used twice
    return hits / trials

print(" k   exact    1-e^(-k(k-1)/2n)  C(k,2)/n   sim")
for k in (5, 10, 20, 23, 30, 40, 60):
    ex = p_exact(k)
    approx = 1 - math.exp(-k * (k - 1) / (2 * 365))
    union = min(1, math.comb(k, 2) / 365)
    print(f"{k:2}  {float(ex):.4f}   {approx:.4f}            "
          f"{union:.4f}     {p_sim(k):.4f}")

k = 1
while p_exact(k) <= Fraction(1, 2):
    k += 1
ex = p_exact(k)
print("smallest k with P > 1/2:", k)
print("exact P(23) =", float(ex), "| denominator has",
      len(str(ex.denominator)), "digits")

 k   exact    1-e^(-k(k-1)/2n)  C(k,2)/n   sim
 5  0.0271   0.0270            0.0274     0.0260
10  0.1169   0.1160            0.1233     0.1120
20  0.4114   0.4058            0.5205     0.4240
23  0.5073   0.5000            0.6932     0.5055
30  0.7063   0.6963            1.0000     0.7045
40  0.8912   0.8820            1.0000     0.8935
60  0.9941   0.9922            1.0000     0.9925
smallest k with P > 1/2: 23
exact P(23) = 0.5072972343239854 | denominator has 53 digits

৩ · Birthday bound আর hash collision

এবার “দিন” বদলে “hash মান” বসান। একটি hash function যেকোনো ইনপুটকে b bit-এর একটি আউটপুটে নেয়, যাকে বলে digest; সম্ভাব্য digest n = 2^bটি। দুটি আলাদা ইনপুটের digest সমান হলে তা collision. ইনপুট অসীম, আউটপুট সসীম, তাই collision থাকা নিশ্চিত (পর্ব ৩২)। প্রশ্ন হলো, এলোমেলো ইনপুট নিয়ে চেষ্টা করলে কতগুলোতে একটি collision আশা করা যায়।

ভালো hash-কে মডেলে একটি “এলোমেলো ফাংশন” ধরা হয়: প্রতিটি নতুন ইনপুটের digest যেন n-টি মানের যেকোনোটি সমান সম্ভাবনায়, আগেরগুলোর ওপর নির্ভর না করে (পর্ব ১৬-এর ভাষায় ইনপুটের সেট থেকে n-উপাদানের সেটে একটি এলোমেলো ফাংশন)। এটি জন্মদিনের মডেলই। তাই উপপাদ্য ২.২ সরাসরি খাটে, আর মোটামুটি 1.1774 · 2^b/2টি ইনপুটে collision-এর সম্ভাবনা অর্ধেক হয়। এই √n-সীমাকে বলে birthday bound.

টেবিলের শিক্ষা পরিষ্কার। ধরুন বাজারঘর প্রতিটি অর্ডারের জন্য একটি এলোমেলো 32-bit order id বানায়। ৪০০ কোটির বেশি সম্ভাব্য id দেখে মনে হয় collision প্রায় অসম্ভব, অথচ মাত্র ৭৭ হাজার অর্ডারেই দুটি অর্ডারের id মেলার সম্ভাবনা অর্ধেক। ১০,০০০ অর্ডারেও সম্ভাবনা প্রায় 1.16 শতাংশ (নিচের অঙ্ক ১)। তাই এলোমেলো id-তে অন্তত 128 bit রাখা হয়, অথবা database-এ আগে থেকে আছে কি না যাচাই করা হয়।

নিরাপত্তায় একই অঙ্কের নাম birthday attack: কেউ যদি যেকোনো দুটি আলাদা বার্তা চান যাদের digest সমান (কোন বার্তা, তাতে কিছু যায় আসে না), তবে এলোমেলো বার্তার digest হিসাব করে মিল খুঁজলেই হয়, আর সাধারণ পদ্ধতিতে প্রায় 2^b/2টি চেষ্টা লাগে। একটি নির্দিষ্ট digest-এর সঙ্গে মেলাতে (preimage) লাগে প্রায় 2^bটি, যা অনেক বেশি; এটি “আমার জন্মদিন” প্রশ্নের মতো। তাই b-bit hash-এর collision-এর বিরুদ্ধে নিরাপত্তা মোটামুটি b/2 bit, আর এই কারণেই আধুনিক hash-এর digest 256 bit: তখন 2¹²⁸টি চেষ্টা লাগে, যা কার্যত অসম্ভব। এই পর্বে আমরা শুধু গণিতটি দেখছি; hash-এর নিরাপদ ব্যবহার Cybersecurity কোর্সের পর্ব ০৯-এ।

৪ · Balls into bins — খালি bin আর collision-জোড়ার প্রত্যাশা

জন্মদিন, hash আর আরও অনেক সমস্যার একটি সাধারণ মডেল আছে: balls into bins. n-টি bin (ঝুড়ি) আর m-টি বল; প্রতিটি বল স্বাধীনভাবে, সমান সম্ভাবনায় একটি bin-এ পড়ে। বাজারঘরের ভাষায়: m-টি অর্ডার n জন ডেলিভারি রাইডারের মধ্যে এলোমেলো ভাগ হলো। প্রশ্নগুলো স্বাভাবিক: কতজন রাইডার কোনো অর্ডার পাবেন না? কত জোড়া অর্ডার একই রাইডারের কাছে গেল? সবচেয়ে ব্যস্ত রাইডারের হাতে কয়টি? জন্মদিনে bin = দিন, বল = মানুষ; hash table-এ bin = slot, বল = key.

প্রত্যাশা (expected value) আর linearity-র মূল ধারণা পর্ব ৪০ “Random variable আর প্রত্যাশা — linearity-র জাদু”-র বিষয়; এখানে দুটি তথ্যই লাগবে। প্রথমত, একটি ঘটনা A-এর indicator random variable I_A হলো A ঘটলে 1, না ঘটলে 0, আর E[I_A] = 1 · P(A) + 0 · P(A^c) = P(A). দ্বিতীয়ত, linearity of expectation: E[X + Y] = E[X] + E[Y], চলকগুলো স্বাধীন হোক বা না হোক। এই দুটি মিলে একটি শক্তিশালী কৌশল দেয়: জটিল একটি সংখ্যাকে অনেক indicator-এর যোগফল হিসেবে লিখুন, আর প্রতিটির সম্ভাবনা যোগ করুন।

প্রমাণ:

1. প্রতিটি bin j-এর জন্য I_j = 1 যদি bin j খালি থাকে, নইলে 0. তাহলে X = I₁ + I₂ + ⋯ + I_n. — প্রতিটি খালি bin একবার গোনা হয়
2. একটি নির্দিষ্ট বল bin j-এ না পড়ার সম্ভাবনা 1 − 1/n. বলগুলো স্বাধীন, তাই m-টির কোনোটিই না পড়ার সম্ভাবনা (1 − 1/n)^m. — স্বাধীন ঘটনার গুণ
3. E[I_j] = P(bin j খালি) = (1 − 1/n)^m. — indicator-এর প্রত্যাশা
4. linearity: E[X] = ∑_j E[I_j] = n(1 − 1/n)^m. লেমা ২.১-এ 1 − 1/n ≤ e^−1/n, তাই E[X] ≤ n e^−m/n. ∎

লক্ষ করুন, I_j-গুলো পরস্পর স্বাধীন নয় (একটি bin খালি হলে বাকিগুলোতে বল বেশি পড়ে), তবু linearity খাটে। m = n-এ (1 − 1/n)ⁿ → 1/e, এটি e-এর একটি পরিচিত সীমা; n = 10-এ মান 0.3487, n = 1000-এ 0.3677, আর n = 10⁶-এ 0.36788.

1X = I₁ + I₂ + I₃2P(bin 1 খালি) = (2/3)³3E[Iⱼ] = 8/27, j = 1, 2, 34E[X] = 3 · 8/27 = 8/9527 ফল: 6 + 18 + 36মোট খালি = 18 + 2·3 = 247n(1 − 1/n)ⁿ ≈ n/e

প্রমাণ: প্রতিটি জোড়া {a, b}-এর জন্য J_ab = 1 যদি a আর b একই bin-এ পড়ে। P(J_ab = 1) = ∑_j (1/n)(1/n) = 1/n. Y = ∑ J_ab, জোড়া C(m, 2)টি (পর্ব ৩৪), তাই linearity-তে E[Y] = C(m, 2)/n. ∎ প্রমাণে শুধু “যেকোনো দুটি বল স্বাধীন” লেগেছে; পুরো স্বাধীনতা লাগেনি। এই পর্যবেক্ষণটিই universal hashing-এর মূলে (অংশ ৬)।

এবার জন্মদিনের সঙ্গে সংযোগটি দেখুন: ২৩ জনে প্রত্যাশিত মিল-জোড়া 253/365 ≈ 0.69, এক জোড়ার কম। তবু “অন্তত একটি মিল”-এর সম্ভাবনা অর্ধেকের বেশি। প্রত্যাশা আর সম্ভাবনা আলাদা জিনিস, কিন্তু birthday bound মূলত এই কথাই বলে: প্রত্যাশিত জোড়া প্রায় 1 হলে মিল সম্ভাব্য হয়ে ওঠে, অর্থাৎ m²/2n ≈ 1, বা m ≈ √(2n).

৫ · সবচেয়ে ভরা bin — maximum load আর দুটি বিকল্পের জাদু

m = n হলে গড়ে প্রতিটি bin-এ ঠিক একটি বল। কিন্তু গড় দিয়ে সবচেয়ে ব্যস্ত রাইডারের কষ্ট বোঝা যায় না। hash table-এ সবচেয়ে লম্বা chain খারাপ ক্ষেত্রের খোঁজার সময় ঠিক করে, আর server-এ সবচেয়ে ভরা machine ঠিক করে কে আগে ভেঙে পড়বে। সবচেয়ে ভরা bin-এর বলের সংখ্যাকে বলে maximum load.

প্রমাণ:

1. একটি নির্দিষ্ট bin-এ অন্তত t-টি বল থাকলে কোনো t-উপাদানের বল-সেট পুরোটা সেই bin-এ পড়েছে। একটি নির্দিষ্ট t-সেটের সবগুলো সেখানে পড়ার সম্ভাবনা (1/n)^t. — স্বাধীনতা
2. t-সেট C(n, t)টি, তাই union bound-এ P(bin-এ ≥ t) ≤ C(n, t)(1/n)^t. — union bound
3. C(n, t) = n(n − 1)⋯(n − t + 1)/t! ≤ n^t/t!, তাই সীমাটি ≤ 1/t!. — প্রতিটি গুণনীয়ক ≤ n
4. n-টি bin-এর ওপর আবার union bound: P(কোনো bin-এ ≥ t) ≤ n/t!. t! ≥ n² হলে এটি ≤ 1/n. ∎

t কত বড় হলে t! ≥ n²? Stirling-এর আসন্নমান t! ≈ (t/e)^t√(2πt) দিয়ে হিসাব করলে দেখা যায়, t = ⌈3 ln n / ln ln n⌉ বড় n-এ যথেষ্ট; তাই maximum load উচ্চ সম্ভাবনায় O(log n / log log n). উদাহরণ: n = 1000-এ 10! = 3,628,800 ≥ 10⁶, তাই P(maximum load ≥ 10) ≤ 1000/10! ≈ 0.00028. একটি মিলিয়ে দেখার মতো নিচের সীমাও জানা আছে: উচ্চ সম্ভাবনায় maximum load অন্তত (1 − o(1)) ln n / ln ln n, তাই আসল বৃদ্ধি Θ(log n / log log n). সেই প্রমাণ এখানে দিচ্ছি না; তা উন্নত পাঠ্যবইয়ে (যেমন Mitzenmacher ও Upfal-এর probability and computing বই) পাবেন।

দুটি বিকল্পের জাদু

এবার একটি ছোট বদল। প্রতিটি অর্ডারের জন্য এলোমেলোভাবে দুজন রাইডার বেছে, তাঁদের মধ্যে যাঁর হাতে এই মুহূর্তে কম অর্ডার, তাঁকে দিন। সুপারশপে দুটি ক্যাশ কাউন্টার দেখে ছোট লাইনে দাঁড়ানোর মতো। ফল নাটকীয়: maximum load log n / log log n থেকে নেমে আসে প্রায় ln ln n / ln 2 + O(1)-এ, যা কার্যত ধ্রুবক (n = 10⁶-এ ln ln n / ln 2-এর মান প্রায় 3.8 হয়)। এই ফলটি power of two choices নামে পরিচিত; Azar, Broder, Karlin আর Upfal-এর কাজ, যা ১৯৯৪ সালে সম্মেলনে আর ১৯৯৯ সালে জার্নালে প্রকাশিত বলে উল্লেখ করা হয়। আশ্চর্যের কথা, d-টি বিকল্পে উন্নতি শুধু ln ln n / ln d, অর্থাৎ ১ থেকে ২-এ যাওয়াই বড় লাফ, ২ থেকে ৩-এ সামান্য। এর প্রমাণ এই পর্বের সীমার বাইরে; আমরা Python-এ সত্যিই দেখব।

import math, random
from collections import Counter
random.seed(7)

def throw(m, n, choices=1):
    """Throw m balls into n bins; with 2 choices pick the lighter bin."""
    load = [0] * n
    for _ in range(m):
        cand = [random.randrange(n) for _ in range(choices)]
        load[min(cand, key=lambda b: load[b])] += 1
    return load

n = m = 1000
T = 200
empty = pairs = 0
top1, top2 = Counter(), Counter()
for _ in range(T):
    load = throw(m, n)
    empty += load.count(0)
    pairs += sum(c * (c - 1) // 2 for c in load)
    top1[max(load)] += 1
    top2[max(throw(m, n, 2))] += 1
print(f"empty bins: sim {empty / T:.2f} | n(1-1/n)^m = "
      f"{n * (1 - 1 / n) ** m:.2f} | n/e = {n / math.e:.2f}")
print(f"colliding pairs: sim {pairs / T:.2f} | C(m,2)/n = "
      f"{math.comb(m, 2) / n:.2f}")
print("max load, 1 choice :", sorted(top1.items()))
print("max load, 2 choices:", sorted(top2.items()))
for n in (10**2, 10**4, 10**5):
    a, b = max(throw(n, n)), max(throw(n, n, 2))
    lnn = math.log(n)
    print(f"n={n:>6}: max load 1 choice {a}, 2 choices {b} | "
          f"ln n/ln ln n = {lnn / math.log(lnn):.2f}")

empty bins: sim 366.93 | n(1-1/n)^m = 367.70 | n/e = 367.88
colliding pairs: sim 498.50 | C(m,2)/n = 499.50
max load, 1 choice : [(4, 6), (5, 108), (6, 69), (7, 9), (8, 7), (9, 1)]
max load, 2 choices: [(3, 199), (4, 1)]
n=   100: max load 1 choice 4, 2 choices 3 | ln n/ln ln n = 3.02
n= 10000: max load 1 choice 6, 2 choices 4 | ln n/ln ln n = 4.15
n=100000: max load 1 choice 8, 2 choices 4 | ln n/ln ln n = 4.71

৬ · Chaining-এর খরচ 1 + α আর universal hashing

Hash table-এ n-টি slot থাকে, আর key x রাখা হয় slot h(x)-এ। Separate chaining-এ প্রতিটি slot-এ একটি linked list, আর একই slot-এ পড়া সব key সেই তালিকায় যায়। m-টি key রাখলে load factor α = m/n, গড়ে প্রতিটি তালিকার দৈর্ঘ্য। (DSA বইয়ে প্রায়ই অক্ষর উল্টো, n key আর m slot; এই পর্বে balls-into-bins-এর সঙ্গে মিল রেখে n = slot.) কোডের দিক DSA কোর্সের পর্ব ৩২-এ; এখানে প্রশ্ন একটাই: গড়ে কতগুলো key-এর সঙ্গে তুলনা লাগে, আর কেন।

গণিতের জন্য একটি মডেল লাগে। Simple uniform hashing ধরে নেয়: প্রতিটি key স্বাধীনভাবে, সমান সম্ভাবনায় n-টি slot-এর যেকোনোটিতে যায়। অর্থাৎ key-রা হলো balls, slot-রা bins.

প্রমাণ (ক):

1. খোঁজা key x, h(x) = s. খুঁজতে slot s-এর পুরো তালিকা দেখতে হয়, তাই তুলনা = L_s = সেই তালিকার দৈর্ঘ্য। — x নেই, তাই শেষ পর্যন্ত যেতে হয়
2. রাখা key k₁, …, k_m-এর জন্য I_i = 1 যদি h(k_i) = h(x). L_s = ∑ I_i. — indicator
3. h(k_i) আর h(x) স্বাধীন ও সমবণ্টিত, তাই P(I_i = 1) = 1/n. — মডেল
4. linearity: E[L_s] = m/n = α. hash হিসাবের একটি ধাপ যোগ করলে মোট 1 + α. ∎

প্রমাণ (খ):

1. key-গুলো k₁, …, k_m ক্রমে ঢোকানো হয়েছে, প্রতিটি তালিকার মাথায়। তাই k_i খুঁজতে তার আগে দেখা হয় শুধু তার পরে ঢোকা, একই slot-এর key-গুলো। — মাথায় বসানো
2. তুলনা = 1 + ∑_j>i X_ij, যেখানে X_ij = 1 যদি h(k_j) = h(k_i); E[X_ij] = 1/n. তাই E = 1 + (m − i)/n. — indicator আর linearity
3. i সমান সম্ভাবনায় 1..m, তাই গড় নিলে 1 + (1/m) ∑_i=1^m (m − i)/n = 1 + (1/m) · m(m − 1)/2 · (1/n) = 1 + (m − 1)/2n. ∎ — ∑(m − i) = 0 + 1 + ⋯ + (m − 1)

অর্থাৎ α ধ্রুবক রাখলে (যেমন টেবিল ভরে গেলে slot দ্বিগুণ করা) খোঁজা গড়ে O(1). উদাহরণ: ৬টি key, ৩টি slot (α = 2): না-থাকা key-এর খোঁজে গড়ে 2টি তুলনা, থাকা key-এর খোঁজে 1 + 5/6 ≈ 1.83টি।

মডেলটি কি বাস্তব? Universal hashing

Simple uniform hashing একটি অনুমান, আর বাস্তবে h একটি নির্দিষ্ট ফাংশন। কেউ যদি জেনে-বুঝে এমন key পাঠান যেগুলো সব একই slot-এ পড়ে, তবে তালিকা m-লম্বা হয়ে খোঁজা O(m) হয়ে যায়। পর্ব ২৬-এ এর উত্তর দেখেছিলাম: universal hashing, যেখানে প্রোগ্রাম শুরুতে একটি ফাংশন-পরিবার থেকে এলোমেলোভাবে h বাছে (যেমন ((ak + b) mod p) mod n; সেখানে বালতির সংখ্যাকে m লেখা হয়েছিল)। পরিবার H-কে universal বলে, যদি যেকোনো দুটি আলাদা key x ≠ y-এর জন্য P_h∈H[h(x) = h(y)] ≤ 1/n.

প্রমাণ: L = ∑_y∈S I_y, যেখানে I_y = 1 যদি h(y) = h(x). universal শর্তে E[I_y] ≤ 1/n, তাই linearity-তে E[L] ≤ m/n. ∎

পার্থক্যটি সূক্ষ্ম কিন্তু গুরুত্বপূর্ণ। উপপাদ্য ৬.১-এ এলোমেলোতা ছিল ডেটায় (key-রা যেন এলোমেলো), যা আমাদের নিয়ন্ত্রণে নেই। উপপাদ্য ৬.২-এ এলোমেলোতা আমাদের বাছাই করা h-এ, আর key-রা যেকোনো, এমনকি প্রতিপক্ষের বাছা। প্রমাণে শুধু জোড়ায় জোড়ায় collision-এর সম্ভাবনা লেগেছে, ঠিক উপপাদ্য ৪.২-এর মতো। এই ধারণাটি Carter আর Wegman-এর, ১৯৭০-এর দশকের শেষভাগে প্রকাশিত।

৭ · Bloom filter — কম জায়গায় “হয়তো আছে” আর “নিশ্চিত নেই”

বাজারঘরে প্রতিদিন লাখো ব্যবহৃত coupon code জমা হয়। নতুন code এলে জানতে হবে আগে ব্যবহার হয়েছে কি না। সব code মেমরিতে রাখা ব্যয়বহুল, আর ডিস্কে খোঁজা ধীর। একটি Bloom filter খুব কম জায়গায় এই প্রশ্নের প্রায়-সঠিক উত্তর দেয়: “নিশ্চিত নেই” বললে সেটি সবসময় সত্য; “হয়তো আছে” বললে মাঝে মাঝে ভুল হতে পারে। এই ভুলের নাম false positive. উত্তর “হয়তো আছে” হলে তবেই ধীর ডিস্কে নিশ্চিত হতে যাওয়া হয়, তাই বেশিরভাগ খোঁজা দ্রুত শেষ হয়।

গঠন সরল। m-টি bit-এর একটি সারি, শুরুতে সব 0, আর k-টি hash function h₁, …, h_k, প্রতিটি 0..m − 1-এ মান দেয়। (এই অংশে অক্ষর প্রচলিত রীতিতে: m = bit-এর সংখ্যা, n = রাখা item-এর সংখ্যা।) item x ঢোকাতে k-টি অবস্থান h₁(x), …, h_k(x)-এ bit 1 করা হয়। খুঁজতে একই k-টি অবস্থান দেখা হয়: কোনোটি 0 হলে x কখনো ঢোকেনি (কারণ ঢুকলে সেটি 1 হতো); সবগুলো 1 হলে “হয়তো আছে”, কারণ অন্য item-রা মিলে ঠিক সেই bit-গুলো 1 করে থাকতে পারে। নিচের stepper-এ একটি খেলনা filter: m = 10, k = 3, তিনটি তিন অঙ্কের order id, আর hash হলো h₁ = শেষ অঙ্ক, h₂ = দশকের অঙ্ক, h₃ = অঙ্কগুলোর যোগফল mod 10.

1bits = 00000000002insert 427 → 7, 2, 33insert 815 → 5, 1, 44insert 362 → 2, 6, 15query 815 → 5, 1, 46query 509 → 9, 0, 47query 236 → 6, 3, 18FP হার ≈ (7/10)³

প্রমাণ (derivation):

1. n-টি item ঢোকাতে মোট kn বার একটি bit বাছা হয়। একটি নির্দিষ্ট bit প্রতিবার বাছা না হওয়ার সম্ভাবনা 1 − 1/m, তাই kn বারেও না হওয়ার সম্ভাবনা (1 − 1/m)^kn. লেমা ২.১-এ এটি ≤ e^−kn/m, আর বড় m-এ প্রায় সমান। — উপপাদ্য ৪.১-এর মতোই: bit = bin, বাছাই = বল
2. তাই প্রত্যাশিতভাবে bit-গুলোর ভগ্নাংশ p = e^−kn/m শূন্য। না-ঢোকানো x-এর k-টি অবস্থান এলোমেলো; সবগুলো 1 হওয়ার সম্ভাবনা প্রায় (1 − p)^k. — আসন্নমান: এখানে bit-গুলোকে স্বাধীন ধরা হচ্ছে, যা পুরো সত্য নয়
3. সেরা k: kn/m = −ln p, তাই k = −(m/n) ln p, আর ln f = k ln(1 − p) = −(m/n) · ln p · ln(1 − p). — লগারিদম নেওয়া
4. ln p · ln(1 − p) রাশিটি p আর 1 − p অদলবদল করলে বদলায় না, আর (0, 1)-এ এর সবচেয়ে বড় মান p = 1/2-এ (প্রতিসাম্য আর একটি সর্বোচ্চ বিন্দু; derivative দিয়ে যাচাই করা যায়)। ln f সবচেয়ে ছোট তখনই। — প্রতিসাম্য
5. p = 1/2 মানে e^−kn/m = 1/2, অর্থাৎ k = (m/n) ln 2, আর f = (1/2)^k = (1/2)^{(m/n) ln 2} ≈ (0.6185)^m/n. ∎

সেরা অবস্থায় অর্ধেক bit 1, অর্ধেক 0: filter-টি সবচেয়ে বেশি “তথ্য” বহন করে। ব্যবহারিক সূত্র: false positive হার f চাইলে প্রতি item-এ m/n = −ln f / (ln 2)² bit লাগে, f = 1% হলে প্রায় 9.59 bit আর k ≈ 7. লক্ষ করুন, এটি item-এর আকারের ওপর নির্ভর করে না; ৩০ অক্ষরের coupon code বা ৩০০ অক্ষরের URL, দুটোতেই প্রায় ১০ bit. খেলনা filter-এ (ধাপ ৮) সূত্রের হিসাব (1 − e^−0.9)³ ≈ 0.209, কিন্তু সেখানে সত্যিকারের ভরা bit ৭টি, প্রত্যাশিত প্রায় ৬.১-এর চেয়ে বেশি, তাই আসল হার 0.344. সূত্রটি গড় filter-এর কথা বলে; একটি নির্দিষ্ট filter-এর জন্য (ভরা bit-এর ভগ্নাংশ)^k ভালো আন্দাজ।

এবার নিজের ডেটায় মেপে দেখা যাক। ২০০টি order id (“BG-2026-00000” ধাঁচের) একটি 2000-bit filter-এ রাখা হবে (m/n = 10), আর ৫০০০টি কখনো না-রাখা id দিয়ে false positive গোনা হবে। k-টি hash বানাতে একটি SHA-256 digest-কে দুই ভাগ করে h_i = (h₁ + i·h₂) mod m নেওয়া হয়েছে; এই “double hashing” কৌশলে প্রায় একই হার মেলে বলে Kirsch আর Mitzenmacher দেখিয়েছিলেন বলে উল্লেখ করা হয়। এখানে কোনো এলোমেলো সংখ্যা নেই, তাই আউটপুট সবসময় একই।

import hashlib, math

def positions(key, k, m):
    """k bit positions from one SHA-256 digest (double hashing)."""
    d = hashlib.sha256(key.encode()).digest()
    h1 = int.from_bytes(d[:8], "big")
    h2 = int.from_bytes(d[8:16], "big") | 1
    return [(h1 + i * h2) % m for i in range(k)]

m, n = 2000, 200                       # bits, stored order ids
stored = [f"BG-2026-{i:05d}" for i in range(n)]
others = [f"BG-2027-{i:05d}" for i in range(5000)]   # never stored

print(" k  ones   measured  (1-e^(-kn/m))^k")
for k in (1, 2, 4, 7, 10, 14):
    bits = bytearray(m)
    for key in stored:
        for p in positions(key, k, m):
            bits[p] = 1
    assert all(all(bits[p] for p in positions(s, k, m)) for s in stored)
    fp = sum(all(bits[p] for p in positions(q, k, m)) for q in others)
    formula = (1 - math.exp(-k * n / m)) ** k
    print(f"{k:2}  {sum(bits):4}   {fp / len(others):.4f}    {formula:.4f}")

k_opt = m / n * math.log(2)
print(f"best k = (m/n) ln 2 = {k_opt:.2f}, then rate ~ "
      f"{0.5 ** k_opt:.4f}")

 k  ones   measured  (1-e^(-kn/m))^k
 1   187   0.0932    0.0952
 2   354   0.0318    0.0329
 4   664   0.0126    0.0118
 7   988   0.0068    0.0082
10  1236   0.0088    0.0102
14  1472   0.0144    0.0190
best k = (m/n) ln 2 = 6.93, then rate ~ 0.0082

৮ · পরীক্ষার অঙ্ক আর তিনটি পরিচিত ভুল

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

অঙ্ক ১: বাজারঘর ১০,০০০টি অর্ডারকে এলোমেলো 32-bit id দেয়। অন্তত দুটি id মেলার সম্ভাবনা কত?

1. n = 2³² = 4,294,967,296, k = 10,000. k(k − 1)/2 = 49,995,000.
2. k(k − 1)/2n = 49,995,000 / 4,294,967,296 ≈ 0.011640.
3. উপপাদ্য ২.২: 1 − e^−0.011640 ≈ 0.011573 ≤ P ≤ 0.011640. নির্ভুল মান (গুণফল দিয়ে) 0.011573, অর্থাৎ প্রায় 1.16 শতাংশ। এত ছোট সম্ভাবনায় দুই সীমা প্রায় সমান।

অঙ্ক ২: ১০০টি অর্ডার ১০০ জন রাইডারের মধ্যে এলোমেলো ভাগ হলে (ক) প্রত্যাশিত কতজন খালি হাতে থাকবেন? (খ) প্রত্যাশিত কত জোড়া অর্ডার একই রাইডারের কাছে যাবে?

1. (ক) উপপাদ্য ৪.১: 100 · (1 − 1/100)¹⁰⁰ = 100 · 0.99¹⁰⁰ ≈ 36.60 জন। (100/e ≈ 36.79-এর খুব কাছে।)
2. (খ) উপপাদ্য ৪.২: C(100, 2)/100 = 4950/100 = 49.5 জোড়া।

অঙ্ক ৩: ১০ লাখ coupon code-এর জন্য 1% false positive হারের Bloom filter-এ কত bit আর কয়টি hash লাগবে?

1. প্রতি item-এ m/n = −ln(0.01)/(ln 2)² = 4.6052/0.4805 ≈ 9.585 bit.
2. m ≈ 9.585 × 10⁶ bit, যা প্রায় 1.2 MB (৮ bit-এ এক byte). k = (m/n) ln 2 ≈ 6.64, তাই k = 7.
3. যাচাই: m/n = 10, k = 7 নিলে (1 − e^−0.7)⁷ ≈ 0.0082 < 0.01 ✓.

ভুল ধরুন ১: “২৩ জনে আমার জন্মদিনেও কারও জন্মদিন মেলার সম্ভাবনা অর্ধেক”

ভুল কোথায়: ২৩ জনের অর্ধেক সম্ভাবনা যেকোনো জোড়ার জন্য (253টি জোড়া)। আপনার সঙ্গে জোড়া মাত্র ২২টি, আর প্রতিজনের আপনার জন্মদিন এড়ানোর সম্ভাবনা 364/365. তাই P = 1 − (364/365)²² ≈ 0.0586, মাত্র প্রায় ৬ শতাংশ। আপনার সঙ্গে মেলার সম্ভাবনা অর্ধেক ছাড়াতে আপনি ছাড়া আরও ২৫৩ জন লাগে। hash-এর ভাষায় এটিই collision (যেকোনো জোড়া, √n) বনাম preimage (নির্দিষ্ট মান, প্রায় n) পার্থক্য।

ভুল ধরুন ২: “৪০ জনে মিলের সম্ভাবনা C(40, 2)/365 = 2.14”

ভুল কোথায়: সম্ভাবনা কখনো 1-এর বেশি হয় না। C(k, 2)/n হলো union bound, একটি উপরের সীমা, আর প্রত্যাশিত মিল-জোড়ার সংখ্যা (উপপাদ্য ৪.২)। জোড়ার ঘটনাগুলো পরস্পর বর্জনশীল নয় (তিনজনের একই জন্মদিনে তিনটি জোড়া একসঙ্গে মেলে), তাই যোগ করলে বেশি গোনা হয়। নির্ভুল উত্তর 0.8912.

ভুল ধরুন ৩: “প্রতিটি bin-এর প্রত্যাশিত load 1, তাই linearity-তে প্রত্যাশিত maximum load-ও 1”

ভুল কোথায়: linearity খাটে যোগফলে, maximum-এ নয়: E[max] ≠ max E. counterexample: ২টি বল, ২টি bin. চারটি সমান সম্ভাব্য ফলের দুটিতে দুই বল একই bin-এ (max = 2), দুটিতে আলাদা bin-এ (max = 1). E[max] = (2 + 1 + 1 + 2)/4 = 1.5 > 1. ব্লক ২-এর আউটপুটেও n = 1000-এ maximum load ৫–৬, গড় load 1 হলেও।

৯ · AI-এর যুগে — সম্ভাবনার হিসাব যাচাই

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

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

• মডেলের অনুমান (সমবণ্টন, স্বাধীনতা) লেখা আছে, আর আমার সমস্যায় সেগুলো যুক্তিসংগত
• জোড়া গোনা হয়েছে ঠিকভাবে: যেকোনো জোড়া C(k, 2), নির্দিষ্ট মানের সঙ্গে k
• আসন্নমান কোন দিকের সীমা, আর তার প্রমাণে কোন অসমতা লেগেছে, তা মিলিয়েছি
• ছোট সংখ্যায় (n = 365, k ≤ 30) Fraction দিয়ে নির্ভুল মান নিজে হিসাব করেছি
• seed দেওয়া simulation চালিয়ে উত্তরের সঙ্গে তুলনা করেছি
• নাম, সাল আর প্রবন্ধ বিশ্বস্ত উৎসে মিলিয়েছি

এই পর্বের প্রায় প্রতিটি দাবি দুইভাবে যাচাই করা যায়: ছোট ক্ষেত্রে সব ফল গুনে নির্ভুল ভগ্নাংশ, আর বড় ক্ষেত্রে seed দেওয়া simulation. AI-এর উত্তর পেলে এই দুটি পরীক্ষা আগে চালান, তারপর প্রমাণের ধাপ পড়ুন।