* 추계적 과정의 의미는? 수학적으로 일부의 결과를 가지고 전체의 결과를 예상하여 계산하는 것.

위키에서 설명하는 Renewal theory의 의미는 아래와 같다. 

Renewal theory is the branch of probability theory that generalizes Poisson processes for arbitrary holding times. Applications include calculating the best strategy for replacing worn-out machinery in a factory and comparing the long-term benefits of different insurance policies.

Renewal theory는 푸아송과정을 모체로하는 확률이론의 한 분야이다. 본 이론이 쓰이는 예는, 공장에서 낡아빠진 장비의 교체 주기를 계산하거나, 전구의 수명이 다하는 것을 예상하여 아 주 긴주기에서의 교체주기를 예상하여 손이익을 계산하고자 할때 사용 될 수 있다. 

Introduction

A renewal process is a generalization of the Poisson process. In essence, the Poisson process is a continuous-time Markov process on the positive integers (usually starting at zero) which has independent identically distributed holding times at each integer i (exponentially distributed) before advancing (with probability 1) to the next integer:i+1. In the same informal spirit, we may define a renewal process to be the same thing, except that the holding times take on a more general distribution. (Note however that the independence and identical distribution (IID) property of the holding times is retained).

푸아송을 배울때 알게되는 Inter-arrival time 이라는 개념이 본  Renewal theory를 설명할 때 사용되었으므로 푸아송을 참고하기 바란다.  Renewal theory는 holding time을 제외한 더욱 일반적인 분포라고 볼수가 있다. 

Formal definition[edit]

Sample evolution of a renewal process with holding times S_i and jump times J_n.

Let  be a sequence of positive independent identically distributed random variables such that

We refer to the random variable  as the "th" holding time.  is the expectation of .

Define for each n > 0 :

each  referred to as the "th" jump time and the intervals

being called renewal intervals.

Then the random variable  given by

(where  is the indicator function) represents the number of jumps that have occurred by time t, and is called a renewal process.

holding times S1~Sn은 각각 IID를 따르는 Random variable을 의미하며 그 평균값은 0보다 큰 양의 값이다.

그냥 간단히 말해서, 예를들어, 푸아송 분포에서 미리 선정한 arrival rate값에 따라 사건을 발생시켰을때의 각 사건들의 발생은 서로 IID하며 그때의 사건마다 주기는 J1~ Jn까지라고 할수가 있다.

*Holding time이란? 만약 어떤 공장에서 사용하나 기계들이 존재할 때, 다른 하나의 기계가 고장나기전 하나의 기계가 고장났을때, 두 고장시간 사이의 시간간격이라고 볼 수 있다. (기계의 고장=이벤트로 볼수가 있으므로, 두 이벤트가 발생할때, 그 두 이벤트 발생시간 사이의 시간간격을 말한다.)

만약 어느 특정한 사건 n시점에서의 사건으로가서 생각해보자. 

Jn은 n번째가 되기에 필요한 Si [1,n] 시간의 모든 합이라 할수있으며, 

Jn에서 그 다음 사건인 n+1 사이의 interval은 [Jn,Jn+1] 이라고 정의하며, 이를 renewal intervals라고 부른다. 

Random variable Xt 는 위와 같이 정의되는데, Jn이 시간 t 안에 포함된다면 그때의 최 상한선 값을 Xt라고 부르며

이를 renewal process라고 한다. 

Renewal-reward processes[edit]

Let  be a sequence of IID random variables (rewards) satisfying

Then the random variable

is called a renewal-reward process. Note that unlike the , each  may take negative values as well as positive values.

The random variable  depends on two sequences: the holding times  and the rewards  These two sequences need not be independent. In particular,  may be a function of .

Y축 값 W1~Wn 값들은 IID 조건을 만족하며 유한할때,

이때 Random variable Yt는 1부터 Xt 까지의 모든 W값들의 합 으로 정의된다.

W는 -와 +값으로 표현이 가능하며, 이를테면 손해와 이득에 대한 표현이 가능한 변수이다. 

따라서 Wi = rewards 는 시간 t에서 연속적인 cost의 losses/gains의 총합을 말한다.

In probability theory and statistics, a sequence or other collection of random variables is independent and identically distributed (i.i.d.) if each random variable has the same probability distribution as the others and all are mutually independent.[1]

The abbreviation i.i.d. is particularly common in statistics (often as iid, sometimes written IID), where observations in a sample are often assumed to be effectively i.i.d. for the purposes of statistical inference. The assumption (or requirement) that observations be i.i.d. tends to simplify the underlying mathematics of many statistical methods (see mathematical statistics and statistical theory). However, in practical applications of statistical modeling the assumption may or may not be realistic. To test how realistic the assumption is on a given data set, the autocorrelation can be computed, lag plots drawn or turning point test performed.[2] The generalization of exchangeable random variables is often sufficient and more easily met.

The assumption is important in the classical form of the central limit theorem, which states that the probability distribution of the sum (or average) of i.i.d. variables with finite variance approaches a normal distribution.

Note that IID refers to sequences of random variables. "Independent and identically distributed" implies an element in the sequence is independent of the random variables that came before it. In this way, an IID sequence is different from a Markov sequence, where the probability distribution for the nth random variable is a function of the previous random variable in the sequence (for a first order Markov sequence). An IID sequence does not imply the probabilities for all elements of the sample space or event space must be the same.[3] For example, repeated throws of loaded dice will produce a sequence that is IID, despite the outcomes being biased.

줄여서 i.i.d.는 어떠한 랜덤 확률변수의 집합이 있을때 각각의 랜덤 확률변수들은 독립적이면서 (자기 사건의 발생의 영향이 다른 랜덤 확률변수에게 미치지 않을 때) 동일한 분포를 가질때를 의미한다.

예를들어서, 이항확률 분포 (성공 or 실패)를 가지는 동전던지기를 3회 실시한다고 가정하자.

각각의 시행은 이전이나 이후의 시행에 영향을 주지않는 독립시행이며 각각의 시행에서 나오는 동전의 앞,뒤에 대한 결과값의 분포는 동일한 이항확률 분포를 따르기 때문에 이는 i.i.d.라고 할수 있다.

만약 이를 코드화나 모델링화 시킨다면, 변수의 값을 선택할 때 정의된 동일한 확률분포에서 표본을 선택한다면 이를 i.i.d.한 확률 표본이 된다고 할수가 있다.

Poisson Processes (Oxford Studies in Probability) J.F.C kingman

http://bookzz.org/book/1101923/2628fe

http://www.math.uni.wroc.pl/~pms/files/26.1/Article/26.1.5.pdf

The Poisson process is one of the most important random processes in probability theory. It is widely used to model random "points" in time and space, such as the times of radioactive emissions, the arrival times of customers at a service center, and the positions of flaws in a piece of material. Several important probability distributions arise naturally from the Poisson process--the Poisson distribution, the exponential distribution, and the gamma distribution. The process has a beautiful mathematical structure, and is used as a foundation for building a number of other, more complicated random processes.

마르코프체인(Markov Chain)   AI / Tip  2010/02/02 01:58

원문출처 :  http://blog.naver.com/ojs83/120100904784   ::  http://happyengine.tistory.com/

마르코프체인(Markov Chain)은 마르코프성질(Markov Property)을 지닌 이산 확률과정(discrete-time stochastic process)을 의미한다.

확률과정이란 무엇인가?

확률과정(stochastic process or random process)이란 어떤 확률분포에 의해 벌어지는 일련의 연속현상들을 수학적으로 모델링하는데 사용되는 개념이다.

가장 간단한 확률과정을 예로 들자면 베르누이과정이 있겠다. 베르누이과정(Bernoulli Process)은 독립적으로 수행되며 오로지 두 결과값만을 갖는 사건이 연속적으로 발생할때, 그 결과값의 열을 모델링하는데 사용된다. 베르누이실험(Bernoulli trial)이라는 것이 "결과가 랜덤하게 둘 중 하나만 나오는 실험"이고, 베르누이 랜덤변수(Bernoulli random variable)이라는것이 베르누이실험의 결과 중 하나는 1로 하나는 0으로 매핑시켜주는 함수니까, 베르누이과정을 좀 더 수학스럽게 얘기하자면, "베르누이 랜덤변수 값의 열" 이라고 할 수 있겠다.

그럼 베르누이과정으로는 무엇을 모델링할 수 있을까? 동전던지기의 결과열이 그 대표적인 예가 되겠다. "앞뒤뒤앞앞뒤앞뒤.." 와 같은 열. 이런 열은 어떤 모델에 의해 생성이 되었냐는 물음에, 바로 "베르누이과정"에 의해 생성되었다고 하면 된다는 얘기다. 이 베르누이 과정에 의해 생성되는 열은 "앞뒤뒤앞앞뒤앞뒤..."가 될 수도 있고, "뒤뒤앞뒤앞뒤앞..."이 될 수도 있겠다.

이보다 아주 조금 복잡한 확률과정을 들자면, 포아송과정(Poisson Process)가 있겠다. 이 과정은 시간축 위에서 독립적으로 랜덤하게 발생하는 사건들의 열을 의미한다. 예를 들자면, 어떤 서버에 있는 홈페이지가 방문되는 사건들이나, 내 전화기에 걸려오는 전화들 같은 것들이 되겠다.또 조금만 생각을 달리하면, 책한권에 있는 오타들 도 될 수 있다. 위에서 예를 든 동전던지기의 경우, 만일 "앞"이 나오는 사건들의 열을 생각한다면, 이것도 포아송과정이다.

왜 이것들이 포아송과정인가? 모두 얘기하자면 매우 수학적이 될것같다. 간단히만 얘기하자면, 몇가지 사소한 조건만 만족할 경우, 이 포아송과정에 의해 발생하는 사건들에는 포아송분포를 따르는 특징이 있기 때문이다. 무엇이 포아송 분포를 따르냐 하면, 바로 특정 시간동안에 발생하는 사건의 수이다.

예를 들어, 10분동안 홈페이지가 방문될 회수가 어떤 확률분포를 따를지 곰곰히 생각해보자. 평균잡아 10분에 5번정도 방문되더라 하는 기존의 계산이 있었다면, 아마도 5번 방문될 확률이 제일 클 것이다. 4번이나 6번은 그보다 조금 작고, 3번이나 7번은 좀 더 작고, 그럴것이다. 이 분포가 포아송분포를 따름이 증명이 되어 있다는 얘기다

베르누이과정이 이산 확률과정인데 반해 포아송과정은 연속 확률과정이다. 베르누이과정에서는 시간의 개념이 1회,2회,3회와 같이 이산적이지만, 포아송과정에서는 0초부터 무한대까지 연속공간의 특정위치이기 때문이다.

그럼 이제 마르코프체인을 알아보도록 하자.

마르코프체인도 어쨌건 이산확률과정이므로 뭔가 1회,2회,3회에 발생하는 사건의 열을 의미하겠다. 중요한건 마르코프성질을 지닌다는 것이다. 그럼 마르코프성질이란 무엇인가? 마르코프성질이란 n+1회의 상태(사건의 결과)가 오로지 n회에서의 상태(사건의 결과)에만 영향을 받는것을 의미한다. 결과가 랜덤하게 나오는 동전던지기는 분명 마르코프성질을 따르지 않는다. 지금 던졌을때 나온 결과가 다음 던졌을때의 결과에 전혀 영향을 주지 않기 때문이다.

그러나 세상에는 그렇게 해석될 수 없는 "사건의 열"이 더 많다. 예를 들어, 1일날씨, 2일날씨, 3일날씨 라던가, 아니면 지금 이 글에서 첫번째단어,두번째단어, 세번째단어 등을 생각해보자. 2일의 날씨는 1일의 날씨와 완전히 무관하게 나타나는 현상일까? 아니면 (말이 되는 문장을 쓰지는 않는다고 가정할 때) 다음에 쓸 단어는 바로 이전 단어와 전혀 독립적으로 나타날까? 그렇지 않다. 그렇다고 위에서 든 두가지 예가 마르코프성질을 지니고 있다고 단정하는 것은 아니다. 3일의 날씨가 2일의 날씨와만 상관있다고 할 수 있지도 않고, 다음에 쓸 단어가, 몇단어 이전의 단어와 상관이 있을 수도 있는 것이기 때문이다. 그러나 이러한 현상들을 단순하게 모델링할때는 마르코프체인이라고 가정한다. 이러한 가정이 실제로 모델을 매우 단순하게 만들며, 때로는 이렇게 단순하게 만들어진 모델이 엄청난 위력을 발휘하기도 한다.

마르코프체인을 약간 다르게 해석하자면, n개의 상태가 있고, 그 상태들 중 임의의 상태로 시간에 따라 변해가는 과정을 생각할 수 있다. 예를 들어 상태가 {R, G, B} 이렇게 세개가 있다면, 첫번째는 G, 두번째는 R, 세번째는 G, 네번째는 G, 다섯번째는 B, 여섯번째는 B, 일곱번째는 R ... 이렇게 말이다.

물론 마르코프 성질을 지니니까, 두번째에 어떤 상태를 가질지는 첫번째 상태가 무엇이었냐에 따라 결정되고, 세번째는 두번째 상태에, 네번째는 세번째 상태에 의해 결정된다. 여기서 주의할것이 있다. 위 예를 보면, 첫번째 상태는 G였고 두번째상태는 R인 경우도 있고, 세번째 상태가 G일때 네번째 상태가 G인 경우도 있다. 즉, 마르코프체인은 "상태가 G일때 무조건 X상태로 간다" 이렇게 만들어지는게 아니라, "상태가 G일때 다음 상태가 R일 확률은 얼마, G일 확률은 얼마, B일 확률은 얼마" 이런식으로 정의된다.

따라서, 마르코프체인에서는 "상태전이확률"(state transition probability) 행렬이 핵심이 되고, 이 확률들을 사용하면 아래와 같은 다이어그램이 그려진다. 

이 게 머냐하면, 아주 간단한 영어문장뼈대의 생성과정을 Markov Chain으로 묘사한 그림이다. <start>는 시작상태, ART는 관사상태, V는 동사상태, N은 명사상태, P는 전치사상태이다. 즉 <start>상태에서 관사상태와 명사상태로 갈 확률이 각각 71%, 29%이고, 명사상태에서 다시명사, 동사, 전치사상태로 갈 확률은 각각 13%, 44%, 46% 라는거다. 이 모형에 따르면, 아주 여러가지 형태의 문장들이 생성될 수 있을 것이다. 이 모형은 음성인식과 자연언어처리의 품사태깅(각 형태소에 적절한 품사를 자동으로 부착하는 작업)의 근간으로 아주 오랫동안 사용되어져왔으며, 지금도 사용되고 있다. 시간이 되면 Hidden Markov Model(은닉 마르코프 모형)이라고 하는 잘 알려진 모형에 대해서도 한번 써보려 한다.

여하간, 중요한 수식 등 자세한건 좀 더 인터넷을 찾아보면 공부할 수 있을 것이고...

그렇다면, 마르코프체인과 구글의 페이지랭크는 어떤 관계가 있을까?

이 제 페이지랭크와 이 마코프체인의 관계를 생각해보자. 그러기 위해 지구상에 존재하는 모든 웹페이지들과 그 페이지간에 걸려있는 링크들을 위의 다이어그램에 매핑시켜보자. 그리고 임의의 한 페이지에서 링크를 따라 아무데로나 페이지를 따라가는 Random Surfer(랜덤서퍼)를 생각해보자. 링크에 위에서처럼 확률값이 붙어야 하는데, 확률값은 대충 준다. 어떻게 주냐면, 어떤 페이지에 링크가 2개면 각 링크를 따라 다른페이지로 갈 확률은 각각 50%, 50%라고 하고, 10개면 10%, 10%..., 10% 라고 그냥 하자. 

대충 저 위의 다이어그램하고 매핑이 되는지?

페이지랭크는 웹을 이런 단순한 구조로 추상화하는데서 시작됐다. 웹을 각 페이지가 노드이고 링크가 간선이며, 간선위의 확률값은 그 간선이 출발한 노드(페이지)에 위치한 링크수분의 1로 단정짓고, 일단 마르코프 체인을 그린거다. 그리고 어떤 문제를 푸냐하면, 이런 마르코프체인 위에서 Random Surfer가 마구 이동을 해대다가 누군가 Stop! 이라 외쳤을때, 각 노드(페이지)에 위치할 확률을 구한것이다. 그 값이 제일 높은 노드가 바로 인터넷상에서 가장 권위있는 페이지라는 것이다!

이렇게 한번 예를 들어보자. 나랑 내 친구 철수랑 그의 친구 영희랑 그의 오빠 영철이랑 네명이 각각 홈페이지를 갖고 있고 거기에 네이버 홈페이지, 이렇게 딱 다섯개의 웹페이지가 있는 공간을 생각해보자. 상식적으로 이 다섯개의 웹페이지에 링크들이 어떻게 서로가 서로를 가리키고 있을지 가정해보고, Random Surfer를 그 마르코프체인위에 올려놓고 돌아다니라고 해보자. 그리고 몇분후에 Stop했을때, 그 Random Surfer가 어디있을 가능성이 제일 클것같은가?

거의 예외없이 네이버홈페이지라 생각할 것이다. 왜냐하면 머리속에 그린 그림은, 네이버가 제일 화살표를 많이 받고 있었기 때문일 것이다. 대충 그렇다. 근데 꼭 많이 받고 있는다고 거기에 머물 확률이 제일 큰건 아니다. 여기서부터 이제 임의의 순간에 각 페이지에 머물러 있을 확률을 구하기 위한 몇가지 수학공식들이 나오게 되는 것이다. 

좀 더 수식적으로 깊이 이해하려면, 구글의 창업자 중 한명인 세르게이 브린이 직접 쓴 논문 (번역판) 이나, 기타 여러가지 강의자료 등을 직접 구해 읽어보는게 제일 좋을것이다. 

세 르게이 브린의 논문에는 Markov Chain이라는 용어가 언급도 되어 있지 않은데, 많은 사람들은 브린이 논문을 쓸 당시 Markov Chain에 대해서는 모르고 있었다는 얘기가 있다. 바꿔 말하면, Markov Chain에 대해 열심히 연구하던 사람들은 따로 있고, 세르게이는 그와 똑같은 생각을 해서, 시스템을 만들고 막대한 부를 거머쥐었다고나 할까~