"무작위성"이해
나는 이것에 대해 내 머리를 가질 수 없습니다.
rand()
또는
rand() * rand()
진짜 수수께끼라고 생각 해요. 도와 주 시겠어요?
편집하다:
직관적으로 나는 그것들이 똑같이 임의적이라는 수학적 대답이 될 것이라는 것을 압니다. 그러나 나는 당신이 두 번을 함께 곱할 때 "난수 알고리즘을 두 번 실행"한다면 당신은 단순히하는 것보다 더 임의적 인 것을 만들 것이라고 생각합니다. 한 번.
설명
의사 난수 변수 또는 그 곱셈의 무작위성을 발견하려고 할 때마다 이전 답변이 옳지 만 Random () 은 일반적으로 균일하게 분포되어 있지만 Random () * Random () 은 그렇지 않습니다.
예
이것은 의사 난수 변수를 통해 시뮬레이션 된 균일 난수 분포 샘플입니다 .
BarChart[BinCounts[RandomReal[{0, 1}, 50000], 0.01]]
이것은 두 개의 랜덤 변수를 곱한 후 얻는 분포입니다.
BarChart[BinCounts[Table[RandomReal[{0, 1}, 50000] *
RandomReal[{0, 1}, 50000], {50000}], 0.01]]
따라서 둘 다 "무작위"이지만 분포가 매우 다릅니다.
다른 예시
하지만 2 * 랜덤 ()가 균일하게 분포되어있다 :
BarChart[BinCounts[2 * RandomReal[{0, 1}, 50000], 0.01]]
Random () + Random ()은 아닙니다!
BarChart[BinCounts[Table[RandomReal[{0, 1}, 50000] +
RandomReal[{0, 1}, 50000], {50000}], 0.01]]
중앙 한계 정리
중심 극한 정리는 의 합한다고 랜덤 () A와 경향이 정규 분포 용어 증가로.
단 4 개의 용어로 다음을 얻을 수 있습니다.
BarChart[BinCounts[Table[RandomReal[{0, 1}, 50000] + RandomReal[{0, 1}, 50000] +
Table[RandomReal[{0, 1}, 50000] + RandomReal[{0, 1}, 50000],
{50000}],
0.01]]
그리고 여기에서 1, 2, 4, 6, 10, 20 개의 균일 분포 랜덤 변수를 더하여 균일에서 정규 분포로가는 길을 볼 수 있습니다.
편집하다
몇 학점
마지막 두 이미지에 표시된 확률 분포가 Irwin-Hall 분포 로 알려져 있다는 의견을 지적 해 주신 Thomas Ahle 에게 감사드립니다.
그녀의 멋진 torn [] 기능에 대해 Heike 에게 감사 합니다.
내 gutfeel은 rand() * rand()더 많은 0을 시드하기 때문에 덜 무작위 라고 말하지만 두 방법 모두 무작위라고 생각합니다 . 하나 rand()가되는 즉시 0합계는0
둘 다 '더 무작위'가 아닙니다.
rand()의사 난수 시드 (일반적으로 항상 변경되는 현재 시간을 기반으로 함)를 기반으로 예측 가능한 숫자 세트를 생성합니다. 시퀀스에서 연속 된 두 숫자를 곱하면 다르지만 동일하게 예측 가능한 숫자 시퀀스가 생성됩니다.
이것이 충돌을 감소시킬 것인지에 대한 대답은 아니오입니다. 실제로 두 숫자를 곱하는 효과로 인해 충돌이 증가 0 < n < 1합니다. 결과는 더 작은 부분이되어 스펙트럼의 하단쪽으로 결과에 편향이 발생합니다.
몇 가지 추가 설명. 다음에서 '예측 불가능'과 '무작위'는 이전 숫자를 기반으로 다음 숫자가 무엇인지 추측 할 수있는 능력을 의미합니다. 오라클.
x다음 값 목록을 생성하는 시드 가 주어집니다 .
0.3, 0.6, 0.2, 0.4, 0.8, 0.1, 0.7, 0.3, ...
rand()위 목록 rand() * rand()을 생성 하고 다음 을 생성합니다.
0.18, 0.08, 0.08, 0.21, ...
두 방법 모두 동일한 시드에 대해 항상 동일한 숫자 목록을 생성하므로 오라클에서 동일하게 예측할 수 있습니다. 그러나 두 호출을 곱한 결과를 보면 0.3원래 시퀀스의 적절한 분포에도 불구하고 모두 언더라는 것을 알 수 있습니다 . 두 분수를 곱한 효과로 인해 숫자가 편향되어 있습니다. 결과 숫자는 항상 더 작기 때문에 여전히 예측할 수 없지만 충돌이 발생할 가능성이 훨씬 더 높습니다.
요점을 설명하기위한 지나치게 단순화했습니다.
임의의 함수가 0또는 1.
random()은 중 하나 (0,1)이지만 다음 random()*random()중 하나입니다.(0,0,0,1)
0두 번째 경우에 a를 얻을 수있는 기회가 1.
내가 처음이 답변을 게시 할 때 나는 그것을 읽는 사람이 눈에서의 차이 이해 가능성이 너무 짧게 유지하고 싶었 random()와 random()*random(),하지만 난 원래 광고 litteram의 질문에 대답에서 자신을 지킬 수 :
어느 것이 더 무작위입니까?
즉,이기 때문에 random(), random()*random(), random()+random(), (random()+1)/2또는 고정 된 결과를 유도하지 않는 임의의 다른 조합 (의사 난수 발생기의 경우 또는 동일한 초기 상태) 엔트로피 같은 소스를 가지고 응답들이 있다는 것이 동일 (차이 임의 배포 중입니다). 우리가 볼 수있는 완벽한 예는 크랩 스 게임입니다. 당신이 얻는 숫자 random(1,6)+random(1,6)는 7 개를 얻을 가능성이 가장 높다는 것을 우리 모두 알고 있지만, 그렇다고 두 개의 주사위를 굴린 결과가 하나를 굴린 결과보다 다소 무작위 적이라는 것을 의미하지는 않습니다.
여기에 간단한 대답이 있습니다. 독점을 고려하십시오. 두 개의 6면 주사위 (또는 게임 표기법을 선호하는 사람들의 경우 2d6)를 굴리고 그 합계를 가져옵니다. 7 (1,6 2,5 3,4 4,3 5,2 및 6,1)을 굴릴 수있는 6 가지 방법이 있기 때문에 가장 일반적인 결과는 7입니다. 2는 1,1에만 굴릴 수 있습니다. 범위가 같더라도 2d6 롤링이 1d12 롤링과 다르다는 것을 쉽게 알 수 있습니다 (1d12에서 1을 얻을 수 있다는 것을 무시하고 포인트는 동일하게 유지됨). 결과를 추가하는 대신 곱하면 비슷한 방식으로 결과가 왜곡되어 대부분의 결과가 범위의 중간에 표시됩니다. 특이 치를 줄이려는 경우 좋은 방법이지만 균등 한 분포를 만드는 데 도움이되지 않습니다.
(이상하게도 낮은 롤도 증가시킬 것입니다. 임의성이 0에서 시작한다고 가정하면 다른 롤이 0으로 바뀌기 때문에 0에서 스파이크를 볼 수 있습니다. 0과 1 사이의 두 개의 난수를 고려하십시오. ) 및 곱하기. 두 결과 중 하나가 0이면 다른 결과에 관계없이 모든 것이 0이됩니다. 1을 얻는 유일한 방법은 두 롤 모두 1이되는 것입니다. 실제로 이것은 아마도 중요하지 않을 것입니다. 그러나 그것은 이상한 그래프를 만듭니다.)
필수 xkcd ...
더 이산적인 숫자로 생각하는 것이 도움이 될 수 있습니다. 1에서 36 사이의 난수를 생성하고 싶으므로 가장 쉬운 방법은 공정한 6면 주사위 두 개를 던지는 것입니다. 당신은 이것을 얻습니다 :
1 2 3 4 5 6
-----------------------------
1| 1 2 3 4 5 6
2| 2 4 6 8 10 12
3| 3 6 9 12 15 18
4| 4 8 12 16 20 24
5| 5 10 15 20 25 30
6| 6 12 18 24 30 36
그래서 우리는 36 개의 숫자를 가지고 있지만 그들 모두가 공정하게 표현되는 것은 아니며 일부는 전혀 발생하지 않습니다. 중앙 대각선 근처 (왼쪽 하단 모서리에서 오른쪽 상단 모서리까지) 근처의 숫자가 가장 높은 주파수로 나타납니다.
주사위 사이의 불공정 한 분배를 설명하는 동일한 원칙이 0.0에서 1.0 사이의 부동 소수점 숫자에도 동일하게 적용됩니다.
"무작위성"에 대한 몇 가지 사항은 반 직관적입니다.
의 균일 분포를 가정하면 rand()다음과 같이 평평하지 않은 분포를 얻을 수 있습니다.
- 높은 편향 :
sqrt(rand(range^2)) - 중간에 바이어스 피크 :
(rand(range) + rand(range))/2 - 낮은 : 편향 :
range - sqrt(rand(range^2))
특정 바이어스 곡선을 만드는 다른 방법이 많이 있습니다. 저는 빠른 테스트를 rand() * rand()했고 매우 비선형적인 분포를 얻었습니다.
대부분의 rand () 구현에는 일정 기간이 있습니다. 즉, 엄청난 수의 호출 후에 시퀀스가 반복됩니다. rand() * rand()반복되는 출력의 순서는 절반의 시간이므로 그런 의미에서 "덜 무작위"입니다.
또한 신중한 구성없이 임의 값에 대해 산술을 수행하면 임의성이 떨어지는 경향이 있습니다. 위에 인용 된 " rand()+ rand()+ rand()..."(예 : k 번)는 실제로 값 범위의 평균 값의 k 배가 rand()반환 되는 경향이 있습니다. (그 평균에 대해 계단이 대칭 인 무작위 걷기입니다.)
rand () 함수가 [0,1) 범위에서 균일하게 분포 된 임의의 실수를 반환한다고 구체적으로 가정합니다. (예,이 예제는 무한한 정밀도를 허용합니다. 이것은 결과를 변경하지 않습니다.) 특정 언어를 선택하지 않았고 다른 언어가 다른 작업을 수행 할 수 있지만 다음 분석은 rand (의 비비 위적 구현에 대한 수정으로 유지됩니다. ). 제품 rand() * rand()도 [0,1) 범위에 있지만 더 이상 균일하게 분포되지 않습니다. 실제로 제품은 구간 [1 / 4,1) 에서처럼 구간 [0,1 / 4)에있을 가능성이 높습니다. 더 많은 곱셈은 결과를 0으로 더 기울입니다. 이것은 결과를 더 예측 가능하게 만듭니다. 넓은 스트로크에서 더 예측 가능 == 덜 무작위.
균일 한 임의 입력에 대한 거의 모든 작업 시퀀스는 균일하지 않은 임의의 순서로되어 예측 가능성이 높아집니다. 조심스럽게이 속성을 극복 할 수 있지만 산술로 시간을 낭비하는 것보다 실제로 원하는 범위에서 균일하게 분포 된 난수를 생성하는 것이 더 쉬웠을 것입니다.
"무작위"대 "더 무작위"는 어느 제로가 더 제로인지 묻는 것과 비슷합니다.
이 경우 rand는 PRNG이므로 완전히 무작위가 아닙니다. (사실, 종자가 알려진 경우 매우 예측 가능합니다). 다른 값을 곱하면 더 많거나 적은 무작위가 아닙니다.
진정한 암호화 유형 RNG는 실제로 무작위입니다. 그리고 어떤 종류의 함수를 통해 값을 실행하면 더 많은 엔트로피를 추가 할 수 없으며 엔트로피를 제거하여 더 이상 무작위로 만들 수 없습니다.
당신이 찾고있는 개념은 일련의 비트의 무질서의 "정도"인 "엔트로피"입니다. 이 아이디어는 "최대 엔트로피"개념으로 이해하기 가장 쉽습니다.
최대 엔트로피를 가진 비트 문자열의 대략적인 정의는 더 짧은 비트 문자열로 정확하게 표현할 수 없다는 것입니다 (즉, 작은 문자열을 원래 문자열로 다시 확장하기 위해 일부 알고리즘을 사용함).
임의성에 대한 최대 엔트로피의 관련성은 "무작위로"숫자를 선택하면 거의 확실하게 비트 열이 최대 엔트로피를 갖는 숫자, 즉 압축 할 수없는 숫자를 선택한다는 사실에서 비롯됩니다. 이것이 "무작위"숫자의 특징을 가장 잘 이해 한 것입니다.
따라서 두 개의 무작위 샘플에서 무작위로 "두 배"인 임의의 숫자를 만들고 싶다면 두 비트 문자열을 함께 연결 합니다. 실제로는 샘플을 이중 길이 단어의 높고 낮은 절반에 채울 것입니다.
좀 더 실용적인 메모에서, 당신이 엉뚱한 rand ()에 안장되어 있다면 때로는 두 개의 샘플을 함께 xor하는 데 도움이 될 수 있습니다 .- 비록 그것이 진정으로 깨진 경우에도 그 절차가 도움이되지는 않습니다.
받아 들여지는 대답은 꽤 멋지지만 질문에 대답하는 다른 방법이 있습니다. PachydermPuncher의 답변은 이미 이러한 대안 접근 방식을 취하고 있으며 조금 확장하려고합니다.
정보 이론에 대해 생각하는 가장 쉬운 방법은 정보의 가장 작은 단위 인 단일 비트에 관한 것입니다.
C 표준 라이브러리 에서 플랫폼에 따라 다르게 정의 될 수있는 한계 인 rand()0 ~ 범위의 정수를 반환합니다 RAND_MAX. 정수가 어디에있는 RAND_MAX것으로 정의 되었다고 가정 해 봅시다 (이는 Microsoft 구현의 경우, 여기서 15입니다). 그런 다음 좋은 구현이 약간의 정보를 반환한다고 말할 수 있습니다.2^n - 1nnn
rand()동전을 뒤집어 1 비트의 값을 찾은 다음 15 비트의 배치가 될 때까지 반복하여 난수 를 구성 한다고 상상해보십시오 . 그런 다음 비트는 독립적입니다 (한 비트의 값은 동일한 배치의 다른 비트가 특정 값을 가질 가능성에 영향을주지 않음). 따라서 독립적으로 간주되는 각 비트는 0과 1 사이의 임의의 숫자와 같으며 해당 범위에 걸쳐 "균등하게 분산"됩니다 (0이 1이 될 가능성이 있음).
비트의 독립성은 비트 배치로 표현되는 숫자가 해당 범위에 균등하게 분산되도록합니다. 이것은 직관적으로 분명합니다. 15 비트가있는 경우 허용되는 범위는 0에서 2^15 - 1= 32767입니다. 해당 범위의 모든 숫자는 다음과 같이 고유 한 비트 패턴입니다.
010110101110010
비트가 독립적이면 다른 패턴보다 패턴이 발생할 가능성이 더 큽니다. 따라서 범위의 모든 가능한 숫자는 똑같이 가능합니다. 따라서 그 반대는 사실입니다. rand()균등하게 분산 된 정수를 생성하면 해당 숫자는 독립적 인 비트로 구성됩니다.
따라서 rand()비트를 만들기위한 생산 라인으로 생각하십시오. 비트를 임의의 크기로 배치하여 제공합니다. 크기가 마음에 들지 않으면 배치를 개별 비트로 나눈 다음 원하는 수량으로 다시 합칩니다 (2의 거듭 제곱이 아닌 특정 범위가 필요한 경우에는 숫자를 줄여야합니다. , 그리고 가장 쉬운 방법은 부동 소수점으로 변환하는 것입니다).
원래 제안으로 돌아가서 15 개 배치에서 30 개 배치로 이동 rand()하고 첫 번째 숫자를 요청 하고 15 자리 비트 시프트 한 다음 다른 숫자를 추가 rand()한다고 가정합니다. 이는 rand()균등 분배를 방해하지 않고 두 통화를 결합하는 방법 입니다. 정보의 일부를 배치하는 위치간에 겹침이 없기 때문에 간단하게 작동합니다.
이것은 rand()상수를 곱하여 범위를 "확장"하는 것과는 매우 다릅니다 . 예를 들어, 범위를 두 배로 늘리고 싶다면 rand()2를 곱할 수 있습니다.하지만 이제는 짝수 만 얻을 수 있고 홀수는 얻을 수 없습니다! 그것은 정확하게 매끄럽게 분배되지 않으며, 예를 들어 홀수 / 짝수 베팅을 허용하는 룰렛과 같은 게임과 같이 응용 프로그램에 따라 심각한 문제가 될 수 있습니다. (비트로 생각하면 실수를 직관적으로 피할 수 있습니다 .2를 곱하는 것은 비트를 왼쪽 (더 큰 의미)으로 한 자리 이동하고 간격을 0으로 채우는 것과 동일하다는 것을 알기 때문입니다. 따라서 정보의 양은 동일합니다. 조금만 움직였습니다.)
부동 소수점 범위는 본질적으로 전혀 표현할 수없는 간격을 가지고 있기 때문에 숫자 범위의 이러한 간격은 부동 소수점 숫자 응용 프로그램에서 파악할 수 없습니다. 각각의 표현 가능한 부동 소수점 사이의 간격 에는 무한한 수의 누락 된 실수가 존재합니다. 포인트 번호! 그래서 우리는 어쨌든 간격을두고 사는 법을 배워야합니다.
다른 사람들이 경고했듯이,이 분야에서 직관은 위험합니다. 특히 수학자들은 엄청나게 무한하고 명백한 역설로 가득 찬 끔찍하게 혼란스러운 실수의 매력에 저항 할 수 없기 때문입니다.
그러나 적어도 비트라는 용어로 생각하면 직감이 조금 더 나아갈 수 있습니다. 비트는 정말 쉽습니다 . 컴퓨터 도 이해할 수 있습니다.
다른 사람들이 말했듯이 쉬운 짧은 대답은 : 아니오, 더 무작위 적이지는 않지만 분포를 변경합니다.
주사위 게임을한다고 가정 해 보겠습니다. 당신은 완전히 공정하고 무작위적인 주사위를 가지고 있습니다. 각 주사위를 굴리기 전에 먼저 두 개의 주사위를 그릇에 넣고 흔들고 무작위로 주사위 중 하나를 고른 다음 그 주사위를 굴리면 주사위 굴림이 "더 무작위 적"일까요? 분명히 그것은 아무런 차이가 없을 것입니다. 두 주사위가 모두 난수를 주면 두 주사위 중 하나를 무작위로 선택해도 차이가 없습니다. 어느 쪽이든 충분한 수의 롤에 걸쳐 균등하게 분포 된 1에서 6 사이의 임의의 숫자를 얻을 수 있습니다.
실생활에서 주사위가 공정하지 않다고 생각되면 그러한 절차가 유용 할 것이라고 생각합니다. 예를 들어, 주사위가 약간 불균형하여 한 사람이 1/6의 시간보다 1을 더 자주 주거나 다른 주사위가 비정상적으로 자주 6을 주려는 경향이 있다면, 둘 중 무작위로 선택하면 편견이 모호 해지는 경향이 있습니다. (이 경우 1과 6은 여전히 2, 3, 4, 5 이상으로 나옵니다. 음, 불균형의 성격에 따라 추측됩니다.)
무작위성에 대한 많은 정의가 있습니다. 랜덤 시리즈의 한 가지 정의는 랜덤 프로세스에 의해 생성 된 일련의 숫자라는 것입니다. 이 정의에 따르면 공정한 주사위를 5 번 굴려서 2, 4, 3, 2, 5라는 숫자를 얻는다면 그것은 무작위 시리즈입니다. 그런 다음 동일한 공정한 주사위를 5 번 더 굴리고 1, 1, 1, 1, 1을 얻는다면 그것은 또한 무작위 시리즈입니다.
여러 포스터에서는 컴퓨터의 임의 함수가 실제로 무작위가 아니라 의사 무작위이며 알고리즘과 시드를 알고 있으면 완전히 예측할 수 있다고 지적했습니다. 이것은 사실이지만 대부분의 경우 완전히 관련이 없습니다. 카드 한 벌을 섞은 다음 한 번에 하나씩 뒤집 으면 무작위 시리즈가됩니다. 누군가 카드를 들여다 보면 결과는 완전히 예측 가능하지만 대부분의 무작위성 정의에 따라 무작위성이 떨어지는 것은 아닙니다. 시리즈가 무작위성에 대한 통계 테스트를 통과하면 카드를 들여다 본 사실이 그 사실을 바꾸지 않습니다. 실제로 다음 카드를 추측 할 수있는 능력에 대해 많은 돈을 도박하는 경우 카드를 들여다 보았다는 사실은 매우 관련이 있습니다. 시스템 성능을 테스트하기 위해 웹 사이트 방문자의 메뉴 선택을 시뮬레이션하기 위해 시리즈를 사용하는 경우, 엿본 사실은 전혀 차이가 없습니다. (이 지식을 활용하기 위해 프로그램을 수정하지 않는 한)
편집하다
Monty Hall 문제에 대한 답변을 댓글로 작성할 수 없다고 생각하므로 답변을 업데이트하겠습니다.
벨리 사리우스 링크를 읽지 않은 사람들을 위해 그것의 요지는 : 게임 쇼 참가자는 3 개의 문을 선택할 수 있습니다. 하나 뒤에는 가치있는 상이 있고, 다른 뒤에는 쓸모없는 것입니다. 그는 1 번 문을 선택합니다. 승자인지 패자인지를 밝히기 전에 호스트는 문 # 3을 열어 패자임을 밝힙니다. 그런 다음 참가자에게 2 번 문으로 전환 할 수있는 기회를 제공합니다. 참가자가 이것을해야합니까?
많은 사람들의 직관을 상하게하는 대답은 그가 전환해야한다는 것입니다. 그의 원래 선택이 승자가 될 확률은 1/3이고 다른 문이 승자가 될 확률은 2/3입니다. 다른 많은 사람들과 함께 저의 초기 직관은 전환시 이득이없고 배당률이 50:50으로 변경되었다는 것입니다.
결국, 호스트가 잃어버린 문을 연 직후에 누군가 TV를 켰다 고 가정 해보십시오. 그 사람은 두 개의 닫힌 문이 남아있는 것을 보게 될 것입니다. 그가 게임의 성격을 안다고 가정하면, 그는 각 문이 상품을 숨길 확률이 1/2이라고 말할 것입니다. 시청자의 확률은 1/2 : 1/2이고 참가자의 확률은 1/3 : 2/3 일 수 있습니까?
제 직감을 이겨내려면 정말 생각해야 했어요. 이에 대한 이해를 돕기 위해 이와 같은 문제의 확률에 대해 이야기 할 때 사용 가능한 정보에 대해 할당 할 확률을 의미합니다. 경품을 넣은 승무원, 예를 들어, 문 # 1에 경품이 문 # 1 뒤에있을 확률은 100 %이고 다른 두 문 중 하나 뒤에있을 확률은 0입니다.
승무원의 배당률은 참가자가 모르는 것을 알고 있기 때문에 참가자의 배당률과 다릅니다. 마찬가지로 참가자의 확률은 시청자가 모르는 것, 즉 그가 처음에 선택한 문을 알고 있기 때문에 시청자의 확률과 다릅니다. 호스트가 어느 문을 열지 선택하는 것이 무작위가 아니기 때문에 이것은 관련이 없습니다. 그는 참가자가 선택한 문을 열지 않을 것이며 상금을 숨기는 문을 열지 않을 것입니다. 이것이 같은 문이라면 두 가지 선택이 남습니다. 문이 다르면 하나만 남습니다.
So how do we come up with 1/3 and 2/3 ? When the contestant originally picked a door, he had a 1/3 chance of picking the winner. I think that much is obvious. That means there was a 2/3 chance that one of the other doors is the winner. If the host game him the opportunity to switch without giving any additional information, there would be no gain. Again, this should be obvious. But one way to look at it is to say that there is a 2/3 chance that he would win by switching. But he has 2 alternatives. So each one has only 2/3 divided by 2 = 1/3 chance of being the winner, which is no better than his original pick. Of course we already knew the final result, this just calculates it a different way.
그러나 이제 진행자는이 두 가지 선택 중 하나가 승자가 아니라는 것을 밝힙니다. 그래서 그가 선택하지 않은 문이 승자가 될 확률이 2/3이므로 이제 그는 두 가지 대안 중 하나가 그렇지 않다는 것을 알고 있습니다. 다른 하나는 그렇지 않을 수도 있습니다. 그래서 그는 더 이상 2/3를 2로 나누지 않습니다. 그는 열린 문에 대해 0을 갖고 닫힌 문에 대해 2/3를 가지고 있습니다.
짝수는 앞면으로, 홀수는 뒷면으로 간주되는 간단한 동전 던지기 문제가 있다고 가정합니다. 논리적 구현은 다음과 같습니다.
rand() mod 2
충분히 큰 분포에서 짝수 수는 홀수 수와 같아야합니다.
이제 약간의 조정을 고려하십시오.
rand() * rand() mod 2
결과 중 하나가 짝수이면 전체 결과가 균등해야합니다. 4 가지 가능한 결과 (짝수 * 짝수 = 짝수, 짝수 * 홀수 = 짝수, 홀수 * 짝수 = 짝수, 홀수 * 홀수 = 홀수)를 고려하십시오. 이제 충분히 큰 분포에서 답은 시간의 75 %가되어야합니다.
내가 당신이라면 앞면이 될 것입니다.
이 설명은 무작위성의 수학적 속성에 대한 논의보다 방법을 기반으로 사용자 지정 무작위 함수를 구현하지 않아야하는 이유에 대한 설명입니다.
난수 조합이 어떻게 될지 의심 스러울 때 통계 이론에서 배운 교훈을 사용할 수 있습니다.
OP의 상황에서 그는 X * X = X ^ 2의 결과가 무엇인지 알고 싶어합니다. 여기서 X는 Uniform [0,1]을 따라 분포 된 랜덤 변수입니다. 우리는 일대일 매핑이기 때문에 CDF 기술을 사용할 것입니다.
X ~ Uniform [0,1]이므로 cdf는 다음과 같습니다. f X (x) = 1 우리는 변환을 원합니다 Y <-X ^ 2 따라서 y = x ^ 2 역수를 구합니다 x (y) : sqrt (y) = x 이것은 우리에게 y의 함수로 x를줍니다. 다음으로 미분 dx / dy를 구합니다 : d / dy (sqrt (y)) = 1 / (2 sqrt (y))
Y의 분포는 다음과 같이 주어집니다. f Y (y) = f X (x (y)) | dx / dy | = 1 / (2 sqrt (y))
아직 끝나지 않았습니다. Y의 영역을 구해야합니다. 0 <= x <1, 0 <= x ^ 2 <1이므로 Y는 [0, 1) 범위에 있습니다. Y의 pdf가 실제로 pdf인지 확인하려면 도메인을 통해 통합하십시오. Integrate 1 / (2 sqrt (y)) from 0 to 1 and true, it pop up as 1 이 기능은 게시 된 belisarious처럼 보입니다.
X 1 + X 2 + ... + X n , (여기서 X i ~ Uniform [0,1]) 우리는 모멘트가 존재하는 모든 분포에 적용되는 Central Limit Theorem에 호소 할 수 있습니다. 이것이 Z- 검정이 실제로 존재하는 이유입니다.
결과 pdf를 결정하는 다른 기술에는 Jacobian 변환 (cdf 기술의 일반화 된 버전) 및 MGF 기술이 포함됩니다.
편집 : 설명 으로 무작위성이 아닌 결과 변환 의 분포 에 대해 이야기하고 있음을 유의하십시오 . 그것은 실제로 별도의 논의를위한 것입니다. 또한 내가 실제로 파생 한 것은 (rand ()) ^ 2입니다. rand () * rand ()의 경우 훨씬 더 복잡하며, 어떤 경우에도 어떤 종류의 균일 한 분포도 생성하지 않습니다.
정확히 명확하지는 않지만 rand()일반적으로 rand()*rand(). 중요한 것은 이것이 대부분의 용도에서 실제로 그다지 중요하지 않다는 것입니다.
그러나 첫째, 그들은 다른 분포를 생성합니다. 그것이 당신이 원하는 것이라면 이것은 문제가 아니지만 중요합니다. 특정 분포가 필요하면 "더 무작위적인"질문 전체를 무시하십시오. 그렇다면 왜 rand()더 무작위입니까?
이유의 핵심 rand()더 임의적입니다 ([0..1] 범위의 부동 소수점 난수를 생성한다는 가정하에, 이것은 매우 일반적입니다) 가수의 많은 정보와 함께 두 개의 FP 숫자를 곱하면 결국 일부 정보 손실; IEEE 배정 밀도 부동 소수점에는 [0..1]에서 균일하게 무작위로 선택된 두 개의 IEEE 배정 밀도 부동 소수점에 있던 모든 정보를 담을 수있는 비트가 충분하지 않으며 이러한 추가 정보 비트는 손실됩니다. 물론, 당신이 (아마) 그 정보를 사용하지 않을 것이기 때문에 그다지 중요하지 않지만 손실은 실제입니다. 또한 생산하는 배포판 (즉, 조합을 수행하는 데 사용하는 작업)은 실제로 중요하지 않습니다. 각 난수에는 52 비트의 임의 정보가 있습니다.
대부분의 난수 사용은 무작위 소스에서 실제로 사용할 수있는만큼의 임의성을 사용하지 않습니다. 좋은 PRNG를 얻고 그것에 대해 너무 걱정하지 마십시오. (“선도”의 수준은 수행중인 작업에 따라 달라집니다. Monte Carlo 시뮬레이션 또는 암호화를 수행 할 때주의해야하지만 그렇지 않으면 일반적으로 훨씬 더 빠르기 때문에 표준 PRNG를 사용할 수 있습니다.)
부동 난수는 일반적으로 0과 특정 범위 사이의 정수를 생성하는 알고리즘을 기반으로합니다. 따라서 rand () * rand ()를 사용하면 본질적으로 int_rand () * int_rand () / rand_max ^ 2-즉 소수 / rand_max ^ 2를 제외한다는 의미입니다.
이는 무작위 분포를 크게 변경합니다.
rand ()는 대부분의 시스템에서 균일하게 배포되며 제대로 시드되었는지 예측하기 어렵습니다. 수학을 할 특별한 이유가없는 한 사용하십시오 (예 : 필요한 곡선에 대한 분포 형성).
숫자를 곱하면 컴퓨터 아키텍처에 따라 더 작은 솔루션 범위가됩니다.
컴퓨터 화면에 16 자리 숫자 rand()가 표시되면 0.1234567890123에 1 초를 곱한 rand()값인 0.1234567890123은 0.0152415를 제공합니다. 실험을 10 ^ 14 번 반복하면 확실히 더 적은 솔루션을 찾을 수 있습니다.
이러한 분포의 대부분은 난수를 제한하거나 정규화해야하기 때문에 발생합니다.
우리는 그것을 모두 양수로 정규화하고, 범위에 맞으며, 할당 된 변수 유형에 대한 메모리 크기의 제약에 맞도록 정규화합니다.
즉, 0과 X 사이의 임의 호출을 제한해야하므로 (X는 변수의 크기 제한) 0과 X 사이의 "무작위"숫자 그룹을 갖게됩니다.
이제 난수를 다른 난수에 더하면 합계는 0과 2X 사이의 어딘가에있을 것입니다. 이것은 값을 가장자리 지점에서 멀어지게합니다 (두 개의 작은 수를 함께 추가하고 두 개의 큰 수를 함께 추가 할 확률은 다음과 같은 경우 매우 작습니다. 큰 범위에 걸쳐 두 개의 난수가 있습니다).
0에 가까운 숫자가 있고 다른 임의의 숫자와 함께 추가하면 확실히 더 커지고 0에서 멀어 질 것입니다 (이는 큰 숫자에 해당 할뿐만 아니라 두 개의 큰 숫자가있을 가능성이 낮습니다). (X에 가까운 숫자) Random 함수에서 두 번 반환합니다.
이제 음수와 양수 (0 축을 가로 질러 균등하게 확장 됨)를 사용하여 임의 방법을 설정했다면 더 이상 그렇지 않습니다.
예를 들어 RandomReal({-x, x}, 50000, .01)음수와 양의 숫자를 균등하게 분배하고 난수를 더하면 "무작위"를 유지할 수 있습니다.
이제 Random() * Random()음에서 양의 범위로 어떤 일이 벌어 질지 모르겠습니다 . 흥미로운 그래프가 될 것입니다 ...하지만 지금 코드 작성으로 돌아 가야합니다. :-피
더 무작위적인 것은 없습니다 . 무작위이거나 아닙니다. 무작위는 "예측하기 어렵다"는 의미입니다. 비 결정적이라는 의미는 아닙니다. random ()과 random () * random ()은 random ()이 무작위이면 똑같이 무작위입니다. 임의성이 진행되는 한 분포는 관련이 없습니다. 비 균일 분포가 발생하면 일부 값이 다른 값보다 더 높음을 의미합니다. 그들은 여전히 예측할 수 없습니다.
의사 랜덤 성이 관련되어 있기 때문에 숫자는 매우 결정적입니다. 그러나 의사 난 수성은 확률 모델과 시뮬레이션에서 종종 충분합니다. 의사 난수 생성기를 복잡하게 만들면 분석하기가 어렵다는 것은 잘 알려져 있습니다. 임의성을 개선 할 가능성은 거의 없습니다. 종종 통계 테스트에 실패합니다.
원하는 난수 속성은 중요합니다. 반복성 및 재현성, 통계적 임의성, (일반적으로) 균일하게 분포 된 값 및 큰 기간이 몇 개 있습니다.
난수 변환 관련 : 누군가 말했듯이 두 개 이상의 균일하게 분포 된 합은 정규 분포를 생성합니다. 이것이 덧셈 중심 극한 정리입니다. 모든 배포가 독립적이고 동일하다면 소스 배포에 관계없이 적용됩니다. 곱셈중심 한계 정리는 두 개 이상의 독립적이고 들여 쓰기로 분포 된 랜덤 변수의 곱이 로그 정규 분포라고 말합니다. 다른 사람이 만든 그래프는 기하 급수적으로 보이지만 실제로는 로그 정규입니다. 따라서 random () * random ()은 로그 정규 분포를 따릅니다 (숫자가 동일한 스트림에서 가져 오기 때문에 독립적이지 않을 수 있음). 이것은 일부 응용 프로그램에서 바람직 할 수 있습니다. 그러나 일반적으로 하나의 난수를 생성하고이를 로그 정규 분포 숫자로 변환하는 것이 좋습니다. Random () * random ()은 분석하기 어려울 수 있습니다.
자세한 내용은 www.performorama.org에서 저의 책을 참조하십시오. 이 책은 건설 중이지만 관련 자료가 있습니다. 장과 섹션 번호는 시간이 지남에 따라 변경 될 수 있습니다. 8 장 (확률 이론)-섹션 8.3.1 및 8.3.3, 10 장 (난수).
Kolmogorov 복잡성 을 사용하여 임의성에 관한 두 배열의 숫자를 비교할 수 있습니다. 숫자 시퀀스를 압축 할 수없는 경우이 길이에서 도달 할 수있는 가장 임의의 것입니다.이 유형의 측정이 더 이론적이라는 것을 알고 있습니다. 선택권...
그것에 대해 사실, 때 생각 rand() * rand()입니다 적은 보다는 무작위 rand(). 그 이유는 다음과 같습니다.
기본적으로 짝수와 동일한 수의 홀수가 있습니다. 0.04325는 홀수, 0.388은 짝수, 0.4는 짝수, 0.15는 홀수라고 말하면
그 수단 rand()갖는 짝수 또는 홀수 소수되는 동일한 기회 .
반면에 rand() * rand()배당률이 약간 다르게 쌓여 있습니까? 의 말을하자:
double a = rand();
double b = rand();
double c = a * b;
a그리고 b모두가 짝수 또는 홀수 인의 50 % 퍼센트 인의 기회가있다. 그것을 아는 것은
- 짝수 * 짝수 = 짝수
- 짝수 * 홀수 = 짝수
- 홀수 * 홀수 = 홀수
- 홀수 * 짝수 = 짝수
즉, 거기에 75 %의 확률c 만을하면서 짝수 25 %의 확률로 이 값 만드는 이상한 rand() * rand()이상의 예측이 rand()때문에 적은 랜덤.
기본 다항식을 구현하는 선형 피드백 시프트 레지스터 (LFSR)를 사용합니다.
결과는 2 ^ n 개의 의사 난수 시퀀스가됩니다. 즉, n이 LFSR의 비트 수인 시퀀스에서 반복되지 않아 균일 한 분포가 생성됩니다.
http://en.wikipedia.org/wiki/Linear_feedback_shift_register http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf
컴퓨터 클럭의 마이크로 초를 기반으로 "무작위"시드를 사용하거나 파일 시스템에서 지속적으로 변경되는 데이터에 대한 md5 결과의 하위 집합을 사용합니다.
예를 들어, 32 비트 LFSR은 주어진 시드로 시작하여 순서대로 2 ^ 32 개의 고유 번호를 생성합니다. 순서는 항상 동일한 순서이지만 시작점은 다른 시드에 대해 (분명히) 달라집니다. 따라서 씨 뿌리기 사이에 반복되는 순서가 문제가되지 않는다면 이것은 좋은 선택 일 수 있습니다.
지속적으로 변경되는 시스템 데이터에 대한 md5 결과 인 시드를 사용하여 하드웨어 시뮬레이터에서 무작위 테스트를 생성하기 위해 128 비트 LFSR을 사용했습니다.
라고 가정 rand()사이 수 복귀 [0, 1)가 분명 rand() * rand()승산 때문이다 0 치우쳐 것 x사이의 숫자로하는 [0, 1)보다 작은 수를 초래할 것이다 x. 다음은 10000 개 이상의 난수 분포입니다 .
google.charts.load("current", { packages: ["corechart"] });
google.charts.setOnLoadCallback(drawChart);
function drawChart() {
var i;
var randomNumbers = [];
for (i = 0; i < 10000; i++) {
randomNumbers.push(Math.random() * Math.random());
}
var chart = new google.visualization.Histogram(document.getElementById("chart-1"));
var data = new google.visualization.DataTable();
data.addColumn("number", "Value");
randomNumbers.forEach(function(randomNumber) {
data.addRow([randomNumber]);
});
chart.draw(data, {
title: randomNumbers.length + " rand() * rand() values between [0, 1)",
legend: { position: "none" }
});
}<script src="https://www.gstatic.com/charts/loader.js"></script>
<div id="chart-1" style="height: 500px">Generating chart...</div>경우 rand()반환의 정수는 [x, y]다음 다음과 같은 분포를 가지고있다. 홀수 대 짝수 값의 수를 확인하십시오.
google.charts.load("current", { packages: ["corechart"] });
google.charts.setOnLoadCallback(drawChart);
document.querySelector("#draw-chart").addEventListener("click", drawChart);
function randomInt(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
}
function drawChart() {
var min = Number(document.querySelector("#rand-min").value);
var max = Number(document.querySelector("#rand-max").value);
if (min >= max) {
return;
}
var i;
var randomNumbers = [];
for (i = 0; i < 10000; i++) {
randomNumbers.push(randomInt(min, max) * randomInt(min, max));
}
var chart = new google.visualization.Histogram(document.getElementById("chart-1"));
var data = new google.visualization.DataTable();
data.addColumn("number", "Value");
randomNumbers.forEach(function(randomNumber) {
data.addRow([randomNumber]);
});
chart.draw(data, {
title: randomNumbers.length + " rand() * rand() values between [" + min + ", " + max + "]",
legend: { position: "none" },
histogram: { bucketSize: 1 }
});
}<script src="https://www.gstatic.com/charts/loader.js"></script>
<input type="number" id="rand-min" value="0" min="0" max="10">
<input type="number" id="rand-max" value="9" min="0" max="10">
<input type="button" id="draw-chart" value="Apply">
<div id="chart-1" style="height: 500px">Generating chart...</div>좋아, 그래서 나는 당신이 난수 생성기를 만들고 사용하고 있다고 말함으로써 다른 대답을 보완하기 위해 어떤 가치를 추가하려고 노력할 것입니다.
난수 생성기는 목적에 맞게 수정할 수있는 여러 특성을 가진 장치 (매우 일반적인 의미에서)입니다. 그들 중 일부는 다음과 같습니다.
- 엔트로피 : Shannon Entropy에서와 같이
- 분포 : 통계적 분포 (포아송, 정규 등)
- 유형 : 숫자 (알고리즘, 자연 사건, 조합 등) 및 적용된 알고리즘의 출처는 무엇입니까?
- 효율성 : 실행의 속도 또는 복잡성.
- 패턴 : 주기성, 시퀀스, 실행 등
- 그리고 아마 더 ...
여기에있는 대부분의 답변에서 분포는 주요 관심 지점이지만 함수와 매개 변수를 혼합하여 일치 시키면 평가가 언뜻보기에 명확하지 않을 수있는 다른 특성을 갖는 난수를 생성하는 새로운 방법을 만들 수 있습니다.
두 난수의 합이 반드시 무작위가 아니라는 것을 쉽게 보여줄 수 있습니다. 6면 주사위와 굴림이 있다고 상상해보십시오. 각 숫자는 1/6의 확률로 나타납니다. 이제 주사위 2 개를 가지고 결과를 합산했다고 가정 해 보겠습니다. 이 합계의 분포는 1/12가 아닙니다. 왜? 특정 숫자가 다른 숫자보다 더 많이 나타나기 때문입니다. 여러 파티션 이 있습니다. 예를 들어 숫자 2는 1 + 1의 합계이지만 7은 3 + 4 또는 4 + 3 또는 5 + 2 등으로 구성 될 수 있으므로 올 확률이 더 높습니다.
따라서 변환 (이 경우 임의 함수에 추가)을 적용해도 더 무작위로 만들거나 반드시 임의성을 보존하지는 않습니다. 위의 주사위의 경우 분포가 7로 치우쳐 져서 덜 무작위 적입니다.
다른 사람들이 이미 지적했듯이, 우리 모두는 그의 머릿속에 자신 의 무작위성 에 대한 그림을 가지고 있기 때문에이 질문에 답하기가 어렵습니다 .
그렇기 때문에 무작위성에 대한 더 나은 아이디어를 얻으려면 시간을내어이 사이트를 읽어 보는 것이 좋습니다.
진짜 질문으로 돌아가려면. 이 용어에는 더 많거나 적은 무작위가 없습니다.
둘 다 무작위로 나타납니다 !
두 경우 모두-just rand () 또는 rand () * rand ()-상황은 동일합니다. 수십억 개의 숫자가 지나면 시퀀스 가 반복됩니다 (!) . 이 나타납니다 그가 전체 순서를 모르기 때문에, 관찰자에 무작위로하지만, 컴퓨터가없는 진정한 임의의 소스를 - 그 중 하나 임의성을 생산하지 수 있습니다.
예 : 날씨가 무작위인가요? 날씨가 무작위인지 아닌지를 판단 할 수있는 센서 나 지식이 충분하지 않습니다.
대답은 상황에 따라 다를 수 있습니다. rand () * rand ()가 rand ()보다 더 무작위 적이지만 다음과 같습니다.
- 두 답변 모두 값의 비트 크기에 따라 다릅니다.
- 대부분의 경우 의사 랜덤 알고리즘 (대부분 컴퓨터 클럭에 의존하는 숫자 생성기이며 그다지 랜덤하지 않음)에 따라 생성합니다.
- 코드를 더 읽기 쉽게 만드세요 (그리고 이런 종류의 주문으로 무작위 부두 신을 호출하지 마세요).
위의 항목 중 하나를 확인하면 간단한 "rand ()"를 사용하는 것이 좋습니다. 당신의 코드는 더 읽기 쉬울 것이기 때문에 (당신 이 이것을 왜 작성했는지 스스로 묻지 않을 것입니다, ... 음 ... 2 초 이상), 유지하기 쉽습니다 (당신이 rand 함수를 super_rand로 바꾸고 싶다면).
더 나은 랜덤을 원한다면 충분한 노이즈 ( 라디오 정적 ) 를 제공하는 소스에서 스트리밍하는 것이 좋습니다. 그러면 간단한 rand()것으로 충분합니다.
참고 URL : https://stackoverflow.com/questions/3956478/understanding-randomness
'Nice programing' 카테고리의 다른 글
| 오류-IIS 메타베이스에 액세스 할 수 없습니다. (0) | 2020.09.28 |
|---|---|
| setup.py는 무엇입니까? (0) | 2020.09.28 |
| AngularJS : $ scope. $ apply () 호출시 이미 진행중인 $ digest 오류 방지 (0) | 2020.09.28 |
| 줄거리에서 범례를 제거하는 방법 (0) | 2020.09.28 |
| 알고리즘의 시간 복잡성을 찾는 방법 (0) | 2020.09.28 |