Optimization 심화 : Random process (5, Stochastic process)

 

모바일 앱 환경에서는 latex 수식이 깨져 나타나므로 가급적 웹 환경에서 봐주시길 바랍니다.

 

오늘은 Random process에서 매우 중요한 개념 중 하나인 'stopping time' 특히 Optinal stopping theorem에 대해 이야기학자 한다.

 

Ranom process $(X_n)$이 supermartingale이고 filtration $(\mathcal{F}_n)$-measurable 하다고 하자.

그러면 우리는 다음과 같은 결과를 얻을 수 있다. (Induction을 사용하면 된다)

 

$\mathbb{E}(X_n) = \mathbb{E}(\mathbb{E}(X_n|\mathcal{F}_{n-1})) \le \mathbb{E}(X_{n-1}) \le \cdots \le \mathbb{E}(X_0)$.

 

첫 번째 등식은 $X_n$이 filtration에 adapted돼 있기 때문이고, 두 번째 부등식은 Super martingale의 정의이다.

이를 귀납적으로 반복하면 최종적으로 $\mathbb{E}(X_0)$로 upper bound를 잡을 수 있다.

이를 도박꾼의 '운' 예시에 빗대어 이야기하면 현재 시점에서 n번째 결과를 확인하기 전, 도박꾼의 '운'은 super-martingale 상황에서는 초기의 '운'보다 더 좋을 순 없다는 이야기이다. (일반적으로, 좋지 못한 상황으로 볼 수 있다.)

즉, 이러한 불공정한 도박 게임에 있어서 도박꾼은 내가 이번 판에도 배팅을 해야 할지, 말아야 할지 결정을 할 필요가 있다. 

도박꾼의 '운'은 초기의 '운'보다 좋지 못하고, 도박꾼은 현재 n번째 게임을 진행할지 말지 결정하고자 한다.

(즉, 이미 n-1번의 도박은 진행한 상태이고 이에 대한 정보들은 'filtration'에 정보로 담겨져 있다.)

 

자, 그럼 이를 좀 더 확장시켜서 도박꾼이 난 'n-1'번만 게임할 거야! 라고 결정하지 못한 상태라고 해보자.

도박꾼이 임의의 시점 $\tau \in T$에 게임을 stop한다고 해보자. 그러면 $\mathbb{E}(X_{\tau})$에 대해서도 귀납적으로 맨 위와 같은 부등식을 유도하는 것이 가능할까? 여기서 우리는 한 가지 짚고 넘어가야 한다.

여기서 time step $\tau$도 random variable이다. 임의의 시점 $\tau$에 도박꾼이 게임을 stop하는 상황을 모델링한다면 $X_n$도 stochastic process이고 (random) stopping time $t$도 random variable이다.

따라서 $X_{\tau}$도 새로운 random variable이다.

 

이때 도입되는 개념이 'stopping time'이다.

Definition은 다음과 같다.

 

Filtered probability space $(\Omega, \mathcal{F}, \mathcal{F}_n, \mathbb{P})$에서 정의된 Random variable $\tau \in \mathbb{N}$이 있다고 하자.

만약 $\{ \tau = n \} \in \mathcal{F}_n$이 모든 n에 대해 참이라면 $\tau$는 stopping time이다.

 

즉, random time 또한 filtration에 adapted돼 있다, measurable하다는 이야기인데 이는 결국 내가 어느 시점 $\tau$에 멈출지는 이전까지의 정보들을 활용해서 결정될 것이라는 의미이다.

즉, 현재 시점에 멈출지 말지에 대한 결정은 이전 시점까지의 정보들이 누적돼있는 filtration에 근거해서 내려질 것이라는 의미이고, 미래 시점에 대한 정보는 활용 불가능하다는 이야기이다.

 

자, 그러면 $X_n^{\tau} := X_{n \wedge \tau}$라 하자.

stopping tiem $\tau$ 이후로는 더 이상 Random process가 정의되지 않으므로 (멈췄으므로),

$X_{\tau +1}, X_{\tau + 2}, X_{\tau + 3} \cdots$는 더 이상 정의되지 않는다.

즉, $X_n$과 $X_{\tau}$중 n이 더 작으면 잘 정의되지만 n이 더 클 땐 더 이상 정의되지 않는다.

이 새로운 Random process를 $X_n^{\tau}$로 표기하도록 하자.

 

그러면 원래 $\{X_n\}$이 super-martingale이었다면, $\{X_n^{\tau}\}$도 super-martingale이다.

이를 확인해보자.

 

$\mathbb{E}(X_{n+1}^{\tau} - X_n^{\tau} | \mathcal{F}_n) = \mathbb{E}((X_{n+1} - X_n) 1 \{T > n \} | \mathcal{F}_n) = 1 \{T > n \} \mathbb{E}(X_{n+1} - X_n | \mathcal{F}_n) = 1 \{T> n \} (\mathbb{E}(X_{n+1}|\mathcal{F}_n -X_n) \le 0$

 

첫 번째 등식은 $X_n^{\tau}$의 정의를 적용한 것이고, 두 번째 등식은 다음의 indicator function $1 \{T > n \}$도 measurable (adapted to filtration)함을 이용한 것이다.

그 이유는 다음과 같다.

$\{T > n\} = \{T = 1\}^{c} \cap \{T = 2 \}^{c} \cap \cdots \cap \{T = n\}^{c} \in \mathcal{F}_n$

 

이는 $\sigma$-algebra, filtration의 정의에 의거한다.

 

자, 그러면 매우 중요한 정리인 Optinal stopping theorem에 대해 보도록 하자.

(여기서는 super-martingale에 대해서만 이야기하지만 martingale / sub-martingale에 대해서도 적용가능하다.)

 

<가정>

1. $(X_n)$이 filtration에 measurable한 super-martingale이라 하자.

2. time $\tau$가 같은 filtration에 measurable한 stopping time이라 하자.

 

그러면 다음 두 가지 조건 중 적어도 하나를 만족하면 $\mathbb{E}(X_T) \le \mathbb{E}(X_0)$이다.

1. $c \in \mathbb{R}$가 있을때, 모든 $n$에 대하여,

$|X_n^{\tau}| \le c$이고, $\mathbb{P}(\tau < \infty) = 1$이다.

 

2. $c \in \mathbb{R}$가 있을 때, 모든 $n$에 대하여,

$\mathbb{E}(|X_{n+1} - X_n| I\{T > n \} | \mathcal{F}_n) \le c$이고 $\mathbb{E}(\tau) < \infty$이다

 

 

첫 번째 조건에서는 stopping time $\tau$가 (almost surely) finite하다는 조건이 있고, 두 번째에는 in-expectation finite하다는 조건이 있다.

또한 첫 번째 조건에서는 random variable의 norm이 $c$로 upper bound된다는 조건이 있고, 두 번째는 차이가 $c$로 conditional upper bound된다는 조건이 있다.

 

이를 증명하기 위해서는 'monotone convergence theorem'과 'dominated convergence theorem'을 알아야 한다.

이에 대해서는 다음 글에서 살펴보자.

 

마지막으로 앞서 이야기한 예시, 도박꾼의 '운'을 통해 optional stopping theorem을 다시 한 번 살펴보자.

super-martingale 상황에서 우린 도박꾼의 '운'은 초기의 '운'보다 더 좋을 수 없다고 이야기했다.

즉, 도박을 얼마나 하든 현재 시점에서의 '운'이 초기의 '운을 넘을 수 없는 것이다.

그렇다면 도박꾼이 random stopping을 하여도 그 시점에서의 '운'은 초기의 '운'을 넘지 못하는 것이다.

이는 사실상 도박꾼에게 있어서는 절망적인 이야기이다.

결국, 자신이 어떤 전략을 쓰든 애시당초 게임이 unfavourable하면, (= super-martingale) 결국 초반의 '운'보다 더 좋은 '운'을 가질 순 없다는 이야기이다.