하나의 확률 세트를 사용하여 다른 [중복] 생성

Question

이 질문에는 이미 답변이 있습니다.

• 무작위 범위를 1~5에서 1~7로 확장 답변 77개

더 작은 확률 세트에서 더 큰 확률 세트를 생성하려면 어떻게 해야 합니까?
이것은 알고리즘 설계 매뉴얼 -Steven Skiena에서 발췌한 것입니다.
큐:

동일한 확률로 {0,1,2,3,4}에서 숫자를 생성하는 난수 생성기(rng04)를 사용하여 0부터 7(rng07)까지의 숫자를 동일한 확률로 생성하는 난수 생성기를 작성하시겠습니까?

지금까지 약 3시간 동안 시도했는데 대부분 2개의 합을 기준으로 했습니다. rng04 출력.문제는 이 경우 각 값의 확률이 다르다는 것입니다. 4는 5/24 확률로 올 수 있지만 0은 1/24입니다.가릴 수 있는 방법을 몇 가지 시도했지만 그럴 수 없습니다.

누군가 이 문제를 해결할 수 있나요?

Answer 1

두 개의 난수 세트(첫 번째 및 두 번째 난수)를 결합하는 방법을 찾아야 합니다. {0,1,2,3,4} ) 그리고 만든다 n*n 뚜렷한 가능성.기본적으로 문제는 추가하면 다음과 같은 결과가 나온다는 것입니다.

        X
      0 1 2 3 4

  0   0 1 2 3 4
Y 1   1 2 3 4 5
  2   2 3 4 5 6
  3   3 4 5 6 7
  4   4 5 6 7 8

중복이 있는데 원하는 것이 아닙니다.두 세트를 결합하는 한 가지 가능한 방법은 다음과 같습니다. Z = X + Y*5 어디 X 그리고 Y 두 개의 난수입니다.그러면 다음과 같은 결과가 나올 것입니다.

        X
       0  1  2  3  4

  0    0  1  2  3  4
Y 1    5  6  7  8  9
  2   10 11 12 13 14
  3   15 16 17 18 19
  4   20 21 22 23 24

이제 더 큰 난수 세트가 있으므로 그 반대의 작업을 수행하여 더 작게 만들어야 합니다.이 세트에는 25 고유한 값(5로 시작하고 두 개의 난수를 사용했기 때문에 5*5=25).원하는 세트에는 8개의 고유한 값이 있습니다.이를 수행하는 순진한 방법은 다음과 같습니다.

x = rnd(5)  // {0,1,2,3,4}
y = rnd(5)  // {0,1,2,3,4}
z = x+y*5   // {0-24}
random07 = x mod 8

이것은 실제로 다양한 범위를 가질 것입니다 {0,7}.그러나 가치는 {1,7} 3/25번 나타나고 값은 0 4/25 번 나타납니다.이 때문입니다 0 mod 8 = 0, 8 mod 8 = 0, 16 mod 8 = 0 그리고 24 mod 8 = 0.

이 문제를 해결하려면 위의 코드를 이에 맞게 수정하면 됩니다.

do {
  x = rnd(5)  // {0,1,2,3,4}
  y = rnd(5)  // {0,1,2,3,4}
  z = x+y*5   // {0-24}
while (z != 24)

random07 = z mod 8

이것은 하나의 값을 취합니다 (24) 그것은 당신의 확률을 버리고 버리는 것입니다.이와 같이 '나쁜' 값을 얻은 경우 새 난수를 생성하면 알고리즘이 약간 더 오래 실행됩니다(이 경우 실행 시간의 1/25는 실행하는 데 2배, 1/625는 3배가 걸립니다 길다 등등).그러나 그것은 당신에게 올바른 확률을 줄 것입니다.

Answer 2

물론 실제 문제는 합계 중간 (이 경우 4)의 숫자가 많은 조합 (0+4, 1+3 등)에서 발생하지만 0과 8은 정확히 한 가지 방법을 가지고 있다는 사실입니다. 생산됩니다.

이 문제를 해결하는 방법을 모르겠지만 문제를 조금 줄이려고 노력할 것입니다. 고려해야 할 사항 :

• 0-7 범위에는 8 개의 가능한 값이 있으므로 궁극적으로 목표로해야 할 가능한 총 상황의 수는 8의 배수가되어야합니다.이 방법으로 해당 코 도메인에서 값 당 값당 분포 수를 가질 수 있습니다.
• 두 밀도 함수의 합을 취할 때, 가능한 상황의 수 (입력의 다른 순열 측면에서 합을 평가할 때 반드시 구별되는 것은 아닙니다)는 각 입력 세트의 크기의 제품과 같습니다.
• 따라서 두 개의 {0,1,2,3,4} 세트가 함께 합산되면 5*5 = 25 가능성이 있습니다.
• 5의 전력에서 8 명 (첫 번째 포인트 참조)을 얻는 것은 불가능합니다 (두 번째 포인트 참조를 참조하십시오. 발생하면 기능을 수행하고 무시하십시오.
• 이 시점에서 볼 수있는 한 가장 간단한 방법은 두 개의 {0,1,2,3,4} 세트 (25 개 가능성)의 합을 사용하고 1 (24를 남기기 위해 24 개, 다중을 남기는 것)의 합을 사용하는 것입니다. 8).
• 따라서 문제는 이제 이것으로 줄어 들었습니다. 8 출력 값 중 나머지 24 개 가능성을 배포하는 방법을 찾으십시오. 이를 위해서는 합을 사용하고 싶지 않고 입력 값 만 사용하고 싶을 것입니다.

그렇게하는 한 가지 방법은 입력으로 구성된 기본 5의 숫자를 상상해보십시오. 44를 무시하고 (25 번째, 불필요한 가치입니다. 당신이 그것을 얻는다면, 새로운 입력 세트를 종합하고, 다른 입력을 모듈로 8 개로 가져 가면, 24 가지 다른 입력 조합 (각각 3)에서 0-7을 얻을 수 있습니다. 동일한 분포입니다.

Answer 3

내 논리는 다음과 같습니다.

rn07 = 0;
do {
  num = rng04;
}
while(num == 4);

rn07 = num * 2;
do {
  num = rng04;
}
while(num == 4);

rn07 += num % 2