저불일치 수열

저불일치 수열(低不一致數列, low-discrepancy sequence)은 수열의 N번째항까지의 불일치측도(discrepancy)가 작은 수열이다. 이러한 수열을 준난수열(quasirandom sequence)라고도 한다. 준난수를 일반적인 난수나 의사 난수 대신 사용하면 수치적분 성능이 개선된다.

준난수의 장점

난수를 사용하지 않는 분할 방법은 데이터포인트의 수가 늘어나면 기존의 결과를 버리고 다시 계산해야 하는데, 난수를 이용한 몬테카를로 방법은 그럴 필요는 없지만 데이터포인트가 불균일하게 분포하여 정확도에 문제가 생긴다. 그러나 준난수를 사용하면 기존의 결과를 버리지 않고 다시 데이터포인트를 추가할 수 있어 유리하다. 준몬테카를로 방법에 사용된다.

방법

무리수 사용 방법

모든 무리수 $\alpha$에 대해

$s_{n}=\{s_{0}+n\alpha \}$

는 좋은 준난수가 된다.

이것은 a가 1이고 m이 1인 선형 합동 생성기의 특별한 경우이다.

$r_{i}=(ar_{i-1}+c){\bmod {m}}$

위 식에서 c가 황금비의 소수부일 때 성능이 아주 좋다고 알려져 있으나, 백은비를 사용할 수도 있다. 다차원에서는 소수의 제곱근(의 소수부)를 사용할 수 있다.

기타

네덜란드의 요하네스 판데르코르퓟이 만든 판데르코퓟 수열(Van der Corput sequence), 영국의 J. H. Halton이 만든 홀턴 수열(Halton sequence), 러시아에서 만들어진 소볼 수열(Sobol sequence) 등이 있다.

같이 보기

• 준몬테카를로 방법
• 마르코프 연쇄 몬테카를로 방법
• 희소 격자