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

ข้อ 1

[Mitzenmacher & Upfal 2.2] ลิงตัวหนึ่งพิมพ์แป้นพิมพ์ดีดที่มีแป้นพิมพ์อยู่ 26 ตัวซึ่งตรงกับตัวอักษรภาษาอังกฤษตัวเล็กทั้ง 26 ตัว โดยที่ตัวอักษรที่ลิงพิมพ์แต่ละตัวถูกเลือกขึ้นมาอย่างๆ สุ่มๆ โดยที่ตัวอักษรแต่ละตัวมีโอกาสได้รับเลือกเท่าๆ กัน และการพิมพ์แต่ละครั้งเป็นอิสระจากการพิมพ์ครั้งอื่นๆ ถ้าลิืงพิมพ์ตัวอักษรไปทั้งหมด 1,000,000 ตัวอักษร จงหาจำนวนที่คำว่า "proof" จะปรากฎอยู่ในข้อความที่ลิงพิมพ์ออกมานี้

เฉลย

ข้อ 2

[Mitzenmacher & Upfal 2.6] โยนลูกเต๋าไม่ถ่วงน้ำหนักหนึ่งลูกสองครั้ง แต่ละครั้งเป็นอิสระจากกัน ให้ $X_{1}\,$ เป็นแต้มของการโยนครั้งแรก $X_{2}\,$ เป็นแต้มของการโยนครั้งที่สอง และให้ $X\,$ เป็นผลบวกของแต้มทั้งสอง จงหาค่า

1. $E[X\ |\ X_{1}{\mbox{ is even}}]\,$
2. $E[X\ |\ X_{1}=X_{2}]\,$
3. $E[X_{1}\ |\ X=9]\,$
4. $E[X_{1}-X_{2}\ |\ X=k]\,$ เมื่อ k อยู่ในช่วง [2, 12]

เฉลย

ข้อ 3

[Mitzenmacher & Upfal 2.7] ให้ X และ Y เป็น geometric random variable ที่เป็นอิสระจากกัน โดยที่ X มี parameter p และ Y มี parameter q

1. จงหาความน่าจะเป็นที่ X = Y
2. จงหา $E[\max(X,Y)]\,$
3. จงหา $\Pr(\min(X,Y)=k)\,$
4. จงหา $E[X\ |\ X\leq Y]\,$

เฉลย

ข้อ 4

[Mitzenmacher & Upfal 2.12] เราทำการดึงไพ่อย่างสุ่มๆ ออกจากกองไพ่ที่มีไพ่อยู่ n ใบ โดยเมื่อดึงออกมาแล้วใส่กลับเข้าไปในกองใหม่

1. เราจะต้ัองดึงไพ่ออกมาประมาณกี่ครั้งจนกว่าจะเราเคยเห็นไพ่ครบทั้ง n ใบ
2. ถ้าเราทำการดึงไพ่ออกมา 2n ครั้ง จงหาจำนวนไพ่ที่ไม่เคยถูกดึงออกมาจากกองเลยโดยเฉลี่ย
3. ถ้าเราทำการดึงไพ่ออกมา 2n ครั้ง จงหาจำนวนไพ่ที่ถูกดึงออกมาจากกองเพียงครั้งเดียวเท่านั้น

เฉลย

ข้อ 5

[Mitzenmacher & Upfal 2.14] โยนเหรียญถ่วงน้ำหนักที่ขึ้นหัวด้วยความน่าจะเป็น p ไปเรื่อยๆ ให้ X เป็นจำนวนการโยนเหรียนจนกระทั่งหัวครั้งที่ k ออกมา จงแสดงว่า $\Pr(X=n)={n-1 \choose k-1}p^{k}(1-p)^{n-k}\,$

เฉลย

ข้อ 6

[Mitzenmacher & Upfal 2.18] พิจารณากระบวนการสุ่มต่อไปนี้: มีไพ่อยู่ n ใบ ซึ่งมีหมายเลข 1 ถึง n ติดอยู่ ขั้นแรกผมหยิบไพ่หมายเลข 1 ส่งให้คุณ แล้วคุณเก็บไว้ หลังจากนั้นผมส่งไพ่หมายเลข 2 ให้คุณ โดยคุณทำการตัดสินใจเก็บไพ่หมายเลข 2 แทนไพ่ที่คุณเก็บไว้ในปัจจุบันด้วยความน่าจะเป็น 1/2 หลังจากนั้นผมจึงส่งไพ่หมายเลข 3, 4, 5, ... ให้ตามลำดับจนกระทั่งครบทั้ง n ใบ โดยเมื่อผมส่งไพ่หมายเลข k ให้คุณ คุณจะเลือกเก็บไพ่หมายเลข k แทนไพ่ที่เก็บไว้ในปัจจุบันด้วยความน่าจะเป็น 1/k

จงแสดงไพ่ท้ายสุดเลย ไพ่ทุกใบมีโอกาสที่จะเป็นไพ่ที่คุณเก็บไว้ใบสุดท้ายเท่าๆ กัน

เฉลย

ข้ัอ 7

ให้ $a_{1},a_{2},a_{3},\ldots ,a_{n}$ เป็น permutation สุ่มของเซต $\{1,2,3,\ldots ,n\}$ โดยมันมีโอกาสจะเป็น permutation ใดๆ ใน permutation n! ตัวที่เป็นไปได้เท่าๆ กัน

เมื่อเราทำการเรียงลำดับ $a_{1},a_{2},a_{3},\ldots ,a_{n}$ เลข $a_{i}$ จะต้องถูกเลื่อนเป็นระยะทาง $|a_{i}-i|$ ไปยังตำแหน่งที่มันอยู่ตอนต้น ไปยังตำแหน่งที่เหมาะสมในลำดับที่เรียงแล้ว

จงหา $E{\bigg [}\sum _{i=1}^{n}|a_{i}-i|{\bigg ]}$ ซึ่งมีค่าเท่ากับระยะทางที่เลขทุกตัวจะถูกเลื่อนโดยเฉลี่ย

เฉลย

ข้่อ 8

คุณเล่นเกมพนันต่อไปนี้ คุณเริ่มต้นด้วยเงินต้น S หน่วย หลังจากนั้นจะมีการโยนเหรียญที่ไม่ถ่วงน้ำหนัก n ครั้ง สำหรับการโยนเหรียนแต่ละครั้ง

• ถ้าเหรียญออกหัว เจ้ามือจะจ่ายเงินให้คุณเพื่อทำให้คุณมีเงินสองเท่าของเงินที่คุณมีอยู่ตอนนั้น
• ถ้าเหรียญออกก้อย คุณจะต้องจ่ายเงินให้เจ้ามือเพื่อทำให้คุณมีเงินเหลือเพียง 1/4 ของเงินที่คุณมีในตอนนั้น

ยกตัวอย่างเช่น สมมติให้ S = 100 บาท ถ้าการโยนเหรียญครั้งแรกออกหัว เจ้ามีจะจ่ายเงินให้คุณ 100 บาท ทำให้คุณมีเงิน 200 บาท และถ้าการโยนเหรียญครั้งที่สองออกก้อย คุณต้องจ่ายเงินให้เจ้ามือ 150 บาท เหลือ 50 บาท (= 200/4)

1. ให้ $X_{n}$ เป็นจำนวนเงินที่คุณมีหลังจากโยนเหรียญ n ครั้ง จงหาค่า $E[X_{n}]$
2. ให้ $Y_{n}$ เป็นจำนวนหัวที่ออกในการโยนเหรียญ n ครั้ง $Y_{n}$ จะต้องมีค่าน้อยที่สุดเท่าไหร่คุณถึงจะไม่ขาดทุน?
3. จงหา $E[Y_{n}]$ และ $\mathrm {Var} [Y_{n}]$
4. จงใ้ช้อสมการของมาร์คอฟและอสมกาารของเชบิเชฟหาขอบเขตบนของความน่าจะเป็นที่คุณจะไม่ขาดทุน

เฉลย