Coupling method
증명할 때 사용하는 테크닉 중 하나이다. 전혀 관련없는, 독립적인 분포로 부터 나온 random varaiable X와 Y를 random vector W=(X', Y') 로 엮어준다. 이 때 조건이 있는데, X'와 Y'는 각각 X, Y의 marginal distribution 을 유지해야 한다.
Coupling method 종류
1) Independent Coupling : Coupling (X’,Y’) s.t. X’= X, Y’=Y are independent.
2) Monotone Coupling : Coupling (X’,Y’) s.t. P(X’>Y’) = 1 (Used to show stochastic dominance)
Example. Coupling of Bernoulli Variables
위 그림의 설명을 덧붙이자면, X와 Y는 0아니면 1인, 베르누이 랜덤변수이다. X와 Y 둘 다 동전 뒤집기인데, head가 나올 확률이 다르다고 생각하면 된다.
X는 head 나올 확률 Pr(X=1)=q 이고, Y가 head 나올 확률 Pr(Y=1)=r 이다. 이 때, 0<=q<r<=1 이다.
X,Y 의 Independent Coupling (X', Y') 는 X와 Y를 그냥 marginal distribution을 유지하도록 엮어준 것이다. X=1일 때 Y가 0인지 1인지 중요하지 않다.
이와 다르게 monotone coupling은 P(X''<=Y'')=1 조건이 추가되는데, 이에 따라서 X''가 1일 때 Y''는 무조건 1(0 안됨). 따라서 P(Y''=0|X''=1)=0.
Stochastic dominance
Stochastic order :
어떤 랜덤변수가 다른 랜덤변수보다 "더 크다"는 개념을 정량화하는 방법이다.
Usual stochastic order :
Usual stochastic order 는 모든 x에 대해 Pr(A>x)<=Pr(B>x) 을 만족할 때, A is less than B in the "usual stochastic order" 라고 한다. 이 때 some x 에 대해 Pr(A>x)<Pr(B>x) 을 만족하면 이를 A is stochastically strictly less than B, B first-order stochastically dominates A 라고 한다.
즉 first-order stochastically dominant 란, r.v. 의 CDF를 비교했을 때 모든 x에 대해 B의 CDF가 A의 CDF보다 크거나 같다면, B가 first-order stochastically dominates A 라는 것이다.
X first-order stochastically dominates Y :
Pr{X>z}≥ Pr{Y>z} for all z
Stochastic dominance 는 several order로 정의되고, first-order는 그 중 하나이다. zero-th order dominance 는 모든 state 에 대해 A<=B 임을 의미한다. (state-wise dominance)
lower order dominance 가 higher order dominance를 내포한다는 성질이 있다.
따라서 stochastic dominance 이다. = state-wise dominance 이다 라고 생각할 수 있겠다. (내 생각...틀리면 지적부탁..ㅠ)
Example (state-wise dominance $ first-order stochastic dominance) :
1~6까지 state에서 A,B,C를 비교하면, A state-wise dominantes B는 굉장히 납득이 쉽다.
C state-wise dominates B가 false라는 것은, 4~6 state 가 만족하지 않기 때문이다.
C first-order stochastically dominates B 가 성립하는 이유는, B와 C의 CDF를 생각해보면 쉽겠다.
C first-order stochastically dominates A 는 성립하지 않는다. Pr(A>=2)=4/6 > Pr(C>=2)=3/6 이기 때문...
그럼 도대체 Coupling method 와 Stochastic Dominance는 무슨 상관일까?
Coupling method와 Stochastic Dominance의 관계
X,Y 의 monotone coupling 이 존재한다는 것과 Stochastic Dominance 가 필요충분조건이다.
언제 쓰는걸까?
2개의 r.v.을 비교하고 싶을 때, 평균을 비교하는 것보다 stochastic dominance를 비교하는 것이 더 strong한 개념이다.
X stochastically dominates Y 라면, E[X]≥E[Y] 를 보장하기 때문이다. (반대는 성립하지 않는다.)
주로 어떤 알고리즘 또는 policy 의 performance를 비교할 때 사용한다.
따라서 어느 2개의 r.v. 을 비교하고, 이를 증명하기 위한 방법으로 Coupling method 를 사용하여 Stochastic Dominance를 증명한다.
출처 :
https://people.math.wisc.edu/~roch/mdp/roch-mdp-chap4.pdf
'수학' 카테고리의 다른 글
| Martingale (0) | 2021.08.01 |
|---|