Марковын тэнцэтгэл биш

Марковын тэнцэтгэл биш нь магадлалын тархалтын хувьд тухайн нэг утган дахь магадлалын мөн дээд, доод хязгаарыг олоход хэрэглэгддэг. Магадлалын тархалт гэдэг нь бүх санамсаргүй утгуудын дундах тэдгээрийг илэрхийлэх функц эсвэл дүрэм юм. Тархалт нь жагсаалт болон график гэсэн 2 төрлөөр илэрхийлэгдэж болдог. Тархалтыг дараах байдлаар тайлбарлая.

• Хоёр шоо хаяад буусан нүднүүдийн нийлбэрийг бичих туршилт хийж байна гэж үзье. Нийлбэр нь 2-12 байх боломжтой. Тэгвэл туршилтын үр дүнд гарсан магадлалуудын тархалт нь дараах байдлаар бичигдэнэ.
  • Нийлбэр 2 байх магадлал нь 1/36
  • Нийлбэр 3 байх магадлал нь 2/36
  • Нийлбэр 4 байх магадлал нь 3/36
  • Нийлбэр 5 байх магадлал нь 4/36
  • Нийлбэр 6 байх магадлал нь 5/36
  • Нийлбэр 7 байх магадлал нь 6/36
  • Нийлбэр 8 байх магадлал нь 5/36
  • Нийлбэр 9 байх магадлал нь 4/36
  • Нийлбэр 10 байх магадлал нь 3/36
  • Нийлбэр 11 байх магадлал нь 2/36
  • Нийлбэр 12 байх магадлал нь 1/36

Марковын тэнцэтгэл биш нь магадлалын тархалтын хувьд дээд болон доод хязгаар дахь магадлалын утгыг олоход хэрэглэдэг.Өгөгдсөн $f(x)$ тархалттай функцийн хувьд $\varepsilon$ гэсэн хязгаарлалт тавигдсан байна..

Марковын тэнцэтгэл бишийг доорхи бодлогонд ашиглая.

• Хуурамч зоос байгаа бөгөөд, сүлдээрээ буух магадлал нь 10-т нэг байна. Сүлдээрээ буух магадлал нь 1/10. 200 удаа дараалан туршилт хийсний дүнд хамгийн багадаа 120 удаа сүлдээрээ буух магдадлалыг ол.

E(X) – буюу хүлээлтийн утга нь
E(X) = n*p = 200*0.1 = 20 байна.

$\mathbb {P} (X\geq a)\leq {\frac {\mathbb {E} (X)}{a}}.$

гэдгээс
(E(X))/120 = 20/120= 1/6 болно. Өөрөөр хэлбэл 200 удаа зоосыг шидэхэд 120 удаад нь сүлдээрээ буух магадлал 1/6-аас хэтрэхгүй гэсэн үг.

• Гэрлийн ламп хийдэг компани энгийн хэрэглээнд нэг ламп дунджаар 4 жил асаад шатдаг болохыг тогтоожээ. Тэгвэл тухайн нэг ламп 12 – оос дээш жил энгийн хэрэглээнд асах магадлал ямар байх вэ?

Бодолт нь:
E(X) – буюу хүлээлтийн утга нь
E(X) = 4 байна.

$\mathbb {P} (X\geq a)\leq {\frac {\mathbb {E} (X)}{a}}.$

гэдгээс (E(X))/12 = 4/12= 1/3 буюу ойролцоогоор 0,33 хувийн магадлалтай байна.

• Бактерийн амьдрах хугацаа нь дунджаар 2 цаг байдаг байна. Тэгвэл бактерийн 10 цаг эсвэл түүнээс илүү хугацаагаар амьдрах магадлал

нь хэд байх вэ?
Бодолт нь: Марковын тэнцэтгэл бишийн дагуу 2/10 гэсэн хэлбэртэй болно. Өөрөөр хэлбэл бактерийн 20 хувь нь 10 цаг буюу түүнээс илүү хугацаатайгаар амьдрах магадлалтай гэсэн үг.

Томьёолол

Хэрэв X нь сөрөг биш дурын утга бөгөөд a нь  > 0 бол

$\mathbb {P} (X\geq a)\leq {\frac {\mathbb {E} (X)}{a}}.$

Марковын тэнцэтгэл бишийн төлөв нь хэрэв (X, Σ, μ) бол (measure space) дараах байдлаар өргөтгөгдөнө.

$\mu (\{x\in X:|f(x)|\geq \varepsilon \})\leq {1 \over \varepsilon }\int _{X}|f|\,d\mu .$

(Энэхүү хэмжилтийн онолын тодорхойлолт нь Чебишевийн тэнцэтгэл бишийн үед хэрэглэгддэг. Chebyshev's inequality .)

Хамааралтай томьёолол: Чебишевийн тэнцэтгэл биш

(Chebyshev's inequality) Чебишевийн тэнцэтгэл биш нь магадлалын тархалтын хувьд дурын утга дунджаасаа ямар магадлалаар хазайж болохыг хэмждэг.

$\mathbb {P} (|X-\mathbb {E} (X)|\geq a)\leq {\frac {{\textrm {Var}}(X)}{a^{2}}},$

дурын a>0 утгын хувьд. Энд Var(X) нь X- ийс вариац бөгөөд дараах байдлаар тодорхойлогдсон:

$\operatorname {Var} (X)=\mathbb {E} [(X-\mathbb {E} (X))^{2}].$

Чебишевийн тэнцэтгэл биш нь Марковын дурын сөрөг биш утга авдаг байдлыг ашигладаг.

$(X-\mathbb {E} (X))^{2}$

Тиймээс марковын тэнцэтгэл бишийг өргөтгөж бичвэл дараах байдалтай болно.

$\mathbb {P} ((X-\mathbb {E} (X))^{2}\geq a^{2})\leq {\frac {\operatorname {Var} (X)}{a^{2}}},$

Баталгаа

Хэрэв X нь зөвхөн сөрөг биш утгыг авдаг гэвэл:

$P(X\geq a)\leq {\frac {E(x)}{a}}.$

Томьёог дараах байдлаар бичиж болно.

$E(x)=\int _{0}^{\infty }xP(x)dx$ =

$\int _{0}^{a}xP(x)dx$ + $\int _{a}^{\infty }xP(x)dx$
P(X) нь магадлал учраас утга нь ≥ 0 байх ёстой. Тиймээс
E(x) = $\int _{0}^{a}xP(x)dx$ + $\int _{a}^{\infty }xP(x)dx$ $\geq \int _{a}^{\infty }xP(x)dx$
$\geq \int _{a}^{\infty }aP(x)dx$
$=\int _{a}^{\infty }aP(x)dx$
$=aP(X\geq a)$

гэдгээс батлагдаж байна.

Задаргаа бүхий гаргалгаа

Сөрөг биш $f$ функц байна, томьёонд зөвхөн абсолют буюу эерэг утгуудыг авна. Одоо s гэсэн функцд X өгөгдсөн гэж үзье.

$s(x)={\begin{cases}\varepsilon ,&{\text{if }}f(x)\geq \varepsilon \\0,&{\text{if }}f(x)<\varepsilon \end{cases}}$

Тэгвэл $s$ энгийн функц бөгөөд дараах нөхцөлийг хангана $0\leq s(x)\leq f(x)$. Лебесгийн интегралаар илэрхийлэгдэнэ.Lebesgue integral

$\int _{X}f(x)\,d\mu \geq \int _{X}s(x)\,d\mu =\varepsilon \mu (\{x\in X:\,f(x)\geq \varepsilon \})$

мөн $\varepsilon >0$ учир, аль аль тал нь $\varepsilon$ - аар хуваагдана

$\mu (\{x\in X:\,f(x)\geq \varepsilon \})\leq {1 \over \varepsilon }\int _{X}f\,d\mu .$

Q.E.D.

Матриксийн утга болон марков

$M\succeq 0$ байх өөртөө хосмог матрикс байна гэж үзвэл $a>0$ байх дурын утгын хувьд дараах томьёо хүчинтэй байна.

$\mathbb {P} (M\npreceq a\cdot I)\leq {\frac {\mathrm {tr} \left(E(M)\right)}{a}}.$

Жишээ

• Марковын тэнцэтгэл бишийг Chebyshev's inequality буюу Чебишевийн тэнцэтгэл бишийг батлахад ашигладаг.
• Дурын сөрөг биш утгын хувьд, дундаж $\mu$ болон медиан нь $m$ дараах байдлаар илэрхийлэгдэнэ. $m\leq 2\mu$.

Бусад бичлэгүүд

• McDiarmid's inequality
• Bernstein inequalities (probability theory)
• Chernoff Bound

Гадаад линкүүд

• The formal proof of Markov's inequality in the Mizar system.