418531 ภาคต้น 2552/โจทย์ปัญหาความน่าจะเป็น II/เฉลยข้อ 4

ข้อ 1

ปัญหานี้คือปัญหา Coupon Collector Problem ฉะนั้นเราได้ว่าจำต้องตึงไพ่ประมาณ $nH_{n}=\Theta (n\log n)\,$ ใบจนกว่าจะเห็นไพ่ครบ

ข้อ 2

ให้ $X_{i}$ เป็น indicator random variable ที่ $X_{i}$ มีค่าเป็น 1 ถ้าไพ่ใบที่ i ไม่เคยถูกดึงออกมาเลยในการดึงทั้ง $2n\,$ ครั้ง

ให้ $X$ เป็น random variable ที่มีค่าเท่ากับจำนวนไพ่ที่ไม่เคยถูกดึงออกมาเลยในการดึงทั้ง $2n\,$ ครั้ง เราได้ว่า $X=X_{1}+X_{2}+\dotsb +X_{n}\,$ ฉะนั้น $E[X]=E[X_{1}]+E[X_{2}]+\dotsb +E[X_{n}]\,$

พิจารณาตัวแปรสุ่ม $X_{i}\,$ แต่ละตัว เราได้ว่า $E[X_{i}]\,$ มีค่าเท่ากับความน่าจะเป็นที่ไพ่ใบที่ i ไม่เคยถูกดึงออกมาเลยในการดึง $2n\,$ ครั้ง เนื่องจากในการดึงแต่ละครั้ง ไพ่ใบที่ i มีโอการไม่ถูกเลือกเท่ากับ $1-{\frac {1}{n}}\,$ เราได้ว่าความน่าจะเป็นที่ไพ่ใบที่ i จะไม่ถูกถึงเลยตลอดการดึงไพ่ $2n\,$ ครั้งมีค่าเท่ากับ ${\bigg (}1-{\frac {1}{n}}{\bigg )}^{2n}\approx e^{-2}$

ฉะนั้น จำนวนไพ่ที่ไม่ถูกดึงออกมาเลยโดยเฉลี่ยจึงมีค่าเท่ากับ $E[X]=n{\bigg (}1-{\frac {1}{n}}{\bigg )}^{2n}\approx {\frac {n}{e^{2}}}$

ข้อ 3

ให้ $X_{i}$ เป็น indicator random variable ที่ $X_{i}$ มีค่าเป็น 1 ถ้าไพ่ใบที่ i ถูกเลือกออกมาจากกองเพียงครั้งเดียวเท่านั้น

ให้ $X$ เป็น random variable ที่มีค่าเท่ากับจำนวนไพ่ที่ไม่ที่ถูกดึงออกมาเพียงครั้งเดียวในการดึงทั้ง $2n\,$ ครั้ง เราได้ว่า $X=X_{1}+X_{2}+\dotsb +X_{n}\,$ ฉะนั้น $E[X]=E[X_{1}]+E[X_{2}]+\dotsb +E[X_{n}]\,$

พิจารณาตัวแปรสุ่ม $X_{i}\,$ แต่ละตัว เราได้ว่า $E[X_{i}]\,$ มีค่าเท่ากับความน่าจะเป็นที่ไพ่ใบที่ i ถูกดึงออกมาเพียงครั้งเดียวเท่านั้น

ในการดึงทั้ง $2n\,$ เรามีวิธีกำหนดครั้งที่ไพ่ใบที่ i จะถูกดึงออกมาอยู่ได้ $2n\,$ วิธี ในการดึงอีก $2n-1\,$ ครั้งที่เลือก แต่ละครั้งไพ่จะเป็นไพ่อะไรก็ได้ที่ไม่ใช่ไพ่หมายเลข i ดังนั้นจึงมีวิธีกรดึงไพ่ให้ไพ่ใบที่ i ถูกดึงออกมาเพียงครั้งเดียวอยู่ $2n(n-1)^{2n-1}={\frac {2n}{n-1}}(n-1)^{2n}$ วิธี เนื่องจากวิธีการดึงไพ่แบบต่างๆ มีความน่าจะเป็นเท่าๆ กันคือ ${\frac {1}{n^{2n}}}$ เราได้ว่าความน่าจะเป็นที่ไพ่หมายเลข i จะถูกดึงออกมาเพียงครั้งเดียวมีค่าเท่ากับ ${\frac {2n}{n-1}}{\frac {(n-1)^{2n}}{n^{2n}}}={\frac {2n}{n-1}}{\bigg (}1-{\frac {1}{n}}{\bigg )}^{2n}\approx 2e^{-2}$

ฉะนั้น จำนวนไพ่ที่ถูกดึงออกเพียงหนึ่งครั้งโดยเฉลี่ยจึงมีค่าเท่ากับ $E[X]=n{\frac {2n}{n-1}}{\bigg (}1-{\frac {1}{n}}{\bigg )}^{2n}\approx {\frac {2n}{e^{2}}}$