อสมการของมาร์คอฟ

จากวิกิพีเดีย สารานุกรมเสรี

ในทฤษฎีความน่าจะเป็น อสมการของมาร์คอฟ เป็นข้อความทางคณิตศาสตร์ที่ให้ขอบเขตบนของความน่าจะเป็นที่ตัวแปรสุ่มที่มีค่าบวกจะมีมากกว่าหรือเท่ากับจำนวนจริงบวกคงที่หนึ่งๆ ชื่อของอสมการตั้งตามนักคณิตศาสตร์ชาวรัสเซียชื่อ อังเดร มาร์คอฟ

อสมการของมาร์คอฟมีใจความดังต่อไปนี้: ให้ X \, เป็นตัวแปรสุ่มที่มีค่าไม่เป็นลบและ t \, เป็นจำนวนจริงใด ๆ ที่มากกว่าศูนย์ แล้ว

\Pr[X \geq t] \leq \frac{\mathrm{E}[X]}{t}

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

การพิสูจน์[แก้]

กำหนดฟังก์ชัน f: \mathbb{R} \rightarrow \mathbb{R} ดังต่อไปนี้ f(x) = 1 เมื่อ x \geq t มิฉะนั้น f(x) = 0 เราได้ว่า

\mathrm{E}[f(X)] = \Pr[X \geq t]

เนื่องจาก f(x) \leq x/t สำหรับทุกๆ จำนวนจริง x เราได้ว่า

\Pr[X \geq t] \leq \mathrm{E}[X/t] = \frac{\mathrm{E}[X]}{t}

ตามต้องการ

อีกบทพิสูจน์หนึ่ง[แก้]

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

จากนิยามของค่าคาดหมาย และเงื่อนไขที่ว่าตัวแปรสุ่ม X มีค่าไม่เป็นลบ เราได้ว่า

\mathrm{E}[X]=\sum_{i=0}^{\infty}i\cdot\Pr[X=i]
=\sum_{i=0}^{t-1}i\cdot\Pr[X=i]
+\sum_{i=t}^{\infty}i\cdot\Pr[X=i]     (กระจายเทอม โดยแยกกรณี i<t กับ i\geq t)
\geq\sum_{i=t}^{\infty}i\cdot\Pr[X=i]     (ทิ้งเทอมหน้าซึ่งมีค่ามากกว่าหรือเท่ากับศูนย์)
\geq\sum_{i=t}^{\infty}t\cdot\Pr[X=i]     (เนื่องจาก i\geq t)
=t\cdot\left(\sum_{i=t}^{\infty}\cdot\Pr[X=i]\right)     (แยก t)
=t\cdot\Pr[X\geq t].     (เนื่องจากเป็นผลรวมของความน่าจะเป็นของเหตุการณ์ที่ไม่เกิดร่วมกัน)

นั่นคือเราได้ \Pr[X\geq t]\leq\mathrm{E}[X]/t ตามต้องการ

รูปแบบอื่นของ อสมการของมาร์คอฟ[แก้]

บางครั้งเราอาจพบเห็น การใช้อสมการของมาร์คอฟ ในรูปแบบอื่น ๆ เช่น

เมื่อ g(x)\uparrow , g(x) \geq 0 คือ เป็นฟังก์ชันที่มีค่าไม่เป็นลบ และ มีค่าไม่ลดลงแล้ว

\Pr[X \geq t] \leq \frac{\mathrm{E}[g(X)]}{g(t)}

ซึ่งในกรณีที่ g(x) = e^{tx} จะนำไปสู่ ขอบเขตเชอร์นอฟ