Probabilistic method আর randomized algorithm

১ · এলোমেলোতা কেন কাজে লাগে — Las Vegas আর Monte Carlo

এই মডিউলের আগের পর্বগুলোতে সম্ভাবনা ছিল বিশ্লেষণের বিষয়: ছক্কা, ত্রুটিপূর্ণ ব্যাচ, hash bucket. শেষ পর্বে দিক বদলাচ্ছে। এবার এলোমেলোতা নিজেই হাতিয়ার: algorithm ইচ্ছা করে মুদ্রা ছোড়ে, আর প্রমাণ ইচ্ছা করে একটি এলোমেলো বস্তু বানায়। দুই ক্ষেত্রেই যে গণিত লাগে তা আপনি এর মধ্যেই শিখেছেন: union bound (পর্ব ৩৮ “বিচ্ছিন্ন সম্ভাবনা — sample space, event আর Laplace-এর সংজ্ঞা”), স্বাধীন ঘটনার গুণ (পর্ব ৩৯ “শর্তসাপেক্ষ সম্ভাবনা, independence আর Bayes-এর উপপাদ্য”), আর indicator দিয়ে প্রত্যাশা (পর্ব ৪০ “Random variable আর প্রত্যাশা — linearity-র জাদু”).

একটি সূক্ষ্ম কিন্তু জরুরি কথা: এখানে সম্ভাবনা নেওয়া হয় algorithm-এর মুদ্রার ওপর, ইনপুটের ওপর নয়। “গড় ইনপুটে দ্রুত” (average-case) আর “প্রতিটি ইনপুটে, প্রত্যাশায় দ্রুত” সম্পূর্ণ আলাদা দাবি। প্রথমটি ইনপুটের বণ্টন অনুমান করে; দ্বিতীয়টি সবচেয়ে খারাপ ইনপুটেও খাটে, কারণ প্রতিপক্ষ ইনপুট বাছতে পারে, মুদ্রার ফল বাছতে পারে না।

এক ধরন থেকে অন্য ধরনে। Las Vegas-কে Monte Carlo বানানো সহজ: প্রত্যাশিত সময় T হলে 2T ধাপে থামিয়ে দিন। Markov-এর অসমতা (পর্ব ৪১ “Variance আর concentration — Markov, Chebyshev আর Chernoff”) বলে P(সময় ≥ 2T) ≤ 1/2, তাই থামানো algorithm বড়জোর 1/2 সম্ভাবনায় “জানি না” বলে। উল্টো দিকে, Monte Carlo-র উত্তর যদি দ্রুত যাচাই করা যায় (যেমন একটি উৎপাদক ভাগ করে মেলানো), তাহলে যাচাই না মেলা পর্যন্ত আবার চালালেই একটি Las Vegas algorithm পাওয়া যায়।

1. ভুল হতে পারে শুধু যখন সঠিক উত্তর “হ্যাঁ” অথচ k বারই “না” এসেছে; সঠিক উত্তর “না” হলে কোনো run “হ্যাঁ” বলে না। — one-sided error
2. E_i = “i-তম run ভুল বলে”, P(E_i) ≤ ε, আর run-গুলোর এলোমেলো bit আলাদা, তাই E₁, …, E_k স্বাধীন। — অনুমান
3. P(E₁ ∩ … ∩ E_k) = P(E₁) ⋯ P(E_k) ≤ ε^k. ∎ — স্বাধীন ঘটনার গুণ (পর্ব ৩৯)

Miller–Rabin পরীক্ষায় (পর্ব ২৫ “Primality test আর factoring — Miller–Rabin থেকে কঠিনতার ধারণা”) এক base-এ ভুলের সম্ভাবনা ≤ 1/4, তাই ২০টি এলোমেলো base-এ ≤ 4⁻²⁰ ≈ 10⁻¹². একে বলে amplification. ধাপ ২-এর “স্বাধীন” শব্দটিই এখানে সব; একই এলোমেলো bit আবার ব্যবহার করলে প্রমাণ ভেঙে পড়ে (§৮-এর ভুল যুক্তিটি দেখুন)। Code-এর দিকটি, যেমন treap আর reservoir sampling, DSA কোর্সের পর্ব ৬১-এ আছে; এখানে আমরা প্রমাণে মন দেব।

২ · Las Vegas-এর প্রত্যাশিত সময় — randomized quickselect

Randomized quicksort প্রতিটি ধাপে বর্তমান অংশ থেকে সমান সম্ভাবনায় একটি pivot বাছে। পর্ব ৪০-এ indicator random variable দিয়ে দেখানো হয়েছে, n-টি আলাদা সংখ্যায় প্রত্যাশিত তুলনা 2(n + 1)H_n − 4n ≈ 2n ln n, যেখানে H_n = 1 + 1/2 + … + 1/n. সেই ফল এখানে আবার প্রমাণ করছি না; বরং তার ছোট ভাই দেখি।

Quickselect একটি তালিকার k-তম ছোট উপাদান খোঁজে, যেমন বাজারঘরের দিনের সব ডেলিভারি-সময়ের median. এলোমেলো pivot p নিয়ে বাকিদের “p-এর ছোট” আর “p-এর বড়” দুই ভাগ করে (s-টি উপাদানে s − 1টি তুলনা), তারপর শুধু যে ভাগে উত্তর আছে সেখানে এগোয়। Quicksort দুই ভাগেই নামে; quickselect নামে একটিতে। উত্তর সবসময় সঠিক, তাই এটি Las Vegas.

1. ভালো pivot: বর্তমান অংশে s-টি উপাদান থাকলে pivot-কে “ভালো” বলি যদি দুই ভাগের প্রতিটিতে ≤ 3s/4টি উপাদান থাকে। Pivot-এর rank r হলে শর্তটি s/4 ≤ r ≤ 3s/4 + 1, যা দৈর্ঘ্য s/2 + 1-এর একটি ব্যবধি; তাতে অন্তত s/2টি পূর্ণসংখ্যা। তাই P(ভালো) ≥ 1/2. — গোনা
2. দশা: অংশের আকার n(3/4)^j+1 থেকে বড় আর n(3/4)^j-এর সমান বা কম হলে algorithm “দশা j”-তে আছে। একটি ভালো pivot আকারকে 3/4 গুণ বা তার কম করে, তাই দশা j শেষ হয়। — সংজ্ঞা
3. প্রতি দশায় ধাপ: দশা j-তে প্রতিটি ধাপ স্বাধীনভাবে ≥ 1/2 সম্ভাবনায় ভালো, তাই দশাটি শেষ হতে প্রত্যাশিত ধাপ ≤ 2 (geometric বণ্টনের প্রত্যাশা 1/p, পর্ব ৪০)। — geometric বণ্টন
4. প্রতি ধাপের খরচ: দশা j-এর প্রতিটি ধাপে তুলনা ≤ n(3/4)^j. তাই দশা j-এর প্রত্যাশিত তুলনা ≤ 2n(3/4)^j. — ধাপ ২, ৩
5. যোগ: মোট তুলনা = দশাগুলোর তুলনার যোগ; linearity of expectation আর geometric series (পর্ব ১৭) থেকে E ≤ ∑_j≥0 2n(3/4)^j = 2n · 1/(1 − 3/4) = 8n. ∎ — linearity, পর্ব ১৭

ধাপ ৫-এর linearity of expectation দশাগুলোর স্বাধীনতা চায় না; সেটাই এর শক্তি। 8n একটি সহজ কিন্তু ঢিলা সীমা: median খুঁজতে আসল প্রত্যাশা প্রায় 2(1 + ln 2)n ≈ 3.39n বলে জানা যায় (Knuth-এর বিশ্লেষণ); আমাদের scratch simulation-এ n = 2001-এ ৪০০ run-এর গড় এসেছে প্রায় 3.42n. খারাপ ক্ষেত্র Θ(n²) এখনো সম্ভব, যদি প্রতিবার সবচেয়ে ছোট pivot ওঠে, কিন্তু তার সম্ভাবনা অতি ক্ষুদ্র। Lomuto/Hoare partition আর নিশ্চিত O(n)-এর median of medians DSA কোর্সের পর্ব ২২-এ।

৩ · Freivalds-এর matrix যাচাই — প্রতি round-এ ভুল ≤ 1/2

বাজারঘরের হিসাব বিভাগ একটি বাইরের সার্ভিসে দুটি বড় matrix A আর B পাঠায় (ধরুন গুদাম × পণ্য আর পণ্য × দাম-ধাপ), আর ফেরত পায় দাবি করা গুণফল C. নিজে AB গুণ করে মেলাতে matrix multiplication-এর সাধারণ পদ্ধতিতে n³টি গুণ লাগে (পর্ব ১৯ “Discrete math-এ matrix — 0-1 matrix আর Boolean product”). তাহলে যাচাই আর নতুন করে হিসাব সমান খরচের। Rūsiņš Freivalds ১৯৭৭ সালে দেখান, এলোমেলোতা দিয়ে যাচাই অনেক সস্তা।

C সত্যিই AB হলে A(Br) = (AB)r = Cr, তাই উত্তর সবসময় “ঠিক মনে হয়”: ভুল হয় শুধু এক দিকে, one-sided error. প্রশ্ন হলো C ভুল হলে কত ঘন ঘন ধরা পড়ে। নিচের stepper একটি 2 × 2 উদাহরণে চারটি সম্ভাব্য r-ই দেখায়।

1দাবি C₂₂ = 51, আসল 502r = (1, 0): Br = (5, 7)3A(Br) = (19, 43) = Cr4r = (0, 1): 50 ≠ 51 ✓5৪টি r-এর ২টি ঠকে: 1/26খরচ 3n² বনাম n³

1. D = AB − C ধরুন। D ≠ 0, তাই কোনো ঘর d_ij ≠ 0. আর A(Br) = Cr ⇔ Dr = 0. — matrix গুণের বণ্টন নিয়ম
2. Dr = 0 হলে বিশেষত তার i-তম উপাদান (Dr)_i = d_ijr_j + y = 0, যেখানে y = ∑_ℓ≠j d_iℓr_ℓ. তাই P(Dr = 0) ≤ P(d_ijr_j + y = 0). — monotonicity (পর্ব ৩৮)
3. আগে r_j ছাড়া বাকি সব r_ℓ-এর মান বসান; তাতে y একটি নির্দিষ্ট সংখ্যা। r_j স্বাধীন, তাই তার মান এখনো সমান সম্ভাবনায় 0 বা 1. এই কৌশলের নাম principle of deferred decisions: যে মুদ্রা দরকার, তা শেষে ছোড়া। — স্বাধীনতা
4. d_ijr_j + y = 0 মানে r_j = −y/d_ij: একটিমাত্র সংখ্যা। 0 আর 1-এর বড়জোর একটি তার সমান, তাই y-এর প্রতিটি মানে শর্তসাপেক্ষ সম্ভাবনা ≤ 1/2. — d_ij ≠ 0
5. সব y-এর ওপর গড় নিলে (total probability, পর্ব ৩৯) P(Dr = 0) ≤ 1/2. ∎ — law of total probability

উপপাদ্য ১.২ অনুযায়ী k স্বাধীন round-এ ভুল C ধরা না পড়ার সম্ভাবনা ≤ 2^−k. নিচের ব্লক একটি 5 × 5 উদাহরণে এটি মাপে। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

import random

def matmul(A, B):                      # ordinary product: n^3 multiplications
    n = len(A)
    return [[sum(A[i][k] * B[k][j] for k in range(n)) for j in range(n)]
            for i in range(n)]

def matvec(M, x):                      # n^2 multiplications
    return [sum(a * b for a, b in zip(row, x)) for row in M]

def freivalds_round(A, B, C):          # True means "C looks correct"
    r = [random.randint(0, 1) for _ in range(len(A))]
    return matvec(A, matvec(B, r)) == matvec(C, r)

random.seed(43)
n = 5
A = [[random.randint(0, 9) for _ in range(n)] for _ in range(n)]
B = [[random.randint(0, 9) for _ in range(n)] for _ in range(n)]
C = matmul(A, B)
C_bad = [row[:] for row in C]
C_bad[2][4] += 1                       # one wrong entry, off by 1

ok = sum(freivalds_round(A, B, C) for _ in range(1000))
print("correct C accepted:", ok, "of 1000 rounds")

trials = 10_000
for k in (1, 2, 3, 5, 8):
    fooled = sum(all(freivalds_round(A, B, C_bad) for _ in range(k))
                 for _ in range(trials))
    print(f"k = {k}: wrong C accepted {fooled / trials:.4f}"
          f"   bound 2^-k = {0.5 ** k:.4f}")
print("cost per round ~", 3 * n * n, "mults; full product", n ** 3)

correct C accepted: 1000 of 1000 rounds
k = 1: wrong C accepted 0.4974   bound 2^-k = 0.5000
k = 2: wrong C accepted 0.2506   bound 2^-k = 0.2500
k = 3: wrong C accepted 0.1159   bound 2^-k = 0.1250
k = 5: wrong C accepted 0.0358   bound 2^-k = 0.0312
k = 8: wrong C accepted 0.0046   bound 2^-k = 0.0039
cost per round ~ 75 mults; full product 125

৪ · Polynomial identity testing — Schwartz–Zippel

Freivalds-এর যুক্তির পেছনে একটি সাধারণ সত্য লুকিয়ে আছে: একটি অশূন্য polynomial খুব কম জায়গায় শূন্য হয়। ধরুন বাজারঘরের দুই প্রোগ্রামার একটি ডিসকাউন্ট সূত্র দুইভাবে লিখেছেন: একজন (x + 1)²⁰, অন্যজন তার বিস্তৃত রূপ ২১টি পদে। দুটি কি হুবহু একই polynomial? সব coefficient মেলানো যায়, কিন্তু বহু চলকের polynomial-এ বিস্তার করলে পদ সংখ্যা বিস্ফোরিত হয়। সহজ পথ: একটি এলোমেলো x বসিয়ে দুই পাশের মান মেলানো। এই প্রশ্নটির নাম polynomial identity testing.

বহু চলকের প্রমাণটি চলকের সংখ্যার ওপর induction, এখানে বাদ রাখছি (এটি DeMillo–Lipton, Zippel আর Schwartz-এর ১৯৭৮–৮০ সালের কাজে আলাদাভাবে আসে)। এক চলকের ক্ষেত্রটি পুরো প্রমাণ করি, কারণ বহু চলকের প্রমাণ এর ওপরই দাঁড়ায়।

1. ভিত্তি d = 0: p একটি অশূন্য ধ্রুবক, কোনো মূল নেই: 0 ≤ 0. — সরাসরি
2. অনুমান: degree d − 1-এর প্রতিটি অশূন্য polynomial-এর মূল ≤ d − 1টি। — induction (পর্ব ১০)
3. ধাপ: degree d-এর p-এর কোনো মূল না থাকলে দাবি সত্য। একটি মূল a থাকলে factor theorem অনুযায়ী p(x) = (x − a)q(x), যেখানে q-এর degree d − 1 আর q অশূন্য। — polynomial ভাগ
4. b ≠ a আরেকটি মূল হলে 0 = p(b) = (b − a)q(b), আর b − a ≠ 0. Field-এ দুটি অশূন্যের গুণফল অশূন্য, তাই q(b) = 0. অর্থাৎ a ছাড়া প্রতিটি মূল q-এর মূল, যা অনুমানে ≤ d − 1টি; মোট ≤ d. — field-এ zero divisor নেই
5. S-এর |S|টি সমান সম্ভাব্য মানের বড়জোর d-টি মূল, তাই P(p(r) = 0) ≤ d/|S|. ∎ — Laplace (পর্ব ৩৮)

ধাপ ৪-এ field-এর শর্তটি সত্যিই লাগে: ℤ₈-এ x² − 1-এর মূল চারটি (1, 3, 5, 7), degree মাত্র 2. তাই mod n-এ এই পরীক্ষা চালাতে n মৌলিক নিন (পর্ব ২২)। দুই প্রোগ্রামারের উদাহরণে পার্থক্য-polynomial p(x) = (x + 1)²⁰ − (বিস্তৃত রূপ)-এর degree ≤ 20. মৌলিক 1000003 নিয়ে ℤ_1000003 থেকে x বাছলে, সূত্র দুটি আলাদা হলে একই মান আসার সম্ভাবনা ≤ 20/1000003 ≈ 2 × 10⁻⁵, আর পাঁচটি স্বাধীন বিন্দুতে ≤ (2 × 10⁻⁵)⁵.

Freivalds এর একটি বিশেষ রূপ: r-কে চলক ভাবলে (Dr)_i হলো r₁, …, r_n-এর degree 1-এর একটি অশূন্য polynomial, আর S = {0, 1}, তাই সীমা 1/2. S বড় নিলে, যেমন {0, …, 99}, এক round-এই ভুল ≤ 1/100. Polynomial identity testing-এর একটি কৌতূহলজাগানো দিক “আরও গভীরে”-তে আছে: এর কোনো দক্ষ নির্ধারিত (deterministic) algorithm আজও জানা নেই।

৫ · Karger-এর min cut — এলোমেলো edge চেপে চেপে

বাজারঘরের গুদামগুলো রাস্তা দিয়ে যুক্ত একটি graph. প্রশ্ন: সবচেয়ে কম কয়টি রাস্তা বন্ধ হলে নেটওয়ার্ক দুই টুকরো হয়ে যায়? গুদামগুলোকে দুটি অখালি দলে ভাগ করলে যে রাস্তাগুলো দুই দলকে জোড়ে, সেগুলো একটি cut; সবচেয়ে ছোট cut-কে বলে global min cut. এটি নেটওয়ার্কের দুর্বলতম জায়গা। গ্রাফের সংজ্ঞা আর connectivity পর্ব ৫৭ “গ্রাফ — সংজ্ঞা, degree আর handshake theorem” আর পর্ব ৫৯ “Connectivity — path, component, cut vertex আর Menger-এর ধারণা”-এ বিস্তারিত আসবে; এখানে শুধু এটুকু লাগবে যে একটি vertex-এর degree মানে তার সঙ্গে যুক্ত edge-এর সংখ্যা, আর সব degree-র যোগফল 2|E|.

David Karger ১৯৯৩ সালে একটি অবিশ্বাস্য সরল algorithm দেন। একটি এলোমেলো edge বাছুন আর তার দুই প্রান্তকে এক vertex-এ জুড়ে দিন: এই কাজের নাম edge contraction. দুজনের মাঝের edge-গুলো self-loop হয়ে বাদ যায়, বাকি সব edge থেকে যায়, তাই একই দুই vertex-এর মাঝে একাধিক edge জমতে পারে: গ্রাফটি হয়ে যায় একটি multigraph. দুটি vertex বাকি না থাকা পর্যন্ত এভাবে চালান; শেষে দুই “মহা-vertex”-এর মাঝের edge-গুলোই উত্তরের cut. এটি Karger-এর algorithm.

1. |K| = c ধরুন। প্রতিটি vertex v-এর degree ≥ c, কারণ “v একা বনাম বাকি সব” নিজেই একটি cut, আর তার আকার deg(v). — min cut-এর সংজ্ঞা
2. তাই |E| = (সব degree-র যোগ)/2 ≥ nc/2, আর প্রথম এলোমেলো edge K-এর হওয়ার সম্ভাবনা ≤ c/(nc/2) = 2/n. — handshake, Laplace
3. K-এর কোনো edge না চাপা পর্যন্ত K নতুন multigraph-এও একটি cut, আর contraction কোনো নতুন cut বানায় না (প্রতিটি নতুন cut পুরোনো গ্রাফের একটি cut), তাই min cut তখনো c. i-টি contraction-এর পরে n − i-টি vertex, প্রতিটির degree ≥ c, edge ≥ (n − i)c/2. — ধাপ ১, ২-এর একই যুক্তি
4. E_i = “(i + 1)-তম contraction K-এর edge চাপে না”. আগের সব ধাপে K টিকে থাকলে P(E_i | আগের সব) ≥ 1 − 2/(n − i). — ধাপ ৩
5. Chain rule (পর্ব ৩৯): P(K শেষ পর্যন্ত টেকে) ≥ ∏_i=0ⁿ⁻³ (n − i − 2)/(n − i) = (n − 2)/n · (n − 3)/(n − 1) · … · 1/3. লবের প্রতিটি সংখ্যা দুই ধাপ পরে হরে কাটে, বাকি থাকে 2·1/(n(n − 1)). ∎ — telescoping গুণফল

একটি run-এ সাফল্য ছোট, যেমন n = 8-এ মাত্র 1/28. কিন্তু স্বাধীনভাবে T বার চালিয়ে সবচেয়ে ছোট cut রাখলে ব্যর্থতার সম্ভাবনা ≤ (1 − 1/C(n, 2))^T ≤ e^{−T/C(n, 2)}, অসমতা 1 − x ≤ e^−x থেকে (পর্ব ৪২ “Birthday paradox, hash collision আর balls-into-bins”-এ এর প্রমাণ)। T = C(n, 2) · ln n হলে ব্যর্থতা ≤ 1/n. এটিও একটি Monte Carlo algorithm: উত্তর কখনো min cut-এর চেয়ে ছোট হয় না, কিন্তু বড় হতে পারে।

import random
from math import comb, log

# two 4-depot clusters (complete inside), joined by 2 roads
E = [(a, b) for a in range(4) for b in range(a + 1, 4)]
E += [(a, b) for a in range(4, 8) for b in range(a + 1, 8)]
E += [(0, 4), (3, 7)]
n = 8

def karger(edges, n):                 # contract until 2 groups remain
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            x = parent[x]
        return x
    order = edges[:]
    random.shuffle(order)             # random order = random edge each time
    groups = n
    for u, v in order:
        ru, rv = find(u), find(v)
        if groups > 2 and ru != rv:   # skip self-loops
            parent[ru] = rv
            groups -= 1
    return sum(find(u) != find(v) for u, v in edges)

random.seed(43)
runs = 5000
results = [karger(E, n) for _ in range(runs)]
best = min(results)
print("edges:", len(E), "  smallest cut found:", best)
print(f"P(one run finds it) ~ {results.count(best) / runs:.4f}"
      f"   bound 1/C(8,2) = {1 / comb(n, 2):.4f}")
T = round(comb(n, 2) * log(n))
print(f"T = {T}: P(all fail) <= {(1 - 1 / comb(n, 2)) ** T:.4f}")

edges: 14   smallest cut found: 2
P(one run finds it) ~ 0.2094   bound 1/C(8,2) = 0.0357
T = 58: P(all fail) <= 0.1213

৬ · Probabilistic method — Erdős-এর Ramsey সীমা

এতক্ষণ এলোমেলোতা ছিল algorithm-এর হাতিয়ার। এবার তা হলো প্রমাণের হাতিয়ার। পর্ব ৯ “প্রমাণের কৌশল — case, existence, uniqueness আর counterexample”-এ দেখেছেন, একটি existence proof বস্তুটি না দেখিয়েও তার অস্তিত্ব প্রমাণ করতে পারে। Probabilistic method এর একটি শক্তিশালী রূপ।

সবচেয়ে বিখ্যাত প্রয়োগটি Ramsey সংখ্যায়। পর্ব ৩২ “Pigeonhole principle — সহজ থেকে generalized”-এ দেখেছেন, ছয়জনের যেকোনো দলে তিনজন পরস্পর পরিচিত বা তিনজন পরস্পর অপরিচিত: R(3, 3) = 6. সাধারণভাবে Ramsey number R(k, k) হলো সবচেয়ে ছোট N, যাতে complete graph K_N-এর edge-গুলো লাল-নীলে যেভাবেই রাঙানো হোক, k-টি vertex-এর একটি একরঙা K_k থাকবেই। R(k, k) > n প্রমাণ করতে হলে K_n-এর এমন একটি রং দেখাতে হয়, যাতে কোনো একরঙা K_k নেই। বড় k-তে এমন রং হাতে বানানো কঠিন। Paul Erdős ১৯৪৭ সালে রং না বানিয়েই প্রমাণ করেন যে তা আছে।

1. K_n-এর প্রতিটি edge স্বাধীনভাবে 1/2 সম্ভাবনায় লাল বা নীল করুন; Ω = সব 2^{C(n, 2)} রং, সমান সম্ভাব্য। — মডেল
2. একটি নির্দিষ্ট k-vertex সেট S-এর ভেতরে C(k, 2)টি edge. S একরঙা মানে সব লাল বা সব নীল: P(A_S) = 2 · 2^{−C(k, 2)} = 2^{1 − C(k, 2)}. — স্বাধীন edge
3. k-vertex সেট C(n, k)টি। Union bound: P(কোনো একরঙা K_k আছে) ≤ ∑_S P(A_S) = C(n, k) · 2^{1 − C(k, 2)} < 1. — union bound (পর্ব ৩৮)
4. তাই P(কোনো একরঙা K_k নেই) > 0, আর নীতি ৬.১ অনুযায়ী এমন রং আছে: R(k, k) > n. — নীতি ৬.১
5. বিশেষ ক্ষেত্র: n = ⌊2^k/2⌋ হলে C(n, k) ≤ n^k/k! ≤ 2^k²/2/k!, তাই সীমা ≤ 2^{k²/2 + 1 − k(k−1)/2}/k! = 2^{1 + k/2}/k!, যা k ≥ 3-এ 1-এর কম (k = 3-এ 2^2.5/6 ≈ 0.94, আর k বাড়লে k! দ্রুত বাড়ে)। ∎ — বীজগণিত

প্রমাণটি একটিও রং দেখায় না, শুধু বলে “বেশিরভাগ রংই ভালো”. নিচের stepper k = 10-এর হিসাব ধাপে ধাপে করে।

1k = 10, n = 2^(k/2) = 322C(32, 10) = 64512240 সেট3এক সেট একরঙা: 2^(1−45)4union bound ≈ 3.67 × 10⁻⁶5< 1 ⇒ R(10, 10) > 326n = 100: 0.984 < 1

নিচের ব্লক দুটি কাজ করে: প্রতিটি k-এর জন্য সবচেয়ে বড় n খোঁজে যেখানে উপপাদ্য ৬.২-এর শর্ত মেটে, আর k = 4, n = 6-এ K₆-এর সব 2¹⁵ = 32768টি রং গুনে দেখে কতগুলো সত্যিই “ভালো” (একরঙা K₄-হীন), union bound-এর নিচের সীমার তুলনায়।

from fractions import Fraction
from itertools import combinations
from math import comb

def first_moment(n, k):               # E[# one-colour K_k] in random colouring
    return Fraction(comb(n, k) * 2, 2 ** comb(k, 2))

for k in (4, 6, 8, 10):
    n = k
    while first_moment(n + 1, k) < 1:
        n += 1
    print(f"k = {k:>2}: largest n with E < 1 is {n:>3}"
          f"  -> R(k,k) > {n}   (2^(k/2) = {2 ** (k / 2):.1f})")

# k = 4, n = 6: check every one of the 2^15 colourings of K6
n, k = 6, 4
edges = list(combinations(range(n), 2))
quads = [[edges.index(e) for e in combinations(q, 2)]
         for q in combinations(range(n), k)]
good = 0
for mask in range(2 ** len(edges)):
    bits = [(mask >> i) & 1 for i in range(len(edges))]
    if all(len({bits[i] for i in q}) == 2 for q in quads):
        good += 1                     # no one-colour K4
print("K6 colourings:", 2 ** len(edges), " good:", good,
      f" share {good / 2 ** len(edges):.4f}")
print("union bound: P(good) >=", 1 - first_moment(n, k),
      f"= {float(1 - first_moment(n, k)):.4f}")

k =  4: largest n with E < 1 is   6  -> R(k,k) > 6   (2^(k/2) = 4.0)
k =  6: largest n with E < 1 is  17  -> R(k,k) > 17   (2^(k/2) = 8.0)
k =  8: largest n with E < 1 is  42  -> R(k,k) > 42   (2^(k/2) = 16.0)
k = 10: largest n with E < 1 is 100  -> R(k,k) > 100   (2^(k/2) = 32.0)
K6 colourings: 32768  good: 22484  share 0.6862
union bound: P(good) >= 17/32 = 0.5312

৭ · প্রত্যাশার যুক্তি — MAX-CUT, derandomization আর MAX-3SAT

Probabilistic method-এর দ্বিতীয় রূপটি সম্ভাবনার বদলে প্রত্যাশা ব্যবহার করে, আর প্রায়ই আরও সহজ।

1. বিপরীতে ধরুন প্রতিটি outcome ω-তে X(ω) < μ. — contradiction-এর অনুমান
2. তাহলে E[X] = ∑_ω X(ω)p(ω) < ∑_ω μ · p(ω) = μ, কারণ ভারগুলো অঋণাত্মক, যোগফল 1, আর অন্তত একটি ভার ধনাত্মক। — প্রত্যাশার সংজ্ঞা
3. E[X] < μ, বিরোধ। দ্বিতীয় অংশ একইভাবে। ∎ — বিরোধ

MAX-CUT. একটি গ্রাফের vertex-গুলোকে দুই দলে ভাগ করে দুই দলের মাঝের edge সর্বোচ্চ করার সমস্যা MAX-CUT. বাজারঘরের ভাষায়: গুদামগুলোকে দুটি ডেলিভারি অঞ্চলে ভাগ করুন যাতে সবচেয়ে বেশি রাস্তা দুই অঞ্চলের মাঝে পড়ে (যেমন দুই অঞ্চলের গাড়ি যাতে একই রাস্তায় ভিড় না করে)। Karger-এর min cut-এর উল্টো দিক, আর আসলে অনেক কঠিন: MAX-CUT একটি NP-hard সমস্যা (DSA কোর্সের পর্ব ৬৪)।

1. প্রতিটি vertex স্বাধীনভাবে 1/2 সম্ভাবনায় বাঁ (L) বা ডান (R) দলে দিন। X = cut-এর edge সংখ্যা। — মডেল
2. প্রতিটি edge e = uv-এর জন্য indicator X_e = 1 যদি u আর v ভিন্ন দলে। চারটি সমান সম্ভাব্য (u, v) জোড়ার দুটিতে ভিন্ন দল, তাই E[X_e] = 1/2. — E[I_A] = P(A)
3. X = ∑_e X_e, তাই linearity থেকে E[X] = m/2; edge-গুলো স্বাধীন না হলেও (একই vertex ভাগ করে) এটি সত্য। — linearity of expectation
4. লেমা ৭.১: কোনো ভাগে X ≥ m/2. ∎ — লেমা ৭.১

1a–b–c–d–a: m = 4, ১৬ ভাগ2P(ab কাটা) = 1/23E[X] = 4 × 1/2 = 2 = m/24cut 0, 2, 4: ২, ১২, ২টি5কোথাও ≥ 2; সর্বোচ্চ 46greedy: R, L, R, L

এলোমেলোতা ছাড়াই। Stepper-এর শেষ ধাপটি একটি সাধারণ কৌশল, method of conditional expectations, যা derandomization-এর (randomized যুক্তিকে নির্ধারিত algorithm-এ রূপ দেওয়া) সবচেয়ে সহজ উদাহরণ। ধারণাটি: vertex v₁, …, v_n একে একে বসানো হচ্ছে; আগের সব বসানো ঠিক রেখে বাকিগুলো এলোমেলো রাখলে cut-এর শর্তসাপেক্ষ প্রত্যাশা W. v-এর দুই পছন্দের প্রত্যাশার গড় ঠিক W (পর্ব ৩৯-এর total probability), তাই অন্তত একটি পছন্দ W কমায় না। শুরুতে W = m/2, আর প্রতিটি ধাপে তা কমে না, তাই শেষে, যখন কিছুই এলোমেলো নেই, cut ≥ m/2. v-এর পছন্দে শুধু v আর আগে বসানো প্রতিবেশীর edge-এর প্রত্যাশা বদলায়, তাই “আগে বসানো প্রতিবেশীদের বেশি অংশ যেদিকে নেই, সেদিকে বসান” নিয়মটিই যথেষ্ট। নিচের ব্লক বাজারঘরের সাতটি গুদামের নেটওয়ার্কে দুটিই করে।

from fractions import Fraction
from itertools import product

# warehouse network: 7 depots (0..6), 11 roads
E = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 4), (3, 4),
     (3, 5), (4, 5), (4, 6), (5, 6), (0, 6)]
n, m = 7, len(E)
nbr = {v: [] for v in range(n)}
for u, v in E:
    nbr[u].append(v)
    nbr[v].append(u)

def cut(side):                        # roads whose ends are on different sides
    return sum(side[u] != side[v] for u, v in E)

sizes = [cut(s) for s in product((0, 1), repeat=n)]   # all 2^7 assignments
print("assignments:", len(sizes), "  m =", m)
print("exact E[cut] =", Fraction(sum(sizes), len(sizes)),
      "  m/2 =", Fraction(m, 2))
print("max cut =", max(sizes), "  P(cut >= m/2) =",
      Fraction(sum(c >= m / 2 for c in sizes), len(sizes)))

# derandomise: place depots in order, each on the side that cuts more
side = {}
for v in range(n):
    placed = [side[u] for u in nbr[v] if u in side]
    side[v] = 1 if placed.count(0) >= placed.count(1) else 0
    print(f"depot {v}: neighbours placed {placed} -> side {side[v]}")
s = [side[v] for v in range(n)]
print("greedy sides:", s, "  cut =", cut(s), ">= m/2 =", m / 2)

assignments: 128   m = 11
exact E[cut] = 11/2   m/2 = 11/2
max cut = 9   P(cut >= m/2) = 35/64
depot 0: neighbours placed [] -> side 1
depot 1: neighbours placed [1] -> side 0
depot 2: neighbours placed [1, 0] -> side 1
depot 3: neighbours placed [0] -> side 1
depot 4: neighbours placed [1, 1] -> side 0
depot 5: neighbours placed [1, 0] -> side 1
depot 6: neighbours placed [0, 1, 1] -> side 0
greedy sides: [1, 0, 1, 1, 0, 1, 0]   cut = 8 >= m/2 = 5.5

MAX-3SAT. একই যুক্তি যুক্তিবিদ্যায়। একটি 3-CNF সূত্রে প্রতিটি clause তিনটি ভিন্ন চলকের তিনটি literal-এর “অথবা” (CNF আর satisfiability: পর্ব ৩ “Logical equivalence — De Morgan, normal form আর satisfiability”; আসল SAT solver: পর্ব ৭ “কাজে যুক্তি — specification, ধাঁধা আর SAT solver”). 3-SAT জিজ্ঞেস করে সব clause একসঙ্গে মেটানো যায় কি না; MAX-3SAT জিজ্ঞেস করে সর্বোচ্চ কয়টি মেটানো যায়।

1. প্রতিটি চলক স্বাধীনভাবে 1/2 সম্ভাবনায় সত্য বা মিথ্যা। একটি clause মেটে না শুধু যখন তার তিনটি literal-ই মিথ্যা: 8টি সমান সম্ভাব্য মান-জোড়ার একটি, সম্ভাবনা 1/8. তাই clause-এর indicator-এর প্রত্যাশা 7/8. — তিনটি ভিন্ন চলক, স্বাধীনতা
2. Linearity: মেটানো clause-এর প্রত্যাশিত সংখ্যা 7m/8; লেমা ৭.১ থেকে কোনো মান-বসানোয় অন্তত 7m/8. — linearity, লেমা ৭.১
3. m ≤ 7 হলে 7m/8 > m − 1 (কারণ m < 8), আর মেটানো clause-এর সংখ্যা একটি পূর্ণসংখ্যা ≥ 7m/8, তাই তা m: সব clause মেটে। ∎ — পূর্ণসংখ্যার যুক্তি

সীমা 7/8 উন্নত করা যায় না, এমন সূত্রও আছে: x, y, z-এর ৮টি সম্ভাব্য চিহ্ন-বিন্যাসের ৮টি clause (x ∨ y ∨ z), (x ∨ y ∨ ¬z), …, (¬x ∨ ¬y ∨ ¬z) নিন। প্রতিটি মান-বসানো ঠিক একটি clause ভাঙে (যেটির সব literal তার উল্টো), তাই প্রতিটিতে ঠিক ৭টি মেটে; scratch-এ ৮টি মান-বসানোই গুনে মেলানো। আর m = 8-এ সূত্রটি unsatisfiable, তাই “m ≤ 7” শর্তটিও সঠিক সীমা।

৮ · এলোমেলোতার উৎস, পরীক্ষার অঙ্ক আর একটি ভুল যুক্তি

প্রতিটি প্রমাণে আমরা ধরে নিয়েছি মুদ্রাগুলো সত্যিই ন্যায্য আর স্বাধীন। কম্পিউটারে মুদ্রা আসে একটি pseudorandom number generator থেকে: একটি নির্দিষ্ট সূত্র, যা একটি শুরুর মান বা seed থেকে এলোমেলো দেখতে সংখ্যার ধারা বানায় (পর্ব ২৬ “সংখ্যাতত্ত্বের প্রয়োগ — check digit, hashing আর pseudorandom সংখ্যা”-এর LCG). এই পর্বের এলোমেলো ব্লকগুলোতে random.seed(43): একই seed মানে একই ধারা, তাই আউটপুট বারবার হুবহু মেলে। Simulation আর পরীক্ষার জন্য এটিই চাই।

দুই ধরনের কাজে প্রয়োজন আলাদা। Freivalds বা Karger-এর মতো algorithm-এ প্রতিপক্ষ সাধারণত seed জানে না, আর Python-এর random (Mersenne Twister) পরিসংখ্যানের দিক থেকে যথেষ্ট ভালো। কিন্তু কুপন কোড, OTP বা পাসওয়ার্ড-রিসেট টোকেনে প্রতিপক্ষ আগের আউটপুট দেখে পরেরটি অনুমান করতে চায়; সেখানে CSPRNG লাগে, যেমন Python-এর secrets module. বিস্তারিত Cybersecurity কোর্সের পর্ব ০৭-এ।

অঙ্ক ১: Schwartz–Zippel দিয়ে কয়টি বিন্দু

degree 40-এর দুটি polynomial সমান কি না, S = {1, …, 1000} থেকে এলোমেলো বিন্দু নিয়ে যাচাই করা হচ্ছে। এক বিন্দুতে ভুলের সীমা 40/1000 = 0.04. ভুল ≤ 10⁻⁶ করতে কয়টি স্বাধীন বিন্দু লাগে?

1. k বিন্দুতে ভুল ≤ 0.04^k (উপপাদ্য ১.২, কারণ “আলাদা” উত্তর সবসময় সঠিক)।
2. 0.04⁴ = 2.56 × 10⁻⁶ > 10⁻⁶, কিন্তু 0.04⁵ ≈ 1.02 × 10⁻⁷ ≤ 10⁻⁶.
3. উত্তর: ৫টি বিন্দু।

অঙ্ক ২: Karger-এ কয়টি run

৫টি vertex-এর একটি গ্রাফে Karger চালানো হবে। একটি নির্দিষ্ট min cut না পাওয়ার সম্ভাবনা ≤ 0.05 করতে সর্বনিম্ন কয়টি স্বাধীন run নিশ্চিতভাবে যথেষ্ট (উপপাদ্য ৫.১-এর সীমা দিয়ে)?

1. এক run-এ সাফল্য ≥ 2/(5 · 4) = 1/10, তাই T run-এ ব্যর্থতা ≤ (9/10)^T.
2. (0.9)²⁸ ≈ 0.0523 > 0.05, (0.9)²⁹ ≈ 0.0471 ≤ 0.05.
3. উত্তর: ২৯ বার চালানো।

অঙ্ক ৩: MAX-3SAT-এর নিশ্চয়তা

২০টি clause-এর একটি 3-CNF (প্রতি clause-এ তিনটি ভিন্ন চলক)। সবসময় অন্তত কয়টি clause একসঙ্গে মেটানো যায়? উত্তর: 7 × 20/8 = 17.5, আর মেটানো clause-এর সংখ্যা পূর্ণসংখ্যা, তাই অন্তত ১৮টি।

যুক্তির ভুল ধরুন: “একই seed, দশ round”

একজন Freivalds-এর ভুল কমাতে এই কোড লিখলেন আর দাবি করলেন, “১০ round চালিয়েছি, তাই ভুল C ধরা না পড়ার সম্ভাবনা ≤ 2⁻¹⁰ = 1/1024.”

for _ in range(10):
    random.seed(7)                  # reset "for reproducibility"
    if not freivalds_round(A, B, C):
        print("C is wrong"); break

ভুল কোথায়: উপপাদ্য ১.২-এর ধাপ ২ স্বাধীন run চায়। কিন্তু প্রতি round-এর আগে seed 7-এ ফেরানো হয়েছে, তাই দশবারই হুবহু একই r. প্রথম round ঠকলে বাকি নয়টিও ঠকে: ভুলের সম্ভাবনা এখনো ১ round-এর সমান, 1/2 পর্যন্ত, 1/1024 নয়। এক round-এর ভুলের ঘটনা E₁ হলে এখানে E₁ = E₂ = … = E₁₀, আর P(E₁ ∩ … ∩ E₁₀) = P(E₁). Seed ঠিক করুন একবার, পুরো পরীক্ষার শুরুতে, প্রতিটি round-এর আগে নয়।

৯ · AI-এর যুগে — randomized যুক্তি যাচাই

Randomized algorithm আর probabilistic method-এর প্রমাণ ছোট আর মসৃণ, তাই AI সহকারী এগুলো আত্মবিশ্বাসের সঙ্গে লেখে। ভুলগুলো সাধারণত একটি শব্দে লুকিয়ে থাকে: “স্বাধীন”, “প্রত্যাশা”, “অন্তত”. এই পর্বের বিষয়ে কয়েকটি ভুল নিয়মিত দেখা যায়:

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

• যেখানে স্বাধীনতা ব্যবহার হয়েছে, সেখানে run-গুলো সত্যিই আলাদা এলোমেলো bit পায় কি না দেখেছি
• “প্রত্যাশা থেকে অস্তিত্ব” আর “প্রত্যাশা থেকে সবসময়” আলাদা করেছি
• ছোট ক্ষেত্রে (৪–৭টি vertex, ৩টি চলক) সব outcome গুনে দাবিটি মিলিয়েছি
• প্রতিটি উপপাদ্যের শর্ত, যেমন field বা ভিন্ন চলক, লেখা আছে কি না দেখেছি
• Seed দেওয়া simulation-এর হার প্রমাণিত সীমার সঙ্গে মিলিয়েছি
• উদ্ধৃত সাল, নাম আর Ramsey সংখ্যার মান বিশ্বস্ত উৎসে মিলিয়েছি

এই পর্বের সব যুক্তি একটি ছোট সরঞ্জাম-বাক্স থেকে এসেছে: union bound, স্বাধীন ঘটনার গুণ, chain rule আর linearity of expectation. AI-এর যুক্তি পড়ার সময় প্রতিটি ধাপে জিজ্ঞেস করুন, এখানে এই চারটির কোনটি খাটানো হলো, আর তার শর্ত মেটে কি না। তাহলে বেশিরভাগ ভুল নিজেই ধরা পড়ে।