วงแหวนเว็บ

neizod's speculation

insufficient data for meaningful answer

เล่นแลกของขวัญให้ไม่ได้ของตัวเอง

Sunday, June 20, 2021, 11:24 PM

เคยตั้งข้อสังเกตไว้กว่าครึ่งทศวรรษว่า งานปาร์ตี้แลกของขวัญมักมีคนที่ได้ของขวัญของตัวเองอยู่บ่อยๆ ซึ่งจากการวิเคราะห์ความน่าจะเป็นทำให้เห็นว่าโอกาสที่งานปาร์ตี้หนึ่งๆ จะไม่มีใครได้ของขวัญของตัวเองเลยนั้นลู่เข้าหา $1/e$ แต่ยังเหลือคำถามสำคัญที่ไม่ได้ตอบคือ แล้วเราจะมีวิธีแลกของขวัญที่แฟร์และไม่มีใครได้ของขวัญของตัวเองมั้ย?

ก่อนอื่นระลึกกันอีกครั้งว่า จากคนที่มาเล่นเกมแลกของขวัญ $n$ คน จำนวนวิธีการการแลกของขวัญที่ไม่มีใครได้ของตัวเองมีทั้งหมด

\[\begin{align} d(0) &= 1 \\ d(1) &= 0 \\ d(n) &= (n-1) \Big( d(n-1) + d(n-2) \Big) = \left\lceil \frac{n!}e \right\rfloor \end{align}\]

แต่เพราะจำนวนวิธีการแลกของขวัญทั้งหมดที่สามารถมีคนได้ของตัวเองได้คือ $n!$ ซึ่งจะเห็นว่าลู่เข้า ดังนั้น $d(n)/n! \approx 1/e$ หรือประมาณ $36\%$ นี่ทำให้เรามีขั้นตอนวิธีที่ง่ายดายสำหรับการแลกของขวัญที่ไม่มีใครได้ของตัวเอง ซึ่งก็คือการสุ่มแลกของขวัญไปเรื่อยๆ จนครบทุกคนนั่นแหละ แต่ถ้าระหว่างทางมีใครจับได้ของขวัญของตัวเองก็จะต้องกลับไปเริ่มการแลกของขวัญใหม่ตั้งแต่ต้น (ถ้าไม่โละกระดานเริ่มใหม่จะได้ผลลัพธ์ที่ไม่แฟร์) เนื่องจากโอกาสที่จะไม่มีใครได้ของขวัญของตัวเองเป็นค่าคงที่ประมาณหนึ่งในสาม ดังนั้นโดยเฉลี่ยแล้วเราจะเริ่มใหม่ประมาณสามรอบถึงจะเจอการแลกของขวัญที่ต้องการ

แม้วิธีข้างต้นจะถือว่าไม่เลวในมุมมองอัลกอริทึมสำหรับคอมพิวเตอร์ แต่หากนำไปใช้งานจริงในปาร์ตี้ก็อาจจะดูแปลกจนน่าเวียนหัว เพราะระหว่างทางที่แลกของขวัญ คนที่ร่วมเล่นเกมจะได้กล่องของขวัญของคนอื่นมาวางไว้ตรงหน้าด้วยความตื่นเต้นแล้ว แต่ก็ยังเปิดกล่องของขวัญไม่ได้จนกว่าการแลกของขวัญจะสิ้นเสร็จถูกต้องสมบูรณ์จนถึงคนสุดท้าย และยังมีโอกาสสูงมากที่จะต้องโบกมือลาบ๊ายบายกล่องของขวัญที่แลกมาระหว่างทางเพราะต้องเริ่มเล่นแลกของขวัญใหม่ทั้งหมดอีกรอบด้วย

เราอาจเปลี่ยนไปใช้วิธีของ Hannah Fry ในวิดีโอ Secret Santa ก็ได้ ซึ่งให้ผลลัพธ์การแลกของขวัญที่ทุกคนมีโอกาสได้ของคนอื่นเท่าๆ กันโดยไม่มีโอกาสได้ของตัวเองเลย แต่กระบวนการดังกล่าวจะให้ผลลัพธ์ไม่ครอบคลุมวิธีการแลกของขวัญทั้งหมด เพราะมีเพียงแค่การแลกของขวัญเป็นวงกลมวงใหญ่เพียงวงเดียวเท่านั้นที่สามารถเป็นผลลัพธ์ได้ ในขณะที่วิธีการแลกของขวัญทั้งหมดสามารถมีวงแลกของขวัญย่อยๆ ได้หลายวงเลย

และแม้วิธีดังกล่าวจะมีขั้นตอนเรียบง่ายทั้งยังให้ผลลัพธ์ที่ถือว่าแฟร์แล้ว แต่จุดตายสำคัญคือการออกแบบวิธีที่ขาดส่วนร่วมจากผู้เล่นแต่ละคนที่อุตสาห์เฟ้นหาของขวัญมาเล่นเกมนี้ เพราะขั้นตอนวิธีดังกล่าวอาศัยเพียงแค่กรรมการหนึ่งคนก็เพียงพอแล้วที่จะจัดเรียงหาว่าใครควรได้ของขวัญจากใคร ผู้เล่นแต่ละคนแค่นำกล่องของขวัญมาวางไว้ตอนเริ่มปาร์ตี้แล้วก็หยิบกล่องของขวัญตามคำบอกกลับบ้านตอนจบปาร์ตี้ได้เลย ไม่ต้องออกแรงสุ่มด้วยตนเองใดๆ ทั้งสิ้น

เช่นนี้แล้วเราจะสิ้นหวังหาทางออกที่บาลานซ์ระหว่างความถูกต้องทางคณิตศาสตร์และความสนุกตื่นเต้นเร้าใจและมีส่วนร่วมของมนุษย์ให้กับเรื่องนี้ไม่ได้เลยหรือ? โชคดีที่ Nat Sothanaphan ส่งข่าวว่ามาว่าเปเปอร์ [Martínez-Panholzer-Prodinger 2008] ได้เขียนรายละเอียดการสร้างลำดับสุ่มโดยห้ามของอยู่ซ้ำที่เดิมในแง่มุมทางคณิตศาสตร์ไปเรียบร้อยแล้ว ซึ่งใจความสำคัญสามารถสรุปเป็นโค้ด Python ได้ดังนี้

import random

def d(n, memo={0: 1, 1: 0}):
    if n not in memo:
        memo[n] = (n-1) * (d(n-1) + d(n-2))
    return memo[n]

def random_close_loop(r):
    return random.choices([True, False], weights=[d(r-1), d(r)])[0]

def derangement(n):
    if n == 1:
        raise Exception('can not do derangement with only 1 item')
    hat = set(range(n))
    result = list(range(n))
    for i in range(n):
        if i in hat:
            hat -= {i}
            j = random.choice(list(avail))
            result[i], result[j] = result[j], result[i]
            if random_close_loop(len(avail)):
                hat -= {j}
    return result

หรือเล่าเป็นขั้นตอนให้คนทั่วไปที่อยากลองเอาไปทดลองตามได้ว่า

  1. เตรียมฉลากที่มีชื่อคนทุกคนที่จะเล่นแลกของขวัญใส่ไหจับฉลาก
  2. ประธานจับฉลากหนึ่งใบ (ไม่ใส่คืน) เพื่อหาคนเริ่มต้นวงจับของขวัญ (หรือจบเกมเมื่อไม่เหลือฉลาก)
  3. เอาของขวัญของคนที่มีชื่อบนฉลากมาวางบนแท่นของขวัญสำหรับการจบรอบวงย่อย
  4. ให้คนที่มีชื่อบนฉลาก เป็นคนจับฉลากใบถัดไปเพื่อหาว่าเขาจะได้รับของขวัญจากใคร
  5. คนจับฉลากในข้อที่ผ่านมารับของขวัญจากคนที่มีชื่อบนฉลากในข้อที่ผ่านมา
  6. นับจำนวนคนที่เหลือที่ยังไม่ได้ของขวัญแล้วให้เป็นค่า $r$ (ไม่ต้องนับคนที่เพิ่งได้ของขวัญในข้อที่แล้ว)
  7. คนที่มีชื่อบนฉลาก โยนเหรียญไบแอสที่มีน้ำหนักดังนี้
    • ออกก้อยด้วยน้ำหนัก $d(r)$ ไม่มีเหตุการณ์ที่น่าสนใจเกิดขึ้น แค่วนกลับไปทำข้อ 4. ไล่ลงมา
    • ออกหัวด้วยน้ำหนัก $d(r-1)$ ถือว่าได้ของขวัญจบวงย่อย ดังนั้นวนกลับไปทำข้อ 2. ไล่ลงมา
  8. ประธานกล่าวปิดงาน 😝

ตัวอย่างการสุ่มแลกของขวัญที่ไม่มีใครได้ของตัวเองเมื่อ $n=6$ ผลลัพธ์นี้ได้วงย่อยของการแลกของขวัญเป็นจำนวนสองวง

จากตัวอย่างการแลกของขวัญของกลุ่มคนหกคนในรูปข้างต้น อธิบายแต่ละขั้นตอนได้คือ

  1. ประธานจับฉลากใบแรกเพื่อหาคนเริ่มต้นวงย่อยการแลกของขวัญ ซึ่งก็คือน้ำเงิน
  2. น้ำเงินนำกล่องของขวัญตัวเองมาวางไว้บนแท่น พร้อมจับฉลากใบถัดไปและได้ชมพู
  3. เพราะตอนนี้ $r=5$ ชมพูโยนเหรียญด้วยน้ำหนักหัว $d(4)$ ต่อน้ำหนักก้อย $d(5)$ และออกหัว
  4. ชมพูได้รับของขวัญบนแท่น และปิดวงย่อยของการแลกของขวัญที่มีแค่สองคน 💏
  5. ประธานจับฉลากอีกครั้งเพื่อหาคนเริ่มวงย่อยเพื่อแลกของขวัญรอบถัดไป ซึ่งคราวนี้ได้เหลือง
  6. เหลืองเอาของขวัญตัวเองมาวางแท่น แล้วจับฉลากได้แดง
  7. แดงโยนเหรียญด้วยน้ำหนักออกหัว $d(2)$ ต่อน้ำหนักออกก้อย $d(3)$ และออกก้อย
  8. แดงอดได้ของขวัญบนแท่น จึงต้องจับฉลากและจับได้ฟ้า
  9. เหลือสองคนสุดท้าย ฟ้าไม่จำเป็นต้องโยนเหรียญแล้ว เพราะน้ำหนักออกหัวคือ $d(1)=0$ จึงต้องจับฉลากแน่นอน และฉลากก็เหลือเพียงใบเดียวฟ้าจึงไม่มีทางเลือกนอกจากได้ของขวัญจากเขียว (ส่วนเขียวก็ไม่ต้องทำอะไรเพราะน้ำหนักโยนเหรียญออกก้อยคือ $d(1)=0$ ซึ่งก็คือต้องรับของขวัญบนแท่นนั่นเอง)
  10. สรุปผลวงย่อยของการแลกของขวัญวงที่สอง ที่มีคนสี่คนแลกของขวัญกันเป็นวงตามรูป 👨‍👩‍👧‍👧

อย่างไรก็ตาม เราคงไม่สามารถหาเหรียญที่ปรับน้ำหนักของแต่ละด้านอย่างละเอียดตามที่อัลกอริทึมต้องการได้ หรือถ้าจะย้ายไปคำนวณเชิงตัวเลขล้วนๆ ด้วยคอมพิวเตอร์เพียง ก็อาจนำมาซึ่งปัญหาเรื่องความเชื่อใจของมนุษย์ต่อเครื่องจักรและ RNGsus แทนอีก เช่นนี้แล้วเราควรทำอย่างไรดี?

สังเกตว่าสำหรับแต่ละค่า $r$ ความน่าจะเป็นของการโยนเหรียญออกหัวคือ

\[\begin{array}{c|cc|cl} r & \text{weight H} & \text{weight T} & P(\text{toss H}) \\ \hline 1 & 1 & 0 & \dfrac1{1+0} = 1 \\ 2 & 0 & 1 & \dfrac0{0+1} = 0 \\ 3 & 1 & 2 & \dfrac1{1+2} = \dfrac13 \\ 4 & 2 & 9 & \dfrac2{2+9} = \dfrac2{11} & \approx \dfrac15 \;\;\text{(error $9\%$)} \\ 5 & 9 & 44 & \dfrac9{9+44} = \dfrac9{53} & \approx \dfrac16 \;\;\text{(error $2\%$)} \\ 6 & 44 & 265 & \dfrac{44}{44+265} = \dfrac{44}{309} & \approx \dfrac17 \\ \vdots & & & \vdots \\ r & d(r-1) & d(r) & \dfrac{d(r-1)}{d(r-1)+d(r)} & \approx \dfrac1{1+r} \end{array}\]

นอกจากที่ค่า $r$ น้อยมากๆ แล้ว จะเห็นว่าโอกาสออกหัวอยู่ที่ประมาณ $\frac1{1+r}$ ซึ่งเราสามารถมาถึงข้อสรุปนี้ได้จาก สมการ $d(r) = \left\lceil \frac{r!}e \right\rfloor$ ที่แสดงให้เห็นว่า

\[\frac{d(r-1)}{d(r-1) + d(r)} \approx \frac{(r-1)!}{(r-1)! + r!} = \frac{(r-1)!}{(r-1)!(1+r)} = \frac1{1+r}\]

จากค่าประมาณอัตราส่วนสวยๆ เช่นนี้ หมายความว่าเราสามารถนำไพ่มาช่วยในการสุ่มได้! ซึ่งเป็นผลดีทางจิตวิทยาของมนุษย์มากกว่าเพราะมันทำให้เราเข้าใจความน่าจะเป็นได้แจ่มชัดกว่าการเห็นเพียงแค่ตัวเลข1 และวิธีการใช้งานมันก็ง่ายดายยิ่งกว่าการหาเหรียญไบแอสมาโยนเป็นไหนๆ เช่นเมื่อ $r=6$ เราสามารถใช้ไพ่เพียงเจ็ดใบที่หนึ่งในนั้นเป็นหน้าโจ๊กเกอร์ได้เลย หากสับไพ่แล้วเปิดเจอโจ๊กเกอร์ก็คือการแลกของขวัญในวงย่อยวงนี้ถึงที่สิ้นสุดนั่นเอง

ข้อสังเกตสำคัญคือกรณีที่ $r=4$ จะเห็นว่าแม้ค่าประมาณนั้นจะมีหน้าตาไล่เลขลดลงมาเรื่อยๆ มาอย่างสวยงาม แต่ความเพี้ยนของการประมาณที่จุดนี้สูงถึงเกือบ $10\%$ ดังนั้นเราจึงควรใช้อัตราส่วน $2:9$ ที่หมายถึงมีโจ๊กเกอร์สองใบต่อไพ่อื่นๆ อีกเก้าใบถึงจะให้ผลลัพธ์การสุ่มที่แฟร์กว่า

def random_close_loop_approx(r):
    if r > 4:
        return random.choices([True, False], weights=[1, r])[0]
    if r == 4:
        return random.choices([True, False], weights=[2, 9])[0]
    if r == 3:
        return random.choices([True, False], weights=[1, 2])[0]
    if r == 2:
        return False
    if r == 1:
        return True
    raise KeyError('undefined behavior')

แล้วทำไมถึงต้องมีการสุ่มเพื่อปิดวงเช่นนี้ด้วยหละ? ย้อนกลับไปตีความการสร้างคำตอบจากสมการเวียนเกิดเมื่อเพิ่มของชิ้นที่ $k$ เข้าไป จะเห็นว่า

\[d(k) = (k-1) \Big( \underbrace{d(k-1)}_\text{EXISTS} + \underbrace{d(k-2)}_\text{CREATE} \Big)\]
  • EXISTS อาจจะมีวงย่อยมาก่อนกี่วงก็ได้ แล้วของชิ้นที่ $k$ เข้าไปแทรกในวงย่อยวงใดวงหนึ่งที่เคยมี
  • CREATE สร้างวงย่อยใหม่ซึ่งมีของเพียงสองชิ้นพอดี คือชิ้นที่ $k$ กับอีกชิ้นที่มาก่อน $k$ ที่ถูกเลือกมาอย่างสุ่ม (อย่างไรก็ตาม เมื่อใส่ของชิ้นหลังจาก $k$ ไปเรื่อยๆ วงนี้อาจถูกขยายขนาดทีหลังได้)

แต่สิ่งที่อัลกอริทึมสุ่มลำดับไม่ซ้ำที่เดิมทำนั้น จะเปลี่ยนเป็นวิ่งสวนทางโดยลดค่า $k$ ลงเรื่อยๆ แทน ดังนั้นเราต้องตีความการ CREATE กลับด้าน โดยหมายความว่าหลังจากพิจารณาของชิ้นที่ $k$ ออกมาแล้ว เราจะเหลือของอยู่ $r=k-1$ ชิ้น และเราจะถามต่อทันทีว่าของชิ้นต่อไปที่จะเอาออกควรย้อนกลับไปปิดวงย่อยที่มีของชิ้นที่ $k$ หรือเปล่า ซึ่งสัดส่วนจำนวนเหตุการณ์ที่เกิดก็คือ $\frac{\text{#CREATE}}{\text{#CREATE}+\text{#EXISTS}}$ นั่นเอง

หวังว่าจะได้ทริกดีๆ ไว้ทำให้ปาร์ตี้แลกของขวัญสนุกยิ่งขึ้นนะ 🃏

  1. วิดีโอจาก GMTK นาทีที่ 15:50-17:07 

neizod

author