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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
(หน้าที่ถูกสร้างด้วย '== ข้อ 1 == [Mitzenmacher & Upfal 2.2] ลิงตัวหนึ่งพิมพ์แป้นพิมพ์ดีดที่…')
 
 
(ไม่แสดง 10 รุ่นระหว่างกลางโดยผู้ใช้ 3 คน)
แถว 1: แถว 1:
 
== ข้อ 1 ==
 
== ข้อ 1 ==
[Mitzenmacher & Upfal 2.2] ลิงตัวหนึ่งพิมพ์แป้นพิมพ์ดีดที่มีแป้นพิมพ์อยู่ 26 ตัวซึ่งตรงกับตัวอักษรภาษาอังกฤษตัวเลขทั้ง 26 ตัว โดยที่ตัวอักษรที่ลิงพิมพ์แต่ละตัวถูกเลือกขึ้นมาอย่างๆ สุ่มๆ โดยที่ตัวอักษรแต่ละตัวมีโอกาสได้รับเลือกเท่าๆ กัน และการพิมพ์แต่ละครั้งเป็นอิสระจากการพิมพ์ครั้งอื่นๆ ถ้าลิืงพิมพ์ตัวอักษรไปทั้งหมด 1,000,000 ตังอักษร จงหาจำนวนที่คำว่า "proof" จะปรากฎอยู่ในข้อความที่ลิงพิมพ์ออกมานี้
+
[Mitzenmacher & Upfal 2.2] ลิงตัวหนึ่งพิมพ์แป้นพิมพ์ดีดที่มีแป้นพิมพ์อยู่ 26 ตัวซึ่งตรงกับตัวอักษรภาษาอังกฤษตัวเล็กทั้ง 26 ตัว โดยที่ตัวอักษรที่ลิงพิมพ์แต่ละตัวถูกเลือกขึ้นมาอย่างๆ สุ่มๆ โดยที่ตัวอักษรแต่ละตัวมีโอกาสได้รับเลือกเท่าๆ กัน และการพิมพ์แต่ละครั้งเป็นอิสระจากการพิมพ์ครั้งอื่นๆ ถ้าลิืงพิมพ์ตัวอักษรไปทั้งหมด 1,000,000 ตัวอักษร จงหาจำนวนที่คำว่า "proof" จะปรากฎอยู่ในข้อความที่ลิงพิมพ์ออกมานี้
 +
 
 +
[[418531 ภาคต้น 2552/โจทย์ปัญหาความน่าจะเป็น II/เฉลยข้อ 1|เฉลย]]
  
 
== ข้อ 2 ==
 
== ข้อ 2 ==
แถว 8: แถว 10:
 
# <math>E[X_1\ |\ X = 9] \,</math>
 
# <math>E[X_1\ |\ X = 9] \,</math>
 
# <math>E[X_1 - X_2 \ |\ X = k] \,</math> เมื่อ k อยู่ในช่วง [2, 12]
 
# <math>E[X_1 - X_2 \ |\ X = k] \,</math> เมื่อ k อยู่ในช่วง [2, 12]
 +
 +
[[418531 ภาคต้น 2552/โจทย์ปัญหาความน่าจะเป็น II/เฉลยข้อ 2|เฉลย]]
  
 
== ข้อ 3 ==
 
== ข้อ 3 ==
แถว 15: แถว 19:
 
# จงหา <math>\Pr(\min(X,Y) = k)\,</math>
 
# จงหา <math>\Pr(\min(X,Y) = k)\,</math>
 
# จงหา <math>E[X\ |\ X \leq Y]\,</math>
 
# จงหา <math>E[X\ |\ X \leq Y]\,</math>
 +
 +
[[418531 ภาคต้น 2552/โจทย์ปัญหาความน่าจะเป็น II/เฉลยข้อ 3|เฉลย]]
  
 
== ข้อ 4 ==
 
== ข้อ 4 ==
แถว 21: แถว 27:
 
# ถ้าเราทำการดึงไพ่ออกมา 2n ครั้ง จงหาจำนวนไพ่ที่ไม่เคยถูกดึงออกมาจากกองเลยโดยเฉลี่ย
 
# ถ้าเราทำการดึงไพ่ออกมา 2n ครั้ง จงหาจำนวนไพ่ที่ไม่เคยถูกดึงออกมาจากกองเลยโดยเฉลี่ย
 
# ถ้าเราทำการดึงไพ่ออกมา 2n ครั้ง จงหาจำนวนไพ่ที่ถูกดึงออกมาจากกองเพียงครั้งเดียวเท่านั้น
 
# ถ้าเราทำการดึงไพ่ออกมา 2n ครั้ง จงหาจำนวนไพ่ที่ถูกดึงออกมาจากกองเพียงครั้งเดียวเท่านั้น
 +
 +
[[418531 ภาคต้น 2552/โจทย์ปัญหาความน่าจะเป็น II/เฉลยข้อ 4|เฉลย]]
  
 
== ข้อ 5 ==
 
== ข้อ 5 ==
 
[Mitzenmacher & Upfal 2.14] โยนเหรียญถ่วงน้ำหนักที่ขึ้นหัวด้วยความน่าจะเป็น p ไปเรื่อยๆ ให้ X เป็นจำนวนการโยนเหรียนจนกระทั่งหัวครั้งที่ k ออกมา จงแสดงว่า <math>\Pr(X = n) = {n-1 \choose k-1} p^k (1-p)^{n-k} \,</math>
 
[Mitzenmacher & Upfal 2.14] โยนเหรียญถ่วงน้ำหนักที่ขึ้นหัวด้วยความน่าจะเป็น p ไปเรื่อยๆ ให้ X เป็นจำนวนการโยนเหรียนจนกระทั่งหัวครั้งที่ k ออกมา จงแสดงว่า <math>\Pr(X = n) = {n-1 \choose k-1} p^k (1-p)^{n-k} \,</math>
 +
 +
[[418531 ภาคต้น 2552/โจทย์ปัญหาความน่าจะเป็น II/เฉลยข้อ 5|เฉลย]]
 +
 +
== ข้อ 6 ==
 +
[Mitzenmacher & Upfal 2.18] พิจารณากระบวนการสุ่มต่อไปนี้: มีไพ่อยู่ n ใบ ซึ่งมีหมายเลข 1 ถึง n ติดอยู่ ขั้นแรกผมหยิบไพ่หมายเลข 1 ส่งให้คุณ แล้วคุณเก็บไว้ หลังจากนั้นผมส่งไพ่หมายเลข 2 ให้คุณ โดยคุณทำการตัดสินใจเก็บไพ่หมายเลข 2 แทนไพ่ที่คุณเก็บไว้ในปัจจุบันด้วยความน่าจะเป็น 1/2 หลังจากนั้นผมจึงส่งไพ่หมายเลข 3, 4, 5, ... ให้ตามลำดับจนกระทั่งครบทั้ง n ใบ โดยเมื่อผมส่งไพ่หมายเลข k ให้คุณ คุณจะเลือกเก็บไพ่หมายเลข k แทนไพ่ที่เก็บไว้ในปัจจุบันด้วยความน่าจะเป็น 1/k
 +
 +
จงแสดงไพ่ท้ายสุดเลย ไพ่ทุกใบมีโอกาสที่จะเป็นไพ่ที่คุณเก็บไว้ใบสุดท้ายเท่าๆ กัน
 +
 +
[[418531 ภาคต้น 2552/โจทย์ปัญหาความน่าจะเป็น II/เฉลยข้อ 6|เฉลย]]
 +
 +
== ข้ัอ 7 ==
 +
ให้ <math>a_1, a_2, a_3, \ldots, a_n</math> เป็น permutation สุ่มของเซต <math>\{1, 2, 3, \ldots, n \}</math> โดยมันมีโอกาสจะเป็น permutation ใดๆ ใน permutation n! ตัวที่เป็นไปได้เท่าๆ กัน
 +
 +
เมื่อเราทำการเรียงลำดับ <math>a_1, a_2, a_3, \ldots, a_n</math> เลข <math>a_i</math> จะต้องถูกเลื่อนเป็นระยะทาง <math>|a_i - i|</math> ไปยังตำแหน่งที่มันอยู่ตอนต้น ไปยังตำแหน่งที่เหมาะสมในลำดับที่เรียงแล้ว
 +
 +
จงหา <math>E \bigg[ \sum_{i=1}^n |a_i - i| \bigg] </math> ซึ่งมีค่าเท่ากับระยะทางที่เลขทุกตัวจะถูกเลื่อนโดยเฉลี่ย
 +
 +
[[418531 ภาคต้น 2552/โจทย์ปัญหาความน่าจะเป็น II/เฉลยข้อ 7|เฉลย]]
 +
 +
== ข้่อ 8 ==
 +
คุณเล่นเกมพนันต่อไปนี้ คุณเริ่มต้นด้วยเงินต้น S หน่วย หลังจากนั้นจะมีการโยนเหรียญที่ไม่ถ่วงน้ำหนัก n ครั้ง สำหรับการโยนเหรียนแต่ละครั้ง
 +
* ถ้าเหรียญออกหัว เจ้ามือจะจ่ายเงินให้คุณเพื่อทำให้คุณมีเงินสองเท่าของเงินที่คุณมีอยู่ตอนนั้น
 +
* ถ้าเหรียญออกก้อย คุณจะต้องจ่ายเงินให้เจ้ามือเพื่อทำให้คุณมีเงินเหลือเพียง 1/4 ของเงินที่คุณมีในตอนนั้น
 +
ยกตัวอย่างเช่น สมมติให้ S = 100 บาท ถ้าการโยนเหรียญครั้งแรกออกหัว เจ้ามีจะจ่ายเงินให้คุณ 100 บาท ทำให้คุณมีเงิน 200 บาท และถ้าการโยนเหรียญครั้งที่สองออกก้อย คุณต้องจ่ายเงินให้เจ้ามือ 150 บาท เหลือ 50 บาท (= 200/4)
 +
# ให้ <math>X_n</math> เป็นจำนวนเงินที่คุณมีหลังจากโยนเหรียญ n ครั้ง จงหาค่า <math>E[X_n]</math>
 +
# ให้ <math>Y_n</math> เป็นจำนวนหัวที่ออกในการโยนเหรียญ n ครั้ง <math>Y_n</math> จะต้องมีค่าน้อยที่สุดเท่าไหร่คุณถึงจะไม่ขาดทุน?
 +
# จงหา <math>E[Y_n]</math> และ <math>\mathrm{Var}[Y_n]</math>
 +
# จงใ้ช้อสมการของมาร์คอฟและอสมกาารของเชบิเชฟหาขอบเขตบนของความน่าจะเป็นที่คุณจะไม่ขาดทุน
 +
 +
[[418531 ภาคต้น 2552/โจทย์ปัญหาความน่าจะเป็น II/เฉลยข้อ 8|เฉลย]]

รุ่นแก้ไขปัจจุบันเมื่อ 08:13, 4 สิงหาคม 2552

ข้อ 1

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

เฉลย

ข้อ 2

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

  1. เมื่อ k อยู่ในช่วง [2, 12]

เฉลย

ข้อ 3

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

  1. จงหาความน่าจะเป็นที่ X = Y
  2. จงหา
  3. จงหา
  4. จงหา

เฉลย

ข้อ 4

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

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

เฉลย

ข้อ 5

[Mitzenmacher & Upfal 2.14] โยนเหรียญถ่วงน้ำหนักที่ขึ้นหัวด้วยความน่าจะเป็น p ไปเรื่อยๆ ให้ X เป็นจำนวนการโยนเหรียนจนกระทั่งหัวครั้งที่ k ออกมา จงแสดงว่า

เฉลย

ข้อ 6

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

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

เฉลย

ข้ัอ 7

ให้ เป็น permutation สุ่มของเซต โดยมันมีโอกาสจะเป็น permutation ใดๆ ใน permutation n! ตัวที่เป็นไปได้เท่าๆ กัน

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

จงหา ซึ่งมีค่าเท่ากับระยะทางที่เลขทุกตัวจะถูกเลื่อนโดยเฉลี่ย

เฉลย

ข้่อ 8

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

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

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

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

เฉลย