베가스 알고리즘

베가스 알고리즘은 G. Peter Lepage로 인해,^[1][2][3] 알려진 또는 대략적인 확률 분포 함수를 사용하여 통합의 해당 영역에 검색을 집중시키고 최종 적분에 가장 큰 기여를 하는 방법으로 몬테카를로 시뮬레이션에서 오류를 줄이는 방법이다.

베가스 알고리즘은 중요도 샘플링을 기반으로 한다.이 ${\displaystyle 값}$은 f ,${\displaystyle$f$,}$ 함수에 의해 설명된 확률 분포로부터 점을 샘플링하여 점들이 적분에 가장 큰 기여를 하는 영역에 집중되도록 한다$$.GNU 과학 도서관(GSL)은 라스베가스의 루틴을 제공한다.

샘플링 방법

일반적으로, 볼륨 $\Omega {\displaystyle \mathrm{}}${\$displaystyle \Oomega}$에 $대한{\displaystyle }$ f$${\$displaystyle$f}의 몬테 카를로 적분을${\displaystyle }$g ,$${\$displaystyle g$${\displaystyle \}}$ $함수{\displaystyle }$ g${\displaystyle }$, ${\displaystyle \mathrm {E} _{g}(f;N)$에 의해 기술된 확률 분포된 점으로 샘플링하면 추정치$$ E${\displaystyle {}_{}}$를 얻는다.

${\displaystyle \mathrm {E} _{g}(f;N)={1 \over N}\sum _{i}^{N}{f(x_{i}})/g(x_{i})}.}$

그러면 새 추정치의 분산은

${\displaystyle \mathrm {Var} _{g}(f;N)=\mathrm {Var}(f/g;N)}$

where ${\displaystyle \mathrm {Var} (f;N)}$ is the variance of the original estimate, ${\displaystyle \mathrm {Var} (f;N)=\mathrm {E} (f^{2};N)-(\mathrm {E} (f;N))^{2}.}$

If the probability distribution is chosen as ${\displaystyle g= f /\textstyle \int _{\Omega } f(x) dx}$ then it can be shown that the variance ${\displaystyle \mathrm {Var} _{g}(f;N)}$ vanishes, and the error in the estimate will be zero.실제로 임의 함수에 대한 정확한 분포 g에서 표본을 추출할 수 없으므로 중요도 샘플링 알고리즘은 원하는 분포에 대한 효율적인 근사치를 산출하는 것을 목표로 한다.

확률 분포의 근사치

VEGAS 알고리즘은 함수 f를 히스토그램화하는 동안 통합 영역을 여러 번 통과함으로써 정확한 분포에 근사치를 낸다.각 히스토그램은 다음 통과에 대한 표본 분포를 정의하는 데 사용된다.점증적으로 이 절차는 원하는 분포로 수렴된다.In order to avoid the number of histogram bins growing like ${\displaystyle K^{d}}$ with dimension d the probability distribution is approximated by a separable function: ${\displaystyle g(x_{1},x_{2},\ldots )=g_{1}(x_{1})g_{2}(x_{2})\cdots }$ so that the n필요한 빈의 양은 Kd에 불과하다.이는 통합의 투영에서 좌표 축으로 함수의 피크를 찾는 것과 같다.베가스의 효율성은 이 가정의 타당성에 달려있다.통합의 정점이 잘 현지화될 때 가장 효율적이다.만약 통합이 대략 분리 가능한 형태로 다시 작성될 수 있다면, 이것은 라스베가스와의 통합의 효율성을 증가시킬 것이다.

참고 항목

• 라스베이거스 알고리즘
• 몬테카를로 통합
• 중요도 샘플링

참조