Computing by Conditioning

○Computing Expectations by conditioning

 ▷Condition을 걸어서 기대값을 구해야 하는 경우

 ▷재귀적인 문제 (선택 이후 선택이 처음과 같음)를 푸는데 유용함.

 

 ◎앞면이 나올때까지 동전 던지기 (Geomatric)

  ▷Condition Y -> 1: 첫 던지기가 앞면 / 0:첫 던지기가 뒷면

  ▷Y가 0이면, 1회를 추가한 뒤, 다시 동전을 던지는 것 (E[N])과 같다.

 

 ◎Quick Sort Average Comparison

  ▶Quicksort

   ▷pivot 선택

   ▷leftmark, rightmark가 순회하며 pivot과 비교. (left가 pivot보다 크고, right가 pivot보다 작으면 멈추고, 둘 다 멈춰있으면 서로 바꾼다.)

   ▷leftmark, rightmark가 서로 같은 위치거나 교차하면, pivot과 바꾼다.

   ▷pivot기준 left partition, right partition에 대해 반복한다.

  ▶Expectation of comparison

   ▷Mn -> E[N], Condition j -> pivot이 j번째로 작은 수

 

○Computing Variances by conditioning

 ▷Condition을 걸어서 분산을 구해야 하는 경우

 ▷Computing Expectation by condition을 이용한다.

 

 ◎Gemmatric random variale (확률 p)

  ▷E[N] = 1/p

  ▷Condition Y -> 1: 처음이 성공 / 0: 처음이 실패

  ▷E[N^2|Y=0] = E[(N+1)^2] = E[N^2] + 2E[N] + 1

 

○Computing Probabilities by conditioning

 ▷Condition을 걸어서 확률을 걸어야 하는 경우

 ▷각 조건에서 확률들의 합을 구한다.

 

 ◎사고가 일어날 횟수(n)에 대한 확률

  ▷사고 빈도가 λ일때, 내년에 사고가 n번 일어날 확률 - Poisson(λ)

  ▷사고 빈도 λ - Exp(λ)

  ▷Gamma Random Variable의 PDF를 이용

 

 ◎Ballet Problem

  ▷선거에서, 출마자 A(n표 받음)와 B(m표 받음)가 있을 때, 개표 방송에서 A가 항상 이길 확률 = (n-m)/(n+m) 임을 증명

  ▷P_n,m = A가 마지막 표를 받았을때, A가 항상 이길확률 × A가 마지막에 표를 받았을 확률 + B가 마지막 표를 받았을때, A가 항상 이길확률 × B가 마지막에 표를 받았을 확률

  ▶수학적 귀납법 (P_n,m = (n-m)/(n+m)에 대해서

   ▷총 개표수가 1일때, 성립한다. 

   ▷총 개표수가 n+m-1 = k인것들에 대해 성립한다면

   ▷총 개표수가 n+m인 것에 대해서도 성립한다.