Markov Inequality에 대하여

(Lecture 3 후반부)

확률 변수에 대해 배우면서 우리는 평균, 분산, 기댓값 등을 계산하는 법에 대해 배웠습니다.

이번 포스팅은 평균(기댓값)을 이용하여 자료의 분포를 추정하는 공식인 마르코프 부등식(Markov Inequality)에 대해 서술합니다.

 

즉, 확률 변수의 확률 분포가 알려지지 않고 기댓값만이 주어질 때 확률 분포에 대한 정보를 알려줍니다. 음이 아닌 수를 값으로 갖는 확률 변수가 어떤 양수 a보다 큰 값을 가질 확률이 기댓값을 a로 나눈 것 보다 클 수 없음을 나타냅니다.

러시아의 수학자 마르코브의 이름을 딴 부등식이고, 다음 게시글에 작성할 마르코프의 스승 체비쇼프의 연구결과에도 나타난다고 합니다.

 

 

출처 네이버 지식백과

 

이를 증명하는 방법은 두 가지를 준비했는데요.

 

1. 네이버 블로그 서치

2. 수업에서 배운 거

---

 

간단한 예시 문제를 풀어보겠습니다

 

Example 1)  Bound the probability of obtaining more than 75 heads in a sequence of 100 fair coin flips.

 

X1, X2, X3, .... , X100 까지의 확률 변수를 정의합니다. 

이때 Xi는 i번째 동전이 head일 때 1이고, tail일 때 0으로 정의합니다.

따라서 X1부터 X100까지 확률변수를 모두 더하면 100개의 코인 중 head가 나온 코인의 갯수를 알 수 있습니다.

이 코인은 biased한 코인이 아니므로 E(Xi)=1/2, 따라서 E(X)=50입니다.

Markov 부등식에 따라 P(X≥75) ≤ E(X)/75 = 50/75 = 2/3입니다.

 

Example 2)  Bound the probability of obtaining more than (3/4)n heads in a sequence of n fair coin flips.

 

위와 같이 X1, X2, ..... , Xn 까지의 확률 변수를 정의합니다.

또 똑같이 Xi는 i번째 동전이 head일 때 1이고, tail일 때 0으로 정의합니다.

따라서 E(Xi)=1/2, 따라서 E(X)=(1/2)n입니다.

Markov 부등식에 따라 P(X≥(3/4)n) ≤ E(X)/(3/4)n = (1/2)n / (3/4)n = 2/3입니다.

 

* 마르코프 부등식은 powerful한 추측 범위를 제공하지만, 기댓값 만으로 추측한 범위이기 때문에 모든 값을 대변하지는 않는다는 점을 기억해야 합니다. (= Expectation is not everything) 이와 관련된 예제를 아래에 소개합니다.

 

Example 3)  (St. Petersburg Lottery) A casino offers a game of chance for a single player in which a fair coin is tossed at each stage. The pot starts at $1 and is doubled every time a head appears. The first time a tail appears, the game ends and the player wins whatever is in the pot. What would be a fair price to pay for entering the game?

 

보통은 기댓값을 입장료로 설정하는 것이 합리적이지 않을까? 라는 생각에서 출발합니다.

처음에 T가 나오면 1달러를 얻고, HT가 나오면 2달러를 얻습니다. 따라서 1달러를 얻을 확률은 1/2, 2달러를 얻을 확률은 1/4 ... 로 이어집니다. 따라서 기댓값은 아래와 같이 계산할 수 있습니다.

기댓값이 무한이니, 우리는 이 로터리에 참가만 하면 큰 돈을 딸 수 있을 것만 같습니다. 그러면 얼마를 지불하든 이 게임은 참여해야만 하겠죠. 하지만 실제로 우리는 그렇지 않다는 것을 압니다. 이것은 그저 기댓값에 지나지 않기 때문에, 우리는 큰 돈을 얻는 것이 아주 낮은 확률인 것을 알고 있습니다.

5번 이상 성공할 확률은 3%, 10번 이상 성공할 확률은 0.09%에 지나지 않습니다.

 

이와 관련된 paradox는 Daniel Bernoulli의 발표에서 처음 발표되었는데요. 아래 표는 bounded version의 Expected value of lottery입니다. 실제로는 무한대가 아닙니다.

출처 위키피디아, St. Peterburg paradox

Example 4)  Program A terminates in 1 hour on 99% of inputs and in 1000 hours on 1% of inputs. Program B terminates in 10.99 hours on every input. Which one would you prefer?

 

두 프로그램에 대한 기댓값을 계산해 봅니다.

E(X_A) = 1*0.99 + 1000*0.01 = 10.99

E(X_B) = 10.99*1 = 10.99

두 프로그램의 종료 시간 기댓값은 동일합니다. 그러면 두 프로그램 중 아무거나 고르면 될까요?

 

기댓값만을 고려한 선택은 합리적이지 않습니다. 우리는 deviation과 같은 다른 수치들도 고려해야합니다. 이는 다음 포스팅에서 이어 서술하겠습니다