Dlaczego generowanie 8 losowych bitów jest jednolite na (0, 255)?

Generuję 8 losowych bitów (0 lub 1) i łączę je ze sobą, tworząc liczbę 8-bitową. Prosta symulacja Pythona daje równomierny rozkład w zestawie dyskretnym [0, 255].

Próbuję uzasadnić, dlaczego to ma sens w mojej głowie. Jeśli porównam to do rzucenia 8 monetami, czy oczekiwana wartość nie wyniesie gdzieś około 4 głów / 4 ogonów? Dla mnie więc sensowne jest, że moje wyniki powinny odzwierciedlać skok w środku zakresu. Innymi słowy, dlaczego sekwencja 8 zer lub 8 zer wydaje się być równie prawdopodobna jak sekwencja 4 i 4 lub 5 i 3 itd.? Czego tu brakuje?

TL; DR: Ostry kontrast między bitami a monetami polega na tym, że w przypadku monet ignorujesz kolejność wyników. HHHHTTTT jest traktowany tak samo jak TTTTHHHH (oba mają 4 głowy i 4 ogony). Ale w bitach zależy Ci na kolejności (ponieważ musisz nadać „wagi” pozycjom bitów, aby uzyskać 256 wyników), więc 11110000 różni się od 00001111.

Dłuższe wyjaśnienie: koncepcje te można bardziej precyzyjnie ujednolicić, jeśli jesteśmy bardziej formalni w formułowaniu problemu. Traktuj eksperyment jako sekwencję ośmiu prób z dychotomicznymi wynikami i prawdopodobieństwem „sukcesu” 0,5 i „porażki” 0,5, a próby są niezależne. Zasadniczo nazywam to sukcesami, n całkowitymi próbami i n - k niepowodzeniami, a prawdopodobieństwo sukcesu wynosi p .$k$$n$$n-k$$p$

• W przykładzie monety wynik „ głów, n - k ogonów” ignoruje kolejność prób (4 głowy to 4 głowy bez względu na kolejność występowania), co daje podstawę do obserwacji, że 4 głowy są bardziej prawdopodobne niż 0 lub 8 głów. Cztery głowy są bardziej powszechne, ponieważ istnieje wiele sposobów na wykonanie czterech głów (TTHHTTHH lub HHTTHHTT itp.) Niż istnieje inna liczba (8 głów ma tylko jedną sekwencję). Twierdzenie dwumianowe podaje liczbę sposobów na wykonanie tych różnych konfiguracji.$k$$n-k$

• Natomiast kolejność jest ważna dla bitów, ponieważ każde miejsce ma przypisaną „wagę” lub „wartość miejsca”. Jedną właściwością współczynnika dwumianowego jest to, że , to znaczy jeśli policzymy wszystkie różne uporządkowane sekwencje, otrzymamy28=256. To bezpośrednio łączy pomysł na wiele różnych sposobów$2^n=\sum_{k=0}^n\binom{n}{k}$$2^8=256$ głowy n dwumianowego próby do liczby różnych sekwencji bajtów.$k$$n$

• Ponadto możemy wykazać, że 256 wyników jest równie prawdopodobne dzięki własności niezależności. Poprzednie próby nie mają wpływu na kolejną próbę, więc prawdopodobieństwo konkretnego uporządkowania wynosi na ogół (ponieważ łączne prawdopodobieństwo wystąpienia niezależnych zdarzeń jest iloczynem ich prawdopodobieństwa). Ponieważ próby są uczciwe, P ( sukces ) = P ( niepowodzenie ) = p = 0,5 , to wyrażenie zmniejsza się do $p^k(1-p)^{n-k}$$P(\text{success})=P(\text{fail})=p=0.5$ . Ponieważ wszystkie zamówienia mają takie samo prawdopodobieństwo, mamy równomierny rozkład tych wyników (który przez kodowanie binarne może być reprezentowane jako liczby całkowite w$P(\text{any ordering})=0.5^8=\frac{1}{256}$ ).$[0,255]$

• Wreszcie możemy przywrócić to pełne koło z powrotem do rzutu monetą i rozkładu dwumianowego. Wiemy, że wystąpienie 0 głów nie ma takiego samego prawdopodobieństwa jak 4 głowy, a to dlatego, że istnieją różne sposoby porządkowania wystąpień 4 głów, a liczba takich porządków jest podana przez twierdzenie dwumianowe. Zatem musi być w jakiś sposób ważone, a konkretnie musi być ważone przez współczynnik dwumianowy. To daje nam PMF rozkładu dwumianowego, P ( k  sukcesów ) $P(\text{4 heads})$. Może być zaskakujące, że to wyrażenie jest PMF, szczególnie dlatego, że nie jest od razu oczywiste, że sumuje się do 1. Aby zweryfikować, musimy sprawdzić, czy∑ n k = 0 ($P(k \text{ successes})=\binom{n}{k}p^k(1-p)^{n-k}$, jednak jest to tylko problem współczynników dwumianowych:1=1n=(p+1-p)n=∑ n k = 0 ($\sum_{k=0}^n \binom{n}{k}p^k(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}$

dlaczego sekwencja 8 zer lub 8 zer wydaje się być równie prawdopodobna jak sekwencja 4 i 4 lub 5 i 3 itd.

Pozorny paradoks można streścić w dwóch twierdzeniach, które mogą wydawać się sprzeczne:

1. Sekwencja (osiem zer) jest równie prawdopodobna jak sekwencja s 2 : 01010101 (cztery zera, cztery jedynki). (Ogólnie: wszystkie 2 $s_1: 00000000$$s_2: 01010101$$2^8$ sekwencji ma takie samo prawdopodobieństwo, niezależnie od liczby zer / jedynek).

2. Zdarzenie „ : sekwencja miała cztery zera ” jest bardziej prawdopodobne (w rzeczywistości 70 razy bardziej prawdopodobne) niż zdarzenie „ e 2 : sekwencja miała osiem zer.$e_1$$70$$e_2$ ”.

Te twierdzenia są prawdziwe. Ponieważ zdarzenie obejmuje wiele sekwencji.$e_1$

Wszystkie sekwencje mają takie samo prawdopodobieństwo 1/ 2 8 = 1/256. Błędem jest sądzić, że sekwencje, które są bliższe równej liczbie zer i jedynek, są bardziej prawdopodobne, gdy pytanie jest interpretowane. Powinno być jasne, że dochodzimy do 1/256, ponieważ zakładamy niezależność od procesu do procesu . Dlatego mnożymy prawdopodobieństwa, a wynik jednej próby nie ma wpływu na następną.$2^8$$2^8$

PRZYKŁAD z 3 bitami (często przykład jest bardziej ilustracyjny)

Napiszę liczby naturalne od 0 do 7 jako:

• Liczba w bazie 10
• Liczba w bazie 2 (tj. Sekwencja bitów)
• Seria rzutów monetą sugerowana przez reprezentację podstawy 2 (1 oznacza przewrócenie głów, a 0 oznacza przewrócenie ogonów).

Wybór liczby naturalnej od 0 do 7 z jednakowym prawdopodobieństwem jest równoznaczny z wybraniem jednej z serii rzutów monetą po prawej z jednakowym prawdopodobieństwem.

$\frac{1}{8}$ chance of choosing 3 heads, $\frac{3}{8}$ chance of choosing 2 heads, $\frac{3}{8}$ chance of choosing 1 head, and $\frac{1}{8}$ chance of choosing 0 heads.

Sycorax's answer is correct, but it seems like you're not entirely clear on why. When you flip 8 coins or generate 8 random bits taking order into account, your result will be one of 256 equally likely possibilities. In your case, each of these 256 possible outcomes uniquely map to an integer, so you get a uniform distribution as your result.

If you don't take order into account, such as considering just how many heads or tails you got, there are only 9 possible outcomes (0 Heads/8 Tails - 8 Heads/0 Tails), and they're no longer equally likely. The reason for this is because out of the 256 possible results, there are 1 combination of flips that gives you 8 Heads/0 Tails (HHHHHHHH) and 8 combinations that give 7 Heads/1 Tails (a Tails in each of the 8 positions in the order), but 8C4 = 70 ways to have 4 Heads and 4 Tails. In the coin flipping case each of those 70 combinations maps to 4 Heads/4 Tails, but in the binary number problem each of those 70 outcomes maps to a unique integer.

The problem, restated, is: Why is the number of combinations of 8 random binary digits taken as 0 to 8 selected digits (e.g., the 1's) at a time different from the number of permutations of 8 random binary digits. In the context herein, random choice of 0's and 1's means that each digit is independent of any other, so that digits are uncorrelated and $p(0)=p(1)=\frac{1}{2}$; .

The answer is: There are two different encodings; 1) lossless encoding of permutations and 2) lossy encoding of combinations.

Ad 1) To lossless encode the numbers so that each sequence is unique we can view that number as being a binary integer $\sum_{i=1}^82^{i-1}{X_i}$, where ${X_i}$ are the left to right $i^{th}$ digits in the binary sequence of random 0's and 1's. What that does is make each permutation unique, as each random digit is then positional encoded. And the total number of permutations is then $2^8=256$. Then, coincidentally one can translate those binary digits into the base 10 numbers 0 to 255 without loss of uniqueness, or for that matter one can rewrite that number using any other lossless encoding (e.g. lossless compressed data, Hex, Octal). The question itself, however, is a binary one. Each permutation is then equally probable because there is then only one way each unique encoding sequence can be created, and we have assumed that the appearance of a 1 or a 0 is equally likely anywhere within that string, such that each permutation is equally probable.

Ad 2) When the lossless encoding is abandoned by only considering combinations, we then have a lossy encoding in which outcomes are combined and information is lost. We are then viewing the number series, w.l.o.g. as the number of 1's; $\sum_{i=1}^82^{0}{X_i}$, which in turn reduces to $C(8,\sum_{i=1}^8{X_i})$, the number of combinations of 8 objects taken $\sum_{i=1}^8{X_i}$ at at time, and for that different problem, the probability of exactly 4 1's is 70 ($C(8,4)$) times greater than obtaining 8 1's, because there are 70, equally likely permutations that can produce 4 1's.

Note: At the current time, the above answer is the only one containing an explicit computational comparison of the two encodings, and the only answer that even mentions the concept of encoding. It took a while to get it right, which is why this answer has been downvoted, historically. If there are any outstanding complaints, leave a comment.

Update: Since the last update, I am gratified to see that the concept of encoding has begun to catch on in the other answers. To show this explicitly for the current problem I have attached the number of permutations that are lossy encoded in each combination.

Note that the number of bytes of information lost during each combinatorial encoding is equivalent to the number of permutations for that combination minus one [$C(8,n)-1$, where $n$ is the number of 1's], i.e., for this problem, from $0$ to $69$ per combination, or $256-9=247$ overall.

Chciałbym trochę rozwinąć ideę zależności porządku od niezależności.

W problemie obliczania oczekiwanej liczby głów po przerzuceniu 8 monet sumujemy wartości z 8 identycznych rozkładów, z których każdy jest rozkładem Bernoulliego [; B(1, 0.5) ;](innymi słowy, 50% szansy na 0, 50% szansy na 1). Rozkład sumy jest rozkładem dwumianowym [; B(8, 0.5) ;], który ma znajomy kształt garbu z większością prawdopodobieństwa wyśrodkowaną wokół 4.

W problemie obliczania oczekiwanej wartości bajtu złożonego z 8 losowych bitów, każdy bit ma inną wartość, niż przyczynia się do bajtu, więc sumujemy wartości z 8 różnych rozkładów. Pierwszym jest [; B(1, 0.5) ;], drugim jest [; 2 B(1, 0.5) ;], trzecim jest [; 4 B(1, 0.5) ;], więc aż do ósmego, co jest [; 128 B(1, 0.5) ;]. Rozkład tej sumy jest, co zrozumiałe, zupełnie inny niż pierwszy.

Jeśli chcesz udowodnić, że ten ostatni rozkład jest jednolity, myślę, że możesz to zrobić indukcyjnie - rozkład najniższego bitu jest jednolity z zakresem 1 z założenia, więc chciałbyś pokazać, że jeśli rozkład najniższych [; n ;]bitów jest jednorodny z zakresem, [; 2^n - 1} ;]a następnie dodanie [; n+1 ;]bitu st sprawia, że ​​rozkład najniższych [; n + 1 ;]bitów jest jednolity z zakresem [; 2^{n+1} - 1 ;], uzyskując dowód na wszystkie dodatnie[; n ;]. Ale intuicyjny sposób jest prawdopodobnie dokładnie odwrotny. Jeśli zaczniesz od wysokiego bitu i wybierzesz wartości pojedynczo w dół do małego bitu, każdy bit dzieli przestrzeń możliwych wyników dokładnie na pół, a każda połowa jest wybierana z jednakowym prawdopodobieństwem, więc do czasu, gdy dojdziesz do na dole, każda indywidualna wartość musiała mieć takie samo prawdopodobieństwo wyboru.

Jeśli wykonujesz wyszukiwanie binarne, porównując każdy bit, potrzebujesz takiej samej liczby kroków dla każdej liczby 8-bitowej, od 0000 0000 do 1111 1111, obie mają długość 8 bitów. Na każdym etapie wyszukiwania binarnego obie strony mają szansę wystąpienia 50/50, więc w końcu, ponieważ każda liczba ma taką samą głębokość i takie same prawdopodobieństwa, bez żadnego rzeczywistego wyboru, każda liczba musi mieć taką samą wagę. Dlatego rozkład musi być jednolity, nawet jeśli każdy pojedynczy bit jest określony przez przerzucenie monety.

Jednak cyfra cyfr nie jest jednolita i będzie równa w rozkładzie do podrzucania 8 monet.

Jest tylko jedna sekwencja z ośmioma zerami. Istnieje siedemdziesiąt sekwencji z czterema zerami i czterema zerami.

Dlatego, podczas gdy 0 ma prawdopodobieństwo 0,39%, a 15 również ma prawdopodobieństwo 0,39%, a 23 [00010111] ma prawdopodobieństwo 0,39% itd., Jeśli zsumujesz wszystkie siedemdziesiąt z 0,39% prawdopodobieństwa dostajesz 27,3%, co jest prawdopodobieństwem posiadania czterech. Prawdopodobieństwo każdego pojedynczego wyniku czterech do czterech nie musi być większe niż 0,39%, aby to zadziałało.

Rozważ kości

Pomyśl o rzuceniu kilkoma kośćmi, co jest częstym przykładem nierównomiernej dystrybucji. Ze względu na matematykę wyobraź sobie, że kości są ponumerowane od 0 do 5 zamiast tradycyjnych od 1 do 6. Powodem, dla którego rozkład nie jest jednolity, jest to, że patrzysz na sumę rzutów kostek, gdzie wiele kombinacji może dać taka sama suma jak {5, 0}, {0, 5}, {4, 1} itd., wszystkie generujące 5.

Jeśli jednak zinterpretujesz rzut kostką jako 2-cyfrową liczbę losową w bazie 6, każda możliwa kombinacja kości jest unikalna. {5, 0} byłoby 50 (podstawa 6), co byłoby 5 * ($6^1$) + 0 * ($6^0$) = 30 (podstawa 10). {0, 5} byłoby 5 (podstawa 6), co byłoby 5 * ($6^0$) = 5 (podstawa 10). Jak widać, istnieje mapowanie 1 do 1 możliwych rzutów kości interpretowane jako liczby w bazie 6 w porównaniu z mapowaniem wielu do 1 dla sumy dwóch kości każdego rzutu.

Jak wskazują zarówno @Sycorax, jak i @Blacksteel, różnica ta naprawdę sprowadza się do kwestii porządku.

Każdy wybrany bit jest od siebie niezależny. Jeśli weźmiesz pod uwagę pierwszy bit, istnieje

• 50% prawdopodobieństwa będzie to 1

i

• 50% prawdopodobieństwa będzie wynosić 0.

Odnosi się to również do drugiego bitu, trzeciego bitu i tak dalej, więc kończy się tak dla każdej możliwej kombinacji bitów, aby twój bajt miał $(\frac{1}{2})^8$ = $\frac{1}{256}$ prawdopodobieństwo wystąpienia tej unikalnej 8-bitowej liczby całkowitej.