ความน่าจะเป็นของการได้บอลจำนวนคี่

Question

เรามี $n$ ลูกบอลเช่นนั้น $k \ge 1$ส่วนที่เหลือเป็นสีขาว พิจารณาขั้นตอนต่อไปนี้:

ก่อนอื่นเราใส่ลูกบอลทั้งหมดลงในถัง $B_0$. จากนั้นเราเลือกแต่ละรายการด้วยความน่าจะเป็น$1/2$ และใส่สิ่งที่เลือกไว้ $B_1$. ต่อไปเราจะเลือกบอลแต่ละลูก$B_1$ ด้วยความน่าจะเป็น $1/2$ และใส่สิ่งที่เลือกไว้ $B_2$. เราทำต่อไปเพื่อ$\Theta(\log{n})$ การทำซ้ำ

อะไรคือความน่าจะเป็นที่ถังเหล่านี้อย่างน้อยหนึ่งลูกมีลูกบอลสีดำจำนวนคี่?

ถ้า $k$ มันเป็นเรื่องแปลกแล้วมันก็ง่ายที่จะเห็นว่าความน่าจะเป็นคือ $1$แต่เราจะวิเคราะห์ได้อย่างไรเมื่อ $k$ เป็นคู่?

Answer 1

ฉันจะใช้คำว่ารอบ $i$ เพื่ออธิบายการย้ายไปที่ถัง $B_i$. สังเกตว่าความน่าจะเป็นของการเคลื่อนย้ายลูกบอลสีดำจำนวนเท่ากันในรอบใด$\frac{1}{2}$ เนื่องจากคุณสามารถย้ายครั้งแรกได้ $x-1$ลูกบอลแบบสุ่มแล้วเลือกอันสุดท้ายเพื่อแก้ไขความเท่าเทียมกัน นอกจากนี้โปรดทราบว่าหากคุณมีลูกบอลจำนวนเท่ากันทั้งหมด$B_{k}$ จนถึง $i$ และคุณย้ายเลขคู่จาก $B_{i}$ ถึง $B_{i+1}$คุณโอเค ที่เกิดขึ้นด้วยความน่าจะเป็น$\frac{1}{2}^i$.

ดังนั้นคำตอบสุดท้ายคือ $1 - \frac{1}{2}^{\Theta (\text{log}n)}$