Poisson 및 Binomial 랜덤 숫자를 생성하는 알고리즘?

StackOverflow https://stackoverflow.com/questions/1241555

문제

나는 둘러보고 있었지만 어떻게 해야할지 잘 모르겠습니다.

내가 찾았 어 이 페이지 마지막 단락에서 다음과 같이 말합니다.

포아송 분포에서 가져온 임의의 숫자에 대한 간단한 생성기는이 간단한 레시피를 사용하여 얻습니다.1, x2, ...는 0과 1 사이의 균일 분포를 갖는 랜덤 숫자의 시퀀스이며, k는 제품 x의 첫 번째 정수입니다.1 · x2 · ... · xK+1 <e-λ

내가 찾았 어 다른 페이지 이항 번호를 생성하는 방법을 설명하지만, Poisson Generation의 근사치를 사용하고 있다고 생각합니다.

예를 들어, 이항 랜덤 숫자를 고려하십시오. 이항 임의의 숫자는 단일 던지기에 헤드의 확률 P가있는 동전의 N 던지기의 헤드 수입니다. 간격 (0,1)에서 n 균일 랜덤 숫자를 생성하고 p보다 작은 숫자를 계산하는 경우, 카운트는 매개 변수 n 및 p를 가진 이항 임의 숫자입니다.

나는 그것을 할 수있는 라이브러리가 있다는 것을 알고 있지만, 언어가 제공하는 표준 균일 생성기 (이 경우 Java) 만 사용할 수 없습니다.

도움이 되었습니까?

해결책

포아송 분포

여기에 있습니다 Wikipedia가 Knuth가 그렇게 말하는 방식:

init:
     Let L ← e^(−λ), k ← 0 and p ← 1.
do:
     k ← k + 1.
     Generate uniform random number u in [0,1] and let p ← p × u.
while p > L.
return k − 1.

자바에서는 다음과 같습니다.

public static int getPoisson(double lambda) {
  double L = Math.exp(-lambda);
  double p = 1.0;
  int k = 0;

  do {
    k++;
    p *= Math.random();
  } while (p > L);

  return k - 1;
}

이항 분포

10 장 불균일 랜덤 변형 생성 (PDF) Luc Devroye (내가 찾은 것을 발견했습니다 위키 백과 기사) 이것은 이것을 제공합니다 :

public static int getBinomial(int n, double p) {
  int x = 0;
  for(int i = 0; i < n; i++) {
    if(Math.random() < p)
      x++;
  }
  return x;
}

참고하십시오

이러한 알고리즘 중 어느 것도 최적이 아닙니다. 첫 번째는 O (λ)이고 두 번째는 O (n)입니다. 이러한 값이 일반적으로 얼마나 큰지, 생성기를 얼마나 자주 호출 해야하는지에 따라 더 나은 알고리즘이 필요할 수 있습니다. 위의 링크 된 논문에는 일정한 시간 내에 실행되는 더 복잡한 알고리즘이 있지만, 그 구현을 독자를위한 운동으로 남겨 두겠습니다. :)

다른 팁

이것과 다른 수치 문제에 대해 성경은 수치 레시피 책입니다.

C에 대한 무료 버전이 있습니다. http://www.nrbook.com/a/bookcpdf.php (플러그인 필요)

또는 Google 도서에서 볼 수 있습니다. http://books.google.co.uk/books?id=4t-sybvuoqoc&lpg=pp1&ots=5ihminlhho&dq=numerical%20Recipes%20In%20C&pg=pp1#v=onepage&q=&f=false

C 코드는 Java로 쉽게 전송해야합니다.

이 책은 많은 수치 문제를 위해 금의 무게가 가치가 있습니다. 위 사이트에서 최신 버전의 책을 구입할 수도 있습니다.

KIP가 게시 한 답변은 작은 도착률 (Lambda)으로 Poisson RV를 생성하는 데 완벽하게 유효하지만 Wikipedia에 게시 된 두 번째 알고리즘 Poisson Random 변수 생성 수치 안정성으로 인해 더 큰 도착률에 대해 더 좋습니다.

나는 이로 인해 Poisson RV를 생성하는 프로젝트 중 하나를 구현하는 동안 문제에 직면했습니다. 그래서 나는 다른 방법을 제안합니다.

다음 라이브러리 (Java Code)에는 CERN의 몇 가지 구현이 있습니다.

http://acs.lbl.gov/~hoschek/colt/

이항 랜덤 숫자와 관련하여 1988 년 "이항 랜덤 변형 생성"의 논문을 기반으로하며 최적화 된 알고리즘을 사용하기 때문에 권장합니다.

문안 인사

이것을 build.gradle에 추가 할 수 있습니다

implementation 'org.kie.modules:org-apache-commons-math:6.5.0.Final'

그리고 클래스를 사용하십시오 POISSONDOPTRITION 수업 poissondotribution에 대한 자세한 내용

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top