# 마팅게일 ## 마팅게일(Martingale)이란? **공정한 게임** 이란? : 번까지의 누적된 정보를 조건으로 번째 게임에서의 기대금액을 구하면 번째 게임 후 그가 갖고 있던 금액이 되는 게임 ------ 다음의 상황을 생각해 보자. 동영이는 이길 확률, 질 확률이 인 일련의 게임을 하는데, 시작 베팅금액은 1000원이다. 게임은 이길때까지 진행하며, 패할 경우 다음 게임에서는 두배를 베팅한다. 이 게임에서, 동영이가 영원히 게임을 질 확률은 이다. 따라서 언젠가는 이기게 되고, 그 언젠가에( 번째라 하자) 이겼을 때 동영이가 받게 되는 돈은 원 고작 1000원이다. 즉, 동영이는 자본금이 무한해야 고작 1000원을 얻는 게임을 하고 있었던 것이다. ------ 위와 같은 베팅 방식을 마팅게일 전략이라고 하며, 실제로는 1)배당*승리확률1인 도박이 없고 2) 자본금은 유한하므로 돈을 벌기 힘든 멍청한 전략이기 때문에, 프랑스 마르티그 지방 사람들의 어리석음에 빗댄 것에서부터 유래하였다고 한다. 위 게임을 일반화하여 수리적 형태로 생각해보자. 각 게임의 결과를 확률변수 으로 나타내어, 여기서 은 도박사가 이긴 사건을 나타낸다. 를 도박사의 초기자본, 번째 게임에 거는 베팅금액을 이라고 하면, 번째 게임 후 총 자본금은 가 되고, 이 식에서 을 얻을 수 있고 이를 이용하면, 이와 같이 이 게임은 앞에서 정의한 공정한 게임이 된다. 즉, 이기거나 질 확률이 동일한 게임에서 과거의 전적에 근거한 베팅전략을 세우면 공정한 게임이 되는 것이다. 위 동영이의 게임에서도, 번째 게임을 진 후 동영이의 수익은 이고, 번째 게임에서 승리하면 동영이의 수익은 1000원, 또 지면 이 될 것이다. 또한 아래의 식이 성립힌다. 따라서, 즉, 동영이의 게임도 공정한 게임이라는 것을 알 수 있다. 이렇게 공정한 게임의 성질 과 같은 성질을 마팅게일 이라고 한다. 마팅게일은 다음과 같이 정의할 수 있다. ------ 확률과정 이 다음 조건을 만족하면 을 에 대한 **마팅게일**이라고 한다. (1) (2) 여기서 (2)식 대신 를 만족하는 은 **열마팅게일(submartingale)**, 를 만족하면 **우마팅게일(supermartingale)** 이라고 한다. ------ 시간까지 얻게 되는 모든 정보집합을 이라고 하면, 시간 이 증가할수록 정보집합은 증가하게 된다. 각 게임의 결과를 이라고 하면, 게임 후의 정보집합 이 되고, 번째 게임 후에 정보집합은 이 된다. 이를 이용하여 위 마팅게일의 정의를 다시 나태내면 ------ 다음 조건을 만족하면 확률과정 을 마팅게일 이라고 부른다. (1) 이 주어지면 을 알 수 있다. (2) (3) ------ ## 마팅게일의 예 **ex1** 은 평균이 0이고 독립동등분포를 하는 확률과정들의 열이고, 이라고 두면 이 성립하므로, 는 마팅게일이다. **ex2** 은 독립동등분포를 하는 확률과정들의 열이고, 이라고 두면 다음이 성립한다. 단일때 이면 은 마팅게일이 된다. 이면 은 열마팅게일, 이면 은 우마팅게일이 된다. **ex3** 는 인 확률변수이고, 은 증가하는 정보집합이라 할때, 이라 두면, 이므로, 은 마팅게일이다. # 대기행렬이론(Queueing Theory) 고객이 특정 서비스 지점에 도착하여 차례가 올 때까지 일정시간 줄을 서서 기다린 뒤 서비스를 받고 떠나는 체계를 **대기행렬체계**라고 하고, 이를 연구하는 학문을 **대기행렬이론**이라고 한다. 대기행렬체제는 다음과 같이 대기행렬체계를 특정짓는 몇가지 요소들을 부호를 이용하여 간단히 표현한다. ------ A - 도착과정(시스템의 상태와 독립적으로 고객이 도착하는 분포) B - 서비스 과정(고객에 대한 서비스 시간의 분포) 위 두가지 분포는 각각 상황에 대해 독립동등분포를 가정한다. c - 서비스 제공자 수(=서버의 수) d - 시스템 용량(시스템에 머물 수 있는 최대허용 고객 수) E - 서비스 방식 ------ 위 A, B에 쓰이는 M은 Markovian 또는 Memoryless - 지수분포, 포아송 프로세스를 G는 일반적인 분포 D는 확정적분포를 의미한다. 대기행렬이론에서 관심을 가지는 것들은, 도착률을 , 서비스율 , 서버 수 이라고 할 때, (1) 제공로드 : 단위 시간당 도착하는 고객들이 시스템에게 주는 평균 부하량 즉 (단위시간당 도착률) x (고객당 평균 서비스시간)이 된다. (2) 교통밀도 : 서버당 할당되는 제공로드 = 단위시간당 도착하는 고객들이 갖고 오는 부하 때문에 서버 한 명이 바쁠 것으로 예상되는 평균시간 (3) 처리로드 : 제공로드 중 실제로 처리되는 로드 이고, 이때 는 손실확률이라고 하며, 이는 시스템에 도착하였지만 용량초과 및 기타 이유로 시스템 안으로 들어오지 못하고 떠난 비율을 나타낸다. (4) 서버 이용률 : 1개의 서버에 할당되는 처리로드를 가리킨다. 또한 대기행렬체계에 대한 대표적 성능척도는 (1) 시스템 고객수 : 서비스를 받고 있는 고객까지 포함한 시스템 내에 있는 총 고객 수를 말한다. (2) 대기 고객 수 : 줄에서 대기 중인 고객수를 말한다. (3) 대기시간 : 고객이 도착하여 서비스를 받기 직전까지 줄에서 보내는 총 시간 (4) 체제시간 : 입력시점부터 시스템을 떠날 때까지 시스템 내에 머문 총 시간을 말한다. 대기행렬체계에서 필요한 몇가지 기본정리들은, **(1) Burke's 정리** 한 명씩 도착하고 한 명씩 서비스를 받고 나가는 무한용량 대기행렬 시스템에서는 도착시점의 확률과 이탈시점의 확률이 같다. 따라서, 도착시점에서 시스템 내에 명을 관찰할 확률은 이탈시점에서 시스템 내에 명을 관찰할 확률과 같다 **(2) PASTA** 도착과정이 포아송과정이면 전체 고객 중에 시스템 내의 고객 수가 명을 관찰하는 고객의 비율은 전체 시간 중 시스템 내의 고객 수가 명이 되는 시간의 비율과 같다. **(3)Little의 법칙** : 시스템으로 들어오는 고객의 입력률 : 시스템 내의 평균 고객 수 : 줄 위에 있는 평균 고객 수 : 시스템 내에 머무는 평균 체제시간 : 줄 위에서 보내는 평균 대기시간 이라고 하면 다음이 성립한다. 이는 (평균 고객 수) = (고객의 도착률) x (고객의 평균 대기시간) 이 성립하는 것을 의미한다. ## 마르코비안 대기행렬체계 마르코비안 대기행렬체계 : 고객의 도착과정이 모수 인 포아송과정을 따르고, 서비스 시간은 모수 인 지수분포를 따르는 대기행렬시스템을 일컫는다. FCFS(First Come First Served)의 서비스 방식을 가정한다. 를 시점에 시스템 안에 있는 고객 수라 하고 의 극한값이 존재하면 이를 이라 하자. 이다. 이러한 을 안정확률 이라고 부른다. 마르코비안 대기행렬체제를 생사과정으로 설명하면, 균형방정식 을 이용하여 을 구할 수 있다. 이 되고 이면 을 이용하여 각각의 을 구할 수 있다. ### M/M/1 체계 M/M/1 Queueing System은 생사과정으로 나타낸다면 다음과 같이 나타낼 수 있다. 이때 이라 하고, 이라고 하면, 일 때, 이 된다. 따라서 시스템이 안정될 조건은 즉, 이 되며, 이 되고, 이면 이 된다. 즉, 시스템 내의 고객 수는 기하분포를 따름을 알 수 있고, 오랜 시간이 흐른 후 서비스 제공자가 쉬고 있을 확률은이 됨을 알 수 있다. 또한 평형상태에서 체계 안의 평균 대기자수를 이라고 하면, 이제, 일때 체계 안에서 기다리는 시간의 분포에 대해 생각해보면, 고객이 도착했을 때 명의 고객이 체계 내에 있으면, 새로 도착한 고객이 체계 내에서 보내는 총 시간이 먼저 온 명의 서비스 시간 + 본인의 서비스 시간이 되므로, 시스템내에서의대기시간줄에서의대기시간번째고객의서비스시간 이라고 하면, 이 된다. 이때 지수분포의 memoryless property 때문에 각각 서비스 시간은 iid를 하게 된다. 따라서, 시스템 내에 있는 고객의 수가 명일때, 새로이 들어오는 고객이 체계 내에서 보내는 시간 의 분포는, 이 된다. 여기에 총 확률 이론을 적용하면, 명이먼저와있다 이 되고, 이를 정리하면, 을 얻는다. 따라서, 는 모수가 인 지수분포를 따르며, 이 된다. 이를 이용하면, 이 성립함을 확인할 수 있다. ### M/M/ 체계 무한이 많은 서비스 제공자가 있다면, 모든 고객은 줄에서 기다리지 않고 서비스를 받을 수 있을 것이다. 따라서, 한 고객이 시스템을 떠나는 비율은 서비스 시간의 모수 가 되고, 명의 고객이 체계를 떠나는 비율은 가 된다. 따라서, M/M/ 는 , 인 생사과정이 되고, 이므로, 을 얻는다. 여기서 임을 쉽게 구할 수 있으며 모든 고객은 도착하자마자 서비스를 받으므로, 고객이 시스템 안에서 보내는 시간은 오직 자기 자신이 서비스를 받는 시간인 모두 인 지수분포이다. 이며 여기서도 임을 확인할 수 있다. ### M/M/s 체계 명의 서버가 있는 모형은 다음이 성립한다. 를 시간에 시스템 내의 고객의 수라 하면 서비스를 받고 있는 사람의 수는 이고, 서비스를 기다리고 있는 사람의 수는 이다. 다음이 성립한다. 여기서 이면 다음이 성립한다. 따라서, 다음이 성립함을 알 수 있다. 따라서 결과적으로 다음이 성립한다. ### M/M/1/k 체계 시스템의 최대 용량이 K일때를 생각해보자. 즉 시스템 안에 이미 명이 있을 때 새로 도착한 고객은 시스템 안에 들어오지 못한다….ㅠㅠ 이 모형에서의 균형방정식은 이때, 이 되므로, 이를 이용하면, 을 얻을 수 있고, 시스템 안의 평균 고객 수는 용량이 유한한 경우에, 도착한 모든 고객이 시스템 내에 있지는 않다. 따라서 시스템 내에 들어간 고객이 시스템 안에서 보내는 평균 시간을 구하기 위해선, 시스템 안에 들어가는 비율을 구하고 이를 이용하여 시스템 안에 들어가는 고객의 도착률을 구한 후 를 구하게 된다. 따라서, 도착한 고객이 시스템 안에 들어갈 확률은 이므로 시스템 안에 들어가는 고객의 도착률이 이 되므로 다음이 성립한다.