(0, 255)에서 8 개의 랜덤 비트를 균일하게 생성하는 이유는 무엇입니까? 함께 연결하여

8 개의 임의 비트 (0 또는 1)를 생성하고 함께 연결하여 8 비트 숫자를 형성합니다. 간단한 파이썬 시뮬레이션은 불연속 세트 [0, 255]에 균일 한 분포를 산출합니다.

왜 이것이 내 머리에 의미가 있는지 정당화하려고합니다. 이것을 8 코인을 뒤집는 것과 비교하면 예상 값이 4 머리 / 4 꼬리 근처에 있지 않습니까? 따라서 제 결과는 범위의 중간에 급등을 반영해야한다는 것이 합리적입니다. 다시 말해, 8 개의 0 또는 8의 시퀀스가 4 및 4 또는 5 및 3의 시퀀스와 같은 가능성이있는 이유는 무엇입니까? 내가 여기서 무엇을 놓치고 있습니까?

답변

TL; DR :
비트와 코인의 뚜렷한 대조는 코인의 경우 결과 의 순서 를 무시 한다는 것입니다. HHHHTTTT는 TTTTHHHH와 동일하게 취급됩니다 (둘 다 4 개의 머리와 4 개의 꼬리가 있습니다). 그러나 비트 단위에서는 순서에 신경을 씁니다 (256 개의 결과를 얻으려면 비트 위치에 “가중치”를 제공해야 함). 11110000은 00001111과 다릅니다.

더 긴 설명 :
문제를 좀 더 정식화 할 때 이러한 개념을보다 정확하게 통일 할 수 있습니다. 실험은 이분법적인 결과와 “성공”0.5 및 “실패”0.5의 확률을 갖는 8 번의 시험의 연속으로 간주되며 시험은 독립적입니다. 일반적으로이 성공, 총 시행 횟수 및 실패라고하며 성공 확률은 입니다. $k$

$n$

$n - k$

n−k

$p$

코인 예제에서 결과 ” heads, tails”는 시행 순서를 무시합니다 (4 개의 헤드는 발생 순서에 상관없이 4 개의 헤드 임). 그러면 4 개의 헤드가 0보다 높을 가능성이 높습니다. 8 헤드. 4 개의 헤드는 다른 수보다 4 개의 헤드 (TTHHTTHH 또는 HHTTHHTT 등)를 만드는 방법이 많기 때문에 더 일반적입니다 (8 개의 헤드에는 하나의 시퀀스 만 있음). 이항 정리는 이러한 다양한 구성을 수행하는 여러 가지 방법을 제공합니다. $k$
k
$n - k$
n−k
대조적으로, 각 장소는 관련된 “무게”또는 “장소 값”을 가지므로 순서는 비트에 중요합니다. 이항 계수의 한 가지 특성은 . 즉, 다른 순서가 지정된 모든 시퀀스를 세면 됩니다. 이것은 이항 실험 에서 헤드 를 얼마나 많은 다른 방법 으로 다른 바이트 시퀀스의 수로 연결하는지에 대한 아이디어를 직접 연결합니다 . $2^{n} = \sum_{k = 0}^{n} (\binom{n}{k})$
2n=∑k=0n(nk)
$2^{8} = 256$
28=256
$k$
k
$n$
n
또한 독립성에 의해 256 개의 결과가 동등하게 나타날 수 있음을 보여줄 수 있습니다. 이전 시험은 다음 시험에 영향을 미치지 않으므로 특정 주문의 확률은 일반적으로 (독립 사건의 공동 확률은 확률의 곱이므로). 시험은 공정하기 때문에 표현식은 . 모든 순서는 동일한 확률을 갖기 때문에, 우리는이 결과에 대해 균일 한 분포를 갖습니다 (이진 인코딩에 의해 에서 정수로 표현 될 수 있음 ). $p^{k} (1 - p)^{n - k}$
pk(1−p)n−k
$P (success) = P (fail) = p = 0.5$
P(success)=P(fail)=p=0.5
$P (any ordering) = {0.5}^{8} = \frac{1}{256}$
P(any ordering)=0.58=1256
$[0, 255]$
[0,255]
마지막으로이 전체 원을 다시 동전 던지기와 이항 분포로 되돌릴 수 있습니다. 우리는 0 헤드의 발생이 4 헤드와 같은 확률을 갖지 않는다는 것을 알고 있으며, 이는 4 헤드의 발생을 주문하는 방법이 다르기 때문에 이러한 순서의 수는 이항 정리에 의해 주어진다는 것입니다. 따라서 가중치를 부여해야합니다. 특히 이항 계수로 가중치를 부여해야합니다. 따라서 이항 분포의 PMF, 됩니다. 이 표현이 PMF라는 것은 놀라운 일이 될 수 있습니다. 특히 그것이 1의 합이라는 것을 즉시 알 수 없기 때문입니다. 확인하려면 $P (4 heads)$
P(4 heads)
$P (k successes) = (\binom{n}{k}) p^{k} (1 - p)^{n - k}$
P(k successes)=(nk)pk(1−p)n−k
$\sum_{k = 0}^{n} (\binom{n}{k}) p^{k} (1 - p)^{n - k} = 1$
∑k=0n(nk)pk(1−p)n−k=1
그러나 이것은 이항 계수의 문제 일뿐입니다. . $1 = 1^{n} = (p + 1 - p)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) p^{k} (1 - p)^{n - k}$
1=1n=(p+1−p)n=∑k=0n(nk)pk(1−p)n−k

답변

8 개의 0 또는 8의 시퀀스가 4 및 4, 5 및 3의 시퀀스와 똑같이 보이는 이유는 무엇입니까?

모호한 역설은 두 가지 제안으로 요약 될 수 있는데, 이는 모순되는 것처럼 보일 수 있습니다.

시퀀스 (8 개의 0)은 시퀀스 (4 개의 0, 4 개의 1) 과 동일하게 가능 합니다. (일반적으로 시퀀스는 0/1 수에 관계없이 동일한 확률을 갖습니다.) $s_{1} : 00000000$
s1:00000000
$s_{2} : 01010101$
s2:01010101
$2^{8}$
28
” : 시퀀스에 4 개의 0이 있음 ” 이벤트가 ” : 시퀀스에 8 개의 0이 있음 ” 보다 더 가능성이 높습니다 (실제로 배 더 높음) . $e_{1}$
e1
$70$
70
$e_{2}$
e2

이 제안은 모두 사실입니다. 이벤트 많은 시퀀스가 포함되어 있기 때문 입니다. $e_{1}$

답변

모든 시퀀스의 확률은 1 / = 1 / 256입니다. 문제가 해석 될 때 같은 수의 0과 1에 더 가까운 서열이 더 가능성이 높다고 생각하는 것은 잘못입니다 . 시험에서 시험까지 독립성을 가정하기 때문에 1/256에 도달한다는 것이 분명해야합니다 . 이것이 우리 가 확률 을 곱한 이유 이며 한 시험의 결과는 다음 시험에 영향을 미치지 않습니다. $2^{8}$

$2^{8}$

답변

3 비트의 예

자연수 0에서 7까지를 다음과 같이 씁니다.

밑이 10 인 숫자
다수의 베이스 (2) (즉, 비트 시퀀스)
베이스 2 표현에 의해 암시 된 일련의 코인 플립 (1은 헤드 플립을 나타내고 0은 테일 플립을 나타냄).

Base 10 01234567 Base 2 (with 3 bits) 000001010011100101110111 Implied Coin Flip Series T T T T T H T H T T H H H T T H T H H H T H H H Heads 01121223 Tails 32212110

같은 확률로 0에서 7까지의 자연수를 선택하는 것은 오른쪽에서 같은 확률로 동전 뒤집기 시리즈 중 하나를 선택하는 것과 같습니다.

따라서 정수 0-7에 대한 균일 분포에서 숫자를 선택하면 은 3 개의 헤드를 선택할 수 있고 은 2 개의 헤드를 선택할 수있는 1 머리를 선택의 기회와 0 헤드 선택의 기회. $\frac{1}{8}$

$\frac{3}{8}$

$\frac{1}{8}$

답변

Sycorax의 답변은 정확하지만 그 이유를 완전히 알지 못하는 것 같습니다. 8 개의 코인을 뒤집거나 8 개의 랜덤 비트를 생성하면 256 개의 가능성 중 하나가 될 것입니다. 귀하의 경우,이 256 가능한 결과 각각은 고유하게 정수로 매핑되므로 결과로 균일 한 분포를 얻습니다.

머리 또는 꼬리 수를 고려하는 것과 같이 주문을 고려하지 않으면 가능한 결과는 9 개 (0 머리 / 8 꼬리-8 머리 / 0 꼬리)이며 더 이상 동일하지 않습니다. . 256 개의 가능한 결과 중 8 개의 헤드 / 0 테일 (HHHHHHHH)을 제공하는 1 개의 플립 조합과 7 개의 헤드 / 1 테일 (8 개의 위치에 각각의 테일)을 제공하는 8 개의 조합이 있기 때문입니다. 순서), 그러나 8C4 = 4 개의 헤드와 4 개의 테일을 갖는 70 가지 방법. 동전 뒤집기의 경우 70 개의 각 조합은 4 개의 Heads / 4 Tail에 매핑되지만 이진수 문제에서는 70 개의 결과 각각이 고유 한 정수에 매핑됩니다.

답변

문제는 다시 말해서, 8 난수 이진수의 조합 수가 8 난수 이진수의 순열 수와 다른 시간에 0에서 8 선택된 숫자 (예 : 1)로 취해진 이유는 무엇입니까? 본 명세서에서, 0과 1의 무작위 선택은 각 숫자가 서로 독립적이며, 숫자가 상관되지 않고 ; . $p (0) = p (1) = \frac{1}{2}$

p(0)=p(1)=12

대답은 다음과 같습니다. 두 가지 인코딩이 있습니다. 1) 순열의 무손실 인코딩 및 2) 조합의 무손실 인코딩

광고 1) 각 시퀀스가 고유하도록 숫자를 무손실 인코딩하기 위해이 숫자를 이진 정수 . 여기서 는 왼쪽입니다 임의의 0과 1의 이진 시퀀스에서 오른쪽으로 자리. 그러면 임의의 숫자가 위치 인코딩되어 각 순열이 고유 해집니다. 그리고 총 순열 수는 $\sum_{i = 1}^{8} 2^{i - 1} X_{i}$

∑i=182i−1Xi

$X_{i}$

$i^{t h}$

ith

$2^{8} = 256$

28=256

. 그런 다음 우연히도 이진 숫자를 고유성을 잃지 않고 0에서 255까지의 기본 10 숫자로 변환 할 수 있으며, 또는 다른 무손실 인코딩 (예 : 무손실 압축 데이터, Hex, Octal)을 사용하여 해당 숫자를 다시 쓸 수 있습니다. 그러나 질문 자체는 이진입니다. 그런 다음 각 고유 인코딩 시퀀스를 만들 수있는 방법이 하나뿐이기 때문에 각 순열도 똑같이 가능합니다 . 1 또는 0의 모양이 해당 문자열 내에서 동일하게 나타날 가능성 이 있다고 가정 하여 각 순열도 똑같이 가능합니다.

Ad 2) 조합 만 고려하여 무손실 인코딩을 포기하면 결과가 결합되고 정보가 손실되는 손실 인코딩이 있습니다. 우리는 그 다음에 숫자의 시리즈를보고 있습니다. , 이는 8 개의 객체를 합한 횟수 인 으로 감소합니다. 이고, 그 다른 문제에 대해 정확히 4 1의 확률은 8 1을 얻는 것보다 70 ( ) 배 더 큽니다. 4 1을 생성 할 수있는 순열입니다. $\sum_{i = 1}^{8} 2^{0} X_{i}$

∑i=1820Xi

$C (8, \sum_{i = 1}^{8} X_{i})$

C(8,∑i=18Xi)

$\sum_{i = 1}^{8} X_{i}$

∑i=18Xi

$C (8, 4)$

C(8,4)

참고 : 현재로서는 위의 대답은 두 인코딩의 명시 적 계산 비교를 포함하는 유일한 답변이며 인코딩 개념을 언급하는 유일한 답변입니다. 제대로 이해하는 데 시간이 걸렸으므로이 답변은 역사적으로 다운 보트되었습니다. 미해결 불만이 있으면 의견을 남기십시오.

업데이트 : 마지막 업데이트 이후 인코딩 개념이 다른 답변에서 시작된 것에 대해 기쁘게 생각합니다. 현재 문제에 대해 이것을 명시 적으로 보여주기 위해 각 조합에서 손실 인코딩 된 순열 수를 첨부했습니다.

각 조합 인코딩 동안 손실 된 정보의 바이트 수는 그 조합에 대한 순열의 수에서 1을 뺀 것 [ , 여기서 은 1의 수임]과 같습니다. 발 행 의 조합에 따라, 또는 전체. $C (8, n) - 1$

C(8,n)−1

$n$

$0$

$69$

$256 - 9 = 247$

256−9=247

답변

순서 의존성 대 독립성에 대해 조금 확장하고 싶습니다.

8 코인을 뒤집어 예상되는 헤드 수를 계산하는 문제에서 우리는 8 개의 동일한 분포에서 값을 합산합니다. 각 분포는 Bernoulli 분포입니다 [; B(1, 0.5) ;](즉, 50 % 확률은 0, 50 % 확률은 1). 합의 분포는 이항 분포로 [; B(8, 0.5) ;], 확률의 대부분이 4를 중심으로 친숙한 혹 모양을 갖습니다.

8 개의 랜덤 비트로 구성된 바이트의 예상 값을 계산하는 문제에서 각 비트는 바이트에 기여하는 다른 값을 가지므로 8 개의 다른 분포 에서 값을 합산합니다 . 첫 번째는 [; B(1, 0.5) ;], 두 번째는 [; 2 B(1, 0.5) ;], 세 번째는 [; 4 B(1, 0.5) ;], 여덟 번째까지입니다 [; 128 B(1, 0.5) ;]. 이 금액 의 분포 는 첫 번째 금액과는 상당히 다릅니다.

이 후자의 분포가 균일하다는 것을 증명하고 싶다면, 유도 적으로 할 수 있다고 생각합니다. 가장 낮은 비트의 분포는 가정에 의해 1의 범위로 균일하므로 가장 낮은 [; n ;]비트 의 분포가 범위가 균일 한 [; 2^n - 1} ;]경우 [; n+1 ;]st 비트를 추가 하면 범위가 가장 낮은 [; n + 1 ;]비트 의 분포가 균일하게되어 [; 2^{n+1} - 1 ;]모든 양수에 대한 증거를 얻을 수 있습니다.[; n ;]. 그러나 직관적 인 방법은 아마도 정반대 일 것입니다. 높은 비트에서 시작하여 낮은 비트로 한 번에 하나씩 값을 선택하면 각 비트는 가능한 결과의 공간을 정확히 반으로 나누고 각 절반은 동일한 확률로 선택되므로 하단에서 각 개별 값은 동일한 확률을 선택해야합니다.

Exit mobile version

How IT

언제든지 물어보세요.

(0, 255)에서 8 개의 랜덤 비트를 균일하게 생성하는 이유는 무엇입니까? 함께 연결하여

답변

답변

답변

답변

3 비트의 예

답변

답변

답변