확률적 시뮬레이션

확률적 시뮬레이션은 개별 확률로 확률적으로(임의적으로) 변화할 수 있는 변수를 갖는 시스템을 시뮬레이션하는 것이다.^[1]

이러한 랜덤 변수의 실현이 생성되어 시스템 모델에 삽입된다. 모델의 출력을 기록한 다음 새로운 랜덤 값 집합을 사용하여 프로세스를 반복한다. 이러한 단계는 충분한 양의 데이터가 수집될 때까지 반복된다. 결국, 산출물의 분포는 가장 가능성이 높은 추정치와 변수들이 어느 범위의 값에 속할 것인지에 대한 기대치를 보여준다.^[1]

종종 모델에 삽입된 랜덤 변수는 RNG(Random Number Generator)가 있는 컴퓨터에서 생성된다. 그런 다음 난수 발생기의 U(0,1) 균일한 분포 출력은 시스템 모델에서 사용되는 확률 분포와 함께 난수 변수로 변환된다.^[2]

어원

Stochastic은 원래 "추측을 할 수 있는 능력"을 의미했고, 그리스 스토하스티코스에서 "추측할 수 있는 능력, 추측"을 의미했다. "스토하즈타이"에서, "추측, 목표, 목표, 표적, 마크"에서. "무례하게 결정된"이라는 감각은 1934년 독일의 스토차스티크로부터 처음 기록되었다.^[3]

이산 이벤트 시뮬레이션

확률적 시뮬레이션에서 다음 사건을 결정하기 위해 모델 상태에 대한 가능한 모든 변경의 비율을 계산한 다음 배열로 정렬한다. 다음으로 배열의 누적합계를 취하며, 최종 셀은 숫자 R을 포함하며, 여기서 R은 총 사건 발생률이다. 이 누적 배열은 이제 이산형 누적분포로서, 무작위 숫자 z~U(0,R)를 선택하고 첫 번째 사건을 선택함으로써 다음 사건을 선택하는 데 사용될 수 있다. 예를 들어 z는 그 사건과 관련된 비율보다 작다.

확률분포

확률 분포는 랜덤 변수의 잠재적 결과를 설명하는 데 사용된다.

변수가 이산형 값에서만 취할 수 있는 결과를 제한한다.^[4]

베르누이 분포

A random variable X is Bernoulli-distributed with parameter p if it has two possible outcomes usually encoded 1 (success or default) or 0 (failure or survival)^[5] where the probabilities of success and failure are ${\displaystyle P(X=1)=p}$ and ${\displaystyle P(X=0)=1-p}$ where ${\display$$스타일 0\leq p\leq 1$

무작위 숫자 생성기에 의해 만들어진 U(0,1) 균일한 분포로부터 베르누이 분포로 랜덤 변수 X를 생성하기 위해, 우리는 정의한다.

${\displaystyle X={\begin{case}1,&{\text{{}if }0\leq U<p\\0,&\text{{}}if{1}\gth U\geq p\end{case}}}}}$

such that the probability for${\displaystyle P(X=1)=P(0\leq U<p)=p}$and ${\displaystyle P(X=0)=P(1\geq U\geq p)=1-p}$.^[2]

예: 동전 던지기

정의

머리가 올라오면 X = 1이고 꼬리가 올라오면 X = 0 

공정한 동전의 경우, 두 가지 실현 가능성은 동등하다. We can generate realizations of this random variable X from a ${\displaystyle U(1,0)}$ uniform distribution provided by a random number generator (RNG) by having ${\displaystyle X=1}$ if the RNG outputs a value between 0 and 0.5 and${\displaystyle X=0}$ if the RNG outputs a value between 0.5 and 1.

P(X = 1) = P(0 ≤ U < 1/2) = 1/2 

P(X = 0) = P(1≥ U ≥ 1/2) = 1/2 

물론 두 가지 결과가 동등하지 않을 수도 있다(예: 치료의 성공).^[6]

이항 분포

매개변수 n과 p를 가진 이항 분포 랜덤 변수 Y는 버누이-분산 랜덤 변수 X₁, X, ..., X의_2n^[4] 합으로 얻는다.

예: 동전은 세 번 던져진다. 정확히 두 개의 머리를 얻을 확률을 찾아라. 이 문제는 샘플 공간을 보면 해결할 수 있다. 머리가 두 개인 방법은 세 가지가 있다.

HHH, HHT, HT, TH, TH, THT, THT, HTT, TTT 

답은 3/8(= 0.375)이다.^[7]

포아송 분포

포아송 공정은 사건들이 시간이나 공간의 간격에서 무작위로 발생하는 공정이다.^[2][8] 시간 간격 당 일정한 비율 λ을 갖는 포아송 공정에 대한 확률 분포는 다음 방정식으로 주어진다.^[4]

${\displaystyle P(k{\text{ interval}})={\frac {\lambda ^{k}e^{-\lambda }}}}{k!}}}$

${\displaystyle \mathrm{시간}}$ 간격 $t{\displaystyle }$ ${\displaystyle N(t)}$을(를${\displaystyle )}$ 시간 간격 t ${\displaystyle t}$에서 발생하는 이벤트 수로 정의$$

${\displaystyle P(N(t)=k)={\frac {(t\lambda )^{k}{k!}}e^{-t\\da }}}$

$F{\displaystyle }$ ( t${\displaystyle }$)${\displaystyle }$= 1${\displaystyle }$- e - ${\displaystyle t^{}}$ $displaystyle F(t)=1-e^{-t}{\lambda }}$의 누적분포함수(CDF)로 이벤트에 대한 도착 간 시간이 기하급수적으로 분포한다는 것을 알 수 있다$.$ 지수 CDF의 역은 다음과 같다.

${\displaystyle t=-{\frac {1}{\\fracda }}{\ln(u)}$

여기서 $u{\displaystyle }$ ${\displaystyle u}$은(는) $U{\displaystyle }$( 0${\displaystyle }$, ${\displaystyle 1}$) ${\displaystyle U(0,1)}$ 균일하게$$ 분포된 랜덤 변수다.^[2]

$간격$[t t ${\displaystyle t_{}}$ ${\displaystyle t_{}}$ ${\displaystyle a_{}}$ r ${\displaystyle t_{}}$ ${\displaystyle t_{}}$ ${\displaystyle {}_{}}$ n ${\displaystyle d_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle$$N}$에 대해$$ 일정한 비율 $\lambda {\displaystyle }$ ${\$$displaystyle \lambda$ $}$을(를$)$^[9] 갖는 Poisson 프로세스를 시뮬레이션하는 작업은 다음 알고리즘을 사용하여 수행할 수 있다$$$.{\displaystyle }$

1. $N{\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle N=0}$ 및 $t$ = ${\displaystyle {}_{}}$ t ${\displaystyle t_{}}$ ${\displaystyle t_{}}$ ${\displaystyle t_{}}$ ${\displaystyle t_{}}$ ${\$로 시작하십시오.
2. $U{\displaystyle (}$0${\displaystyle }$, ${\displaystyle 1}$) ${\displaystyle$ U$(0,1$) 균일$$ 분포에서$$ 랜덤 변수 $u{\displaystyle }$ ${\displaystyle u}$ 생성
3. $t{\displaystyle }$= ${\displaystyle t}$+ (${\displaystyle }$- ${\displaystyle 1}$/ ${\displaystyle \lambda }$) ${\displaystyle l}$ ${\displaystyle n}$ (${\displaystyle u}$ ) ${\displaystyle t=t+(-1/\lambda )ln(u$)}을$($를) 사용하여 시간 업데이트
4. > > t e ${\$인 경우 중지하십시오. 그렇지 않으면 5단계를 계속하십시오.
5. ${\displaystyle N=N+1}$
6. 2단계 계속

방법들

직접 및 첫 번째 반응 방법

1977년 댄 길레스피에 의해 출판되었으며, 누적 배열에 대한 선형 검색이다. 길레스피 알고리즘을 참조하십시오.

길레스피의 확률적 시뮬레이션 알고리즘(SSA)은 본질적으로 그러한 시스템에 내재된 무작위성을 적절히 고려하여 잘 긴장된 화학 반응 시스템의 시간 진화를 수치적으로 시뮬레이션하는 정확한 절차다.^[10]

그것은 화학 마스터 방정식의 기초가 되고 결정론적 반응 속도 방정식(RRE)이 OSE에 의해 수학적으로 대표되는 것보다 시스템 진화의 보다 현실적인 표현을 제공하는 동일한 마이크 물리학적 전제에 엄격하게 기초하고 있다.^[10]

화학 마스터 방정식과 마찬가지로 SSA는 대량 반응 물질의 한계에서 질량 작용의 법칙과 동일한 용액으로 수렴한다.

차반응법

2000년 깁슨과 브루크가 출판했다.^[11] 사용하지 않은 반응 시간을 재사용하는 1차 반응 방식보다 개선된 것이다. 반응 샘플링을 보다 효율적으로 만들기 위해 인덱스된 우선 순위 대기열을 사용하여 반응 시간을 저장한다. 한편, 프로포즈의 재평가를 보다 효율적으로 하기 위해, 종속성 그래프를 사용한다. 이 의존성 그래프는 특정 반응이 발생한 후 어떤 반응을 보일지 알려준다.

최적화 및 정렬 직접 방법

2004년과^[12] 2005년 출판. 이러한 방법은 알고리즘의 평균 검색 깊이를 줄이기 위해 누적 배열을 정렬한다. 전자는 반응의 발화 빈도를 추정하기 위해 전자를 운영하고 후자는 누적 배열을 즉시 분류한다.

로그직접법

2006년에 출판되었다. 이는 누적 어레이에 대한 이진 검색이므로 반응 샘플링의 최악의 시간 복잡성을 O(log M)로 줄인다.

부분확대법

2009년, 2010년, 2011년 발행(Ramaswamy 2009, 2010년, 2011년) (더 많은) 반응 개수가 아닌 네트워크의 종 수에 따라 확장하기 위한 계산 비용을 줄이려면 인자화된 부분 반응 개수를 사용하십시오. 네 가지 변종이 존재한다.

• PDM, 부분-확대형 직접법. 네트워크의 커플링 등급에 관계 없이, 반응 네트워크의 다른 종의 수에 따라 선형적으로 확장되는 계산 비용을 갖는다(Ramaswamy 2009).
• SPDM, 정렬 부분확대 직접법. 동적 거품 정렬을 사용하여 반응 속도가 여러 개의 크기(Ramaswamy 2009)에 걸쳐 있는 다중 척도 반응 네트워크에서 계산 비용의 사전 인자(pre-factor)를 줄인다.
• PSSA-CR, 구성 거부 샘플링이 있는 부분확대 SSA. 합성 거부 샘플링(Slepoy 2008)을 사용하여 약하게 연결된 네트워크(Ramaswamy 2010)에 대해 일정한 시간(즉, 네트워크 크기와 무관)으로 계산 비용 절감
• dPDM, 지연 부분확대 직접법. 지연 SSA 방법(Bratsun 2005, Cai 2007)의 부분적 확장 변형을 제공함으로써 시간 지연이 발생하는 대응 네트워크(Ramaswamy 2011)로 PDM을 확장한다.

부분확대 방법의 사용은 기본적인 화학 반응, 즉 최대 두 개의 서로 다른 반응 물질과의 반응으로 제한된다. 모든 비원소 화학반응은 네트워크 크기의 선형적(반응 순서에 따라) 증가를 희생하여 일련의 기본적인 화학반응으로 균등하게 분해될 수 있다.

근사 방법

확률적 시뮬레이션의 일반적인 단점은 대형 시스템의 경우 시뮬레이션에서 모두 고려할 수 없는 너무 많은 사건이 발생한다는 것이다. 다음 방법은 시뮬레이션 속도를 일부 근사치로 극적으로 향상시킬 수 있다.

τ 도약법

SSA 방법은 각 전환을 추적하기 때문에, 높은 시간 복잡성으로 인해 특정 애플리케이션에 대해 구현하는 것은 비현실적일 것이다. Gillespie는 정확성 손실을 최소화하면서 계산 시간을 단축하는 근사 절차인 타우-리프팅 방법을 제안했다.^[13] SSA 방법에서와 같이 각 시간 단계에서 X(t)를 추적하면서 증분 단계를 수행하는 대신, 타우-리프팅 방법은 한 하위 절간에서 다음 하위 절간으로 도약하여 주어진 하위 절간 동안 얼마나 많은 전환이 발생하는지 근사하게 된다. 비약값인 τ은 하위간격[t, t + τ]을 따라 전환율의 가치에 유의미한 변화가 없을 정도로 작다고 가정한다. 이 상태를 도약조건이라고 한다. 따라서 타우 리핑 방법은 많은 전환을 한 번의 도약으로 시뮬레이션하면서 상당한 정확도를 잃지 않는 장점이 있어 계산 시간이 빨라진다.^[14]

조건부 차이 방법

이 방법은 가역 가능한 프로세스의 반대되는 사건의 순 속도만 고려함으로써 가역 가능한 프로세스(임의의 보행/확산 프로세스를 포함한다)에 근사치를 적용한다. 이 방법의 주요 장점은 모델의 이전 전환율을 새롭고 효과적인 속도로 대체하는 간단한 if-statement로 구현할 수 있다는 것이다. 따라서 기존 SSA와 같이 대체된 변환 속도를 가진 모델을 해결할 수 있다.^[15]

연속 시뮬레이션

불연속 상태 공간에서는 연속적인 공간의 특정 상태(값)를 명확하게 구별하지만 특정 연속성 때문에 가능하지 않다. 시스템은 보통 모델의 변수인 시간이 지남에 따라 변화한 다음, 지속적으로 변화한다. 따라서 연속 시뮬레이션은 상태 변수의 변화 속도를 결정하는 미분방정식을 주어진 시간 경과에 따라 시스템을 시뮬레이션한다.^[16] 연속 시스템의 예로는 포식자/프리 모델^[17] 또는 카트 폴 밸런싱이 있다.

확률분포

정규 분포

그 확률 변수 X가 확률 변수의 밀도는 공식[4]에 의해 fX()) 주어진다로 매개 변수와 σ, XN(μ, σ2)∈ 단축, μ 정상적으로 분배되어야 할 일고 있다고 한다 12π σ 2e−()− μ)22σ 2.{\displaystyle f_{X}())={\frac{1}{\sqrt{2\pi \sigma ^{2}}}}e^{-{\frac{{2(x-\mu)^}}.{2\s$이그마 ^{2}}}}.$$}$ x$$ ∈ R.^[4]

많은 것들이 실제로 일반적으로 분포되어 있거나 그것에 매우 가까이 있다. 예를 들어 높이와 지능은 근사적으로 정규 분포를 따른다. 측정 오류도 정규 분포를 따르는 경우가 많다.^[19]

지수 분포

지수 분포는 포아송 공정에서 사건 사이의 시간, 즉 사건이 일정한 평균 속도로 연속적이고 독립적으로 발생하는 과정을 설명한다.

지수 분포는 예를 들어, 특정 사건이 일어날 때까지 기다려야 하는 시간을 모형화하려는 경우, 대기열 이론에서 인기가 있다. 예를 들어, 다음 고객이 상점에 들어갈 때까지의 시간, 특정 회사의 채무 불이행까지의 시간 또는 일부 기계에 결함이 있을 때까지의 시간이 포함된다.^[4]

학생의 t-분포

학생의 t-분포는 금융에서 자산 수익의 확률론적 모델로 사용된다. 그 티분포의 밀도 함수는 다음 방정식:[4]f(t)xΓ(ν+12)ν π Γ(ν 2)(1+t2ν)− ν+12,{\displaystyle f(t)={\frac{\Gamma)}{{\sqrt{\nu \pi}}\,\Gamma({\frac{\nu}{2}})}}\left(1+{\frac{t^{2}}{\nu}}\right)^{-{\frac 주어진다. {)$nu +1}{2}}:},\!}$

여기서 $\nu {\displaystyle }$ ${\displaystyle \nu}$은(는) 자유도 수이고 $\gamma {\displaystyle \mathrm{}}$ ${\displaystyle \Gamma}$은(는) 감마함수다.

n의 큰 값의 경우 t-분포는 표준 정규 분포와 유의하게 다르지 않다. 일반적으로 값 n > 30의 경우 t-분포는 표준 정규분포와 동일한 것으로 간주된다.

기타분포

• 일반화된 극단값 분포

조합 시뮬레이션

완전히 다른 세계관을 사용함으로써 하나와 같은 시스템을 모델링하는 것이 종종 가능하다. 문제의 이산 이벤트 시뮬레이션과 그에 대한 연속 이벤트 시뮬레이션(연속적인 흐름을 방해하는 이산 이벤트와의 연속 시뮬레이션)은 결국 같은 해답을 도출할 수 있다. 그러나 때때로 이 기술은 시스템에 대한 다른 질문에 대답할 수 있다. 반드시 모든 질문에 답해야 하거나, 모델이 어떤 목적으로 사용될 것인지 모르는 경우, 조합된 연속/분리 방법론을 적용하는 것이 편리하다.^[20] 유사한 기법은 시간과 공간에 의존하는 방식으로 이산적이고 확률적인 설명에서 결정론적이고 연속적인 설명으로 변할 수 있다.^[21] 이 기법을 사용하면 기존의 길레스피 알고리즘보다 시뮬레이션이 훨씬 빠르면서도 작은 복사 번호로 인한 노이즈를 포착할 수 있다. 또한 결정론적 연속체 설명을 사용하면 임의의 대형 시스템의 시뮬레이션을 가능하게 한다.

몬테카를로 시뮬레이션

몬테카를로는 추정 절차다. 어떤 랜덤 변수의 평균값을 알 필요가 있고 그 분포가 명시될 수 없는 경우, 그리고 분포에서 표본을 추출할 수 있는 경우, 표본을 추출하여 독립적으로, 평균화하여 추정할 수 있다는 것이 주된 생각이다. 표본이 충분하다면, 대수의 법칙에 따르면 평균은 참 값에 가까워야 한다. 중심 한계 정리는 평균이 참값을 중심으로 가우스 분포를 갖는다고 말한다.^[22]

간단한 예로, 복잡하고 불규칙한 윤곽선으로 형상의 면적을 측정해야 한다고 가정합시다. 몬테카를로 접근법은 모양 주위에 정사각형을 그려서 정사각형을 재는 것이다. 그리고 가능한 한 한결같이 광장에 다트를 던진다. 모양에 떨어지는 다트의 분수는 정사각형 면적에 대한 모양 면적의 비율을 제공한다. 사실, 거의 모든 본질적인 문제, 또는 평균화 문제를 이 형태로 던져 넣는 것은 가능하다. 외곽선 안에 있는지, 몇 개의 다트를 던질지 파악할 수 있는 좋은 방법이 필요하다. 마지막으로 중요한 것은 다트를 균일하게 던져야 한다는 것이다. 즉, 좋은 무작위 숫자 생성기를 사용해야 한다.^[22]

적용

Monte Carlo Method의 사용 가능성은 매우 크다.^[1]

• 랜덤 변수 생성을 이용한 통계 실험(예: 주사위)
• 표본 추출법
• 수학(예: 수치적 통합, 다중 통합)
• 신뢰성 엔지니어링
• 프로젝트 관리(SixSigma)
• 실험입자물리학
• 시뮬레이션
• 리스크 측정/리스크 관리(예: 포트폴리오 가치 추정)
• 경제(예: 가장 적합한 수요 곡선 찾기)
• 프로세스 시뮬레이션
• 오퍼레이션 리서치

난수생성기

시뮬레이션 실험(몬테 카를로 포함)의 경우 (변수의 값으로) 난수를 생성해야 한다. 문제는 컴퓨터가 매우 결정론적인 기계(기본적으로 각 프로세스 뒤에는 항상 알고리즘이 존재하며, 출력으로 입력을 변경하는 결정론적 계산이 존재하므로 정의된 간격이나 집합에 걸쳐 균일하게 분산된 무작위 숫자를 생성하기가 쉽지 않다는 점이다.^[1]

난수 발생기는 결정론적 특성으로 "쉽게" 식별될 수 없는 일련의 숫자를 생성할 수 있는 장치다. 이 순서를 확률적 숫자의 순서라고 한다.^[23]

알고리즘은 일반적으로 프로세스에서 가능한 하나의 결과인 실현을 생성하기 위해, 컴퓨터가 생성한 숫자들은 실제 무작위 숫자를 모방하는 유사 숫자에 의존한다.^[24]

무작위 번호를 얻는 방법은 오랫동안 존재해 왔고 많은 다른 분야(예: 게임)에서 사용되고 있다. 그러나 이 숫자들은 일정한 편견에 시달린다. 현재 진정으로 무작위 시퀀스를 만들 것으로 기대되는 최선의 방법은 양자 현상의 무작위 특성을 이용하는 자연적인 방법이다.^[23]

참고 항목

• 결정론적 시뮬레이션
• 길레스피 알고리즘
• 네트워크 시뮬레이션
• 네트워크 트래픽 시뮬레이션
• 시뮬레이션 언어
• 큐잉 이론
• 디스커트화
• 하이브리드 확률 시뮬레이션

참조

• (Slepooy 2008): Slepoy, A; Thompson, AP; Plimpton, SJ (2008). "A constant-time kinetic Monte Carlo algorithm for simulation of large biochemical reaction networks". Journal of Chemical Physics. 128 (20): 205101. Bibcode:2008JChPh.128t5101S. doi:10.1063/1.2919546. PMID 18513044.
• (Bratsun 2005): D. Bratsun; D. Volfson; J. Hasty; L. Tsimring (2005). "Delay-induced stochastic oscillations in gene regulation". PNAS. 102 (41): 14593–8. Bibcode:2005PNAS..10214593B. doi:10.1073/pnas.0503858102. PMC 1253555. PMID 16199522.
• (Cai 2007): X. Cai (2007). "Exact stochastic simulation of coupled chemical reactions with delays". J. Chem. Phys. 126 (12): 124108. Bibcode:2007JChPh.126l4108C. doi:10.1063/1.2710253. PMID 17411109.
• Hartmann, A.K. (2009). Practical Guide to Computer Simulations. World Scientific. ISBN 978-981-283-415-7. Archived from the original on 2009-02-11. Retrieved 2012-05-03.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 17.7. Stochastic Simulation of Chemical Reaction Networks". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
• (Ramaswamy 2009): R. Ramaswamy; N. Gonzalez-Segredo; I. F. Sbalzarini (2009). "A new class of highly efficient exact stochastic simulation algorithms for chemical reaction networks". J. Chem. Phys. 130 (24): 244104. arXiv:0906.1992. Bibcode:2009JChPh.130x4104R. doi:10.1063/1.3154624. PMID 19566139. S2CID 4952205.
• (Ramaswamy 2010): R. Ramaswamy; I. F. Sbalzarini (2010). "A partial-propensity variant of the composition-rejection stochastic simulation algorithm for chemical reaction networks" (PDF). J. Chem. Phys. 132 (4): 044102. Bibcode:2010JChPh.132d4102R. doi:10.1063/1.3297948. PMID 20113014.
• (Ramaswamy 2011): R. Ramaswamy; I. F. Sbalzarini (2011). "A partial-propensity formulation of the stochastic simulation algorithm for chemical reaction networks with delays" (PDF). J. Chem. Phys. 134 (1): 014106. Bibcode:2011JChPh.134a4106R. doi:10.1063/1.3521496. PMID 21218996.

외부 링크

소프트웨어

• Cayenne - 빠르고, Python 패키지를 사용하여 확률적 시뮬레이션을 수행하십시오. 직접, tau-leapping 및 tau-adaptive 알고리즘의 구현.
• StochSS - StochSS: Stochastic Simulation Service - Stochastic 생화학적 시스템의 모델링 및 시뮬레이션을 위한 클라우드 컴퓨팅 프레임워크.
• ResAssure - 확률적 저장장치 시뮬레이션 소프트웨어 - 모든 지질학적 실현을 위해 완전히 암묵적이고 동적인 3상 유체 흐름 방정식을 해결한다.
• 가인 - 화학 운동학의 확률적 시뮬레이션. 직접, 다음 반응, 타우 리핑, 하이브리드 등
• pSSAlib - 모든 부분 확장 방법을 C++로 구현.
• StochPy - Python의 확률적 모델링
• STEPS - Swig를 사용하여 C/C++ 코드에 대한 Python 인터페이스를 생성하는 경로 시뮬레이션용 STocastic Engine