Mengapa menghasilkan 8 bit acak yang seragam pada (0, 255)?

35

Saya menghasilkan 8 bit acak (0 atau 1) dan menggabungkannya bersama-sama untuk membentuk angka 8-bit. Simulasi Python sederhana menghasilkan distribusi yang seragam pada set diskrit [0, 255].

Saya mencoba membenarkan mengapa ini masuk akal di kepala saya. Jika saya membandingkan ini dengan membalik 8 koin, bukankah nilai yang diharapkan sekitar 4 ekor / 4 ekor? Jadi bagi saya, masuk akal bahwa hasil saya harus mencerminkan lonjakan di tengah kisaran. Dengan kata lain, mengapa urutan 8 nol atau 8 yang tampaknya sama mungkin dengan urutan 4 dan 4, atau 5 dan 3, dll? Apa yang kulewatkan di sini?

seperti kaca
sumber
17
Nilai yang diharapkan dari distribusi bit dalam acak acak kisaran [0,255] juga sekitar 4 1/4 0.
user253751
2
Hanya karena Anda memberikan bobot yang sama untuk setiap angka 0 hingga 255, tidak berarti hasil fungsi "perbedaan antara hitungan 1s dan 0s" juga akan terjadi sekali dan hanya sekali. Saya bisa memberikan bobot yang sama untuk setiap orang di organisasi saya. Tidak berarti usia mereka akan sama-sama berbobot. Beberapa usia mungkin jauh lebih umum daripada yang lain. Tetapi satu orang tidak lebih umum daripada orang lain.
Brad Thomas
2
Pikirkan seperti ini ... Bit acak pertama Anda akan menentukan nilai bit 7, 1 bernilai 128 dan 0 bernilai 0. Dari 256 angka, Anda memiliki peluang 50% dari angka 0-127 jika bit adalah 0 dan 128-255 jika bitnya adalah 1. Misalkan 0, maka bit berikutnya menentukan apakah hasilnya akan 0-63 atau 64-127. Semua 8 bit diperlukan untuk membentuk salah satu dari 256 hasil yang kemungkinan sama. Anda berpikir untuk menambahkan total seperti yang Anda lakukan dengan dadu. Peluang mendapatkan 4 1s dan 4 0s lebih tinggi daripada mendapatkan 8 1s, tetapi ada lebih banyak cara mereka dapat diatur untuk memberi Anda hasil yang berbeda.
Jason Goemaat
2
Misalkan Anda melempar dadu berpihak 256 yang bertuliskan angka 0 hingga 255. Anda akan mengharapkan distribusi yang seragam. Sekarang anggaplah Anda menandai ulang dadu sehingga satu sisi mengatakan 0, 8 sisi mengatakan 1, 28 sisi mengatakan 2, dan seterusnya; setiap sisi sekarang diberi label dengan jumlah bit on pada jumlah yang dulu ada di sisi itu. Anda melempar mati lagi; mengapa Anda berharap mendapatkan distribusi angka yang seragam dari 0 hingga 8?
Eric Lippert
Jika distribusinya bekerja seperti ini, maka saya dapat menghasilkan banyak uang dengan bertaruh pada roulette hanya setelah 7 merah muncul berturut-turut. 7 dan 1 lebih 8 kali lebih mungkin daripada 8 dan 0! (Mengabaikan 0's, tetapi condong ini jauh melebihi 0, dan 00 condong)
Cruncher

Jawaban:

61

TL; DR: Kontras yang tajam antara bit dan koin adalah bahwa dalam kasus koin, Anda mengabaikan urutan hasilnya. HHHHTTTT diperlakukan sama seperti TTTTHHHH (keduanya memiliki 4 kepala dan 4 ekor). Tetapi dalam bit, Anda peduli dengan urutan (karena Anda harus memberikan "bobot" ke posisi bit untuk mendapatkan 256 hasil), jadi 11110000 berbeda dari 00001111.


Penjelasan yang lebih panjang: Konsep-konsep ini dapat lebih tepat disatukan jika kita sedikit lebih formal dalam membingkai masalah. Anggap percobaan sebagai urutan delapan percobaan dengan hasil dikotomis dan probabilitas "sukses" 0,5, dan "kegagalan" 0,5, dan uji coba itu independen. Secara umum, saya akan menyebut ini keberhasilan, n percobaan total dan kegagalan n - k dan probabilitas keberhasilan adalah p .knn-khal

  • Dalam contoh koin, hasil " kepala , ekor n - k " mengabaikan urutan percobaan (4 kepala adalah 4 kepala tidak peduli urutan kejadiannya), dan ini memunculkan pengamatan Anda bahwa 4 kepala lebih mungkin daripada 0 atau 8 kepala. Empat kepala lebih umum karena ada banyak cara untuk membuat empat kepala (TTHHTTHH, atau HHTTHHTT, dll.) Daripada ada beberapa nomor lainnya (8 kepala hanya memiliki satu urutan). Teorema binomial memberikan sejumlah cara untuk membuat konfigurasi yang berbeda ini.kn-k

  • Sebaliknya, urutan penting untuk bit karena setiap tempat memiliki "bobot" atau "nilai tempat" yang terkait. Salah satu properti dari koefisien binomial adalah bahwa , yaitu jika kita menghitung semua urutan yang berbeda, kita mendapatkan28=256. Ini secara langsung menghubungkan gagasan tentang berapa banyak cara yang berbeda untuk membuatkhead din2n=k=0n(nk)28=256kn percobaan binomial untuk jumlah urutan byte yang berbeda.

  • Selain itu, kami dapat menunjukkan bahwa 256 hasil kemungkinan sama-sama dimiliki oleh properti kemerdekaan. Uji coba sebelumnya tidak memiliki pengaruh pada uji coba berikutnya, sehingga probabilitas pemesanan tertentu adalah, secara umum, (karena probabilitas gabungan peristiwa independen adalah produk dari probabilitas mereka). Karena cobaan itu adil, P ( sukses ) = P ( gagal ) = p = 0,5 , ungkapan ini berkurang menjadi P ( urutan apa pun ) = 0,5 8 =halk(1-hal)n-kP(keberhasilan)=P(gagal)=hal=0,5 . Karena semua pemesanan memiliki probabilitas yang sama, kami memiliki distribusi yang seragam atas hasil-hasil ini (yang oleh pengkodean biner dapat direpresentasikan sebagai bilangan bulat dalam[0,255]).P(any ordering)=0.58=1256[0,255]

  • Akhirnya, kita dapat mengambil lingkaran penuh ini kembali ke lemparan koin dan distribusi binomial. Kita tahu kemunculan 0 head tidak memiliki probabilitas yang sama dengan 4 head, dan bahwa ini karena ada berbagai cara untuk memesan kemunculan 4 head, dan bahwa jumlah pemesanan tersebut diberikan oleh teorema binomial. Jadi harus ditimbang entah bagaimana, khususnya harus ditimbang dengan koefisien binomial. Jadi ini memberi kita PMF dari distribusi binomial, P ( k  successes ) = ( nP(4 heads). Mungkin mengejutkan bahwa ungkapan ini PMF sebuah, secara khusus karena itu tidak segera jelas bahwa itu merangkum ke 1. Untuk memverifikasi, kita harus memeriksa bahwaΣ n k = 0 ( nP(k successes)=(nk)pk(1p)nk, namun hal ini hanya masalah koefisien binomial:1=1n=(p+1-p)n=Σ n k = 0 ( nk=0n(nk)pk(1p)nk=1.1=1n=(p+1p)n=k=0n(nk)pk(1p)nk

Sycorax berkata Reinstate Monica
sumber
Itu masuk akal ... tapi bukankah kita berharap 15, 30, 60, 120 dan 240 memiliki bobot yang lebih tinggi dalam distribusi daripada 0 atau 255?
kaca
1
Saya pikir saya mengerti sekarang. Saya akan menerima jawaban ini karena saya pikir kuncinya di sini adalah urutan, yang Anda perhatikan. Terima kasih
kaca
Satu lagi catatan - untuk menggunakan contoh koin saya, ini benar-benar membalik 8 koin pada saat yang sama berlawanan dengan 8 percobaan membalik koin. Disinilah letak kebingungan saya.
kaca
2
Konsep "nilai tempat" dari "aritmatika tingkat dasar" dapat diterapkan secara khusus di sini; untuk menggunakan analogi desimal, orang menganggap 10001000dan 10000001menjadi angka yang sangat berbeda.
JM bukan ahli statistik
17

mengapa urutan 8 nol atau 8 yang tampaknya sama mungkin dengan urutan 4 dan 4, atau 5 dan 3, dll

Paradoks aparent dapat diringkas dalam dua proposisi, yang mungkin tampak kontradiktif:

  1. Urutan (delapan nol) sama - sama mungkin sebagai urutan s 2 : 01010101 (empat nol, empat yang). (Secara umum: semua urutan 2 8 memiliki probabilitas yang sama, terlepas dari berapa banyak nol / yang mereka miliki.)s1:00000000s2:0101010128

  2. Acara " : urutan memiliki empat nol " lebih mungkin (memang, 70 kali lebih mungkin) daripada acara " e 2 : urutan memiliki delapan nol ".e170e2

Proposisi ini sama-sama benar. Karena acara mencakup banyak urutan.e1

leonbloy
sumber
8

Semua dari sekuens memiliki probabilitas yang sama 1/2 8 = 1/256. Adalah salah untuk berpikir bahwa urutan yang lebih dekat ke jumlah yang sama dengan 0s dan 1s lebih mungkin ketika pertanyaan ditafsirkan. Harus jelas bahwa kita sampai pada 1/256 karena kita mengasumsikan independensi dari percobaan ke percobaan . Itu sebabnya kami mengalikan probabilitas dan hasil dari satu percobaan tidak memiliki pengaruh pada yang berikutnya.2828

Michael R. Chernick
sumber
2
Ini akan baik-baik saja, jika singkat, jawab ... jika pertanyaannya tidak termasuk kata "mengapa". Karena itu, Anda cukup mengulangi salah satu dari givens dalam pertanyaan, tanpa penjelasan yang diberikan.
Tin Man
1
Sebenarnya ... Jawaban ini sebenarnya salah, lihat jawaban leonbloy untuk alasannya.
Tin Man
3
@ Walau itu tidak salah. Kehalusan bahasa. Setiap urutan yang diberikan tidak lebih mungkin karena memiliki ketidakseimbangan antara 0s dan 1s. Ada lebih banyak urutan seperti itu .
hobbs
4
Adakah yang setuju dengan saya? Jika 0 memiliki probabilitas 1/2 dan 1 memiliki probabilitas 1/2 dan satu istilah dalam urutan independen dari berikutnya kemungkinan urutan tertentu panjang 8 memiliki probabilitas . dan begitu pula urutan 8. lainnya.1/28=1/256
Michael R. Chernick
4
@Michael Saya sepenuhnya setuju dan senang melihat - akhirnya! - seruan eksplisit ke inti permasalahan: kemerdekaan. Saya akan dengan senang hati mengubah jawaban Anda jika Anda mau memasukkan komentar itu di dalamnya.
whuber
7

CONTOH dengan 3 bit (seringkali contoh lebih ilustratif)

Saya akan menulis bilangan asli 0 hingga 7 sebagai:

  • Angka dalam basis 10
  • Angka dalam basis 2 (yaitu urutan bit)
  • Serangkaian flips koin tersirat oleh representasi basis 2 (1 menunjukkan flip kepala dan 0 menunjukkan flip ekor).

Base 10Base 2 (with 3 bits)Implied Coin Flip SeriesHeadsTails0000TTT031001TTH122010THT123011THH214100HTT125101HTH216110HHT217111HHH30

Memilih bilangan alami dari 0 hingga 7 dengan probabilitas yang sama setara dengan memilih salah satu dari seri flip koin di sebelah kanan dengan probabilitas yang sama.

18 chance of choosing 3 heads, 38 chance of choosing 2 heads, 38 chance of choosing 1 head, and 18 chance of choosing 0 heads.

Matthew Gunn
sumber
3

Jawaban Sycorax benar, tetapi sepertinya Anda tidak sepenuhnya tahu mengapa. Ketika Anda membalik 8 koin atau menghasilkan 8 bit acak dengan mempertimbangkan, hasil Anda akan menjadi salah satu dari 256 kemungkinan yang sama-sama memungkinkan. Dalam kasus Anda, masing-masing 256 kemungkinan hasil ini secara unik memetakan ke integer, sehingga Anda mendapatkan distribusi yang seragam sebagai hasil Anda.

Jika Anda tidak memperhitungkannya, seperti mempertimbangkan berapa banyak kepala atau ekor yang Anda dapatkan, hanya ada 9 hasil yang mungkin (0 Kepala / 8 Ekor - 8 Kepala / 0 Ekor), dan mereka tidak lagi sama kemungkinannya . Alasan untuk ini adalah karena dari 256 hasil yang mungkin, ada 1 kombinasi membalik yang memberi Anda 8 Kepala / 0 Ekor (HHHHHHHH) dan 8 kombinasi yang memberikan 7 Kepala / 1 Ekor (Ekor di masing-masing dari 8 posisi di urutan), tetapi 8C4 = 70 cara untuk memiliki 4 Kepala dan 4 Ekor. Dalam kasus membalik koin, masing-masing 70 kombinasi tersebut memetakan menjadi 4 Kepala / 4 Ekor, tetapi dalam masalah bilangan biner, masing-masing dari 70 hasil tersebut memetakan ke bilangan bulat unik.

Blacksteel
sumber
2

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)=12; .

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 i=182i1Xi, where Xi are the left to right ith 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 28=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; i=1820Xi, which in turn reduces to C(8,i=18Xi), the number of combinations of 8 objects taken i=18Xi 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.enter image description here

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 2569=247 overall.

Carl
sumber
2
Using the conventional way to name numbers--by omitting all reference to preceding zeros--potentially confuses this explanation. Don't you think the situation would become much clearer by writing 0 as 00000000, 1 (which you inadvertently omitted) as 00000001, and so on?
whuber
16
Frankly this is all correct as far as it goes but it doesn't address the question. You've done a fine job of showing how eight ordered bits can represent numbers in the range, but haven't explained why selecting those bits at random give a uniform distribution (something which is, admittedly, so simple that explaining it clearly takes some subtlety).
dmckee
9
Wouldn't it be simpler to say that 8 (independently) random bits is uniformly distributed on [00000000, 11111111] for the same reason that 3 random digits is uniformly distributed on [000, 999]? The side rant about how/why computers use binary and the fractional bases is totally unnecessary and unrelated. I mean, the fact that binary uses only the symbols 0 and 1 is just an inherent property of base 2... no need to explain that. If you wanted to keep that kind of explanation in there, it would probably be more useful to explain how bases work in general, but it would still be beside the point.
Blackhawk
3
I am glad to see how much this answer has improved. However, I have difficulty seeing what base-10 representations have to do with this question (wouldn't base-3 or base-17 work just as well?) and I cannot see what might be special about 8 bits that doesn't also generalize to any finite number of bits. That suggests that most of the considerations in this answer are tangential or irrelevant.
whuber
3
And I wish to thank you for that felicitous characterization of the confusion expressed in the question: "lossy" and "lossless" encoding. It's memorable, slightly different than other perspectives, insightful, and potentially could clear up that confusion quickly.
whuber
1

I'd like to expand a little bit on the idea of order dependence vs. independence.

In the problem of calculating the expected number of heads from flipping 8 coins, we're summing the values from 8 identical distributions, each of which is the Bernoulli distribution [; B(1, 0.5) ;] (in other words, a 50% chance of 0, a 50% chance of 1). The distribution of the sum is the binomial distribution [; B(8, 0.5) ;], which has the familiar hump shape with most of the probability centered around 4.

In the problem of calculating the expected value of a byte made of 8 random bits, each bit has a different value that it contributes to the byte, so we're summing the values from 8 different distributions. The first is [; B(1, 0.5) ;], the second is [; 2 B(1, 0.5) ;], the third is [; 4 B(1, 0.5) ;] , so on up to the eighth which is [; 128 B(1, 0.5) ;]. The distribution of this sum is understandably quite different from the first one.

If you wanted to prove that this latter distribution is uniform, I think you could do it inductively — the distribution of the lowest bit is uniform with a range of 1 by assumption, so you would want to show that if the distribution of the lowest [; n ;] bits is uniform with a range of [; 2^n - 1} ;] then the addition of the [; n+1 ;]st bit makes the distribution of the lowest [; n + 1 ;] bits uniform with a range of [; 2^{n+1} - 1 ;], achieving a proof for all positive [; n ;]. But the intuitive way is probably the exact opposite. If you start at the high bit, and choose values one at a time down to the low bit, each bit divides the space of possible outcomes exactly in half, and each half is chosen with equal probability, so by the time you get to the bottom, each individual value must have had the same probability to be chosen.

hobbs
sumber
Ini bukan seragam berkelanjutan. Bitnya 0 atau 1 dan tidak ada di antara keduanya.
Michael R. Chernick
@MichaelChernick tentu saja kita hanya berurusan dengan distribusi diskrit di sini.
hobbs
The OP said that the bits are only 1 or 0 and nothing in between.
Michael R. Chernick
1
@MichaelChernick correct.
hobbs
1

If you do a binary search comparing each bit, then you need the same number of steps for each 8 bit number, from 0000 0000 to 1111 1111, they both have the length 8 bit. At each step in the binary search both sides have a 50/50 chance of occuring, so in the end, because every number has the same depth and the same probabilities, without any real choice, each number must have the same weight. Thus the distribution must be uniform, even when each individual bit is determined by coin flips.

However, the digitsum of the numbers isn't uniform and would be equal in distribution to tossing 8 coins.

HopefullyHelpful
sumber
1

There is only one sequence with eight zeros. There are seventy sequences with four zeros and four ones.

Therefore, while 0 has a probability of 0.39%, and 15 [00001111] also has a probability of 0.39%, and 23 [00010111] has a probability of 0.39%, etc., if you add up all seventy of the 0.39% probabilities you get 27.3%, which is the probability of having four ones. The probability of each individual four-and-four result does not have to be any higher than 0.39% for this to work.

Random832
sumber
This doesn't change the fact that all 256 sequences are equally probable.
Michael R. Chernick
@MichaelChernick I didn't say it did, I explicitly said that they all have a probability of 0.39%, I'm addressing OP's assumptions.
Random832
You are right. It is another way of saying what I said in my answer. Some of the other answers are wrong.
Michael R. Chernick
1

Consider dice

Think about rolling a couple of dice, a common example of non-uniform distribution. For the sake of the math, imagine the dice are numbered from 0 to 5 instead of the traditional 1 to 6. The reason the distribution is not uniform is that you are looking at the sum of the dice rolls, where multiple combinations can yield the same total like {5, 0}, {0, 5}, {4, 1}, etc. all generating 5.

However, if you were to interpret the dice roll as a 2 digit random number in base 6, each possible combination of dice is unique. {5, 0} would be 50 (base 6) which would be 5*(61) + 0*(60) = 30 (base 10). {0, 5} would be 5 (base 6) which would be 5*(60) = 5 (base 10). So you can see, there is a 1 to 1 mapping of possible dice rolls interpreted as numbers in base 6 versus a many to 1 mapping for the sum of the two dice each roll.

As both @Sycorax and @Blacksteel point out, this difference really boils down to the question of order.

Blackhawk
sumber
0

Each bit you choose is independent from each other bit. If you consider for the first bit there is a

  • 50% probability it will be 1

and

  • 50% probability it will be 0.

This also applies to the second bit, third bit and so on so that you end up with so for each possible combination of bits to make your byte you have (12)8 = 1256 chance of that unique 8 bit integer occurring.

Ahemone
sumber
All of these statements are true, but this doesn't address why coin tosses, which are also fair and independent, have only 9 distinct outcomes when an outcome is defined as the number of heads and tails.
Sycorax says Reinstate Monica
That is only a result of placing the results into an ordered system after choosing them. The same distribution would be achieved even if the random bits were placed into random positions on the byte. You also will get the same distribution on coin tosses by the way you frame the question to finding the chance of getting a particular combination of heads and tails, such as HHTHTTTH. You will have a 1/256 chance of getting that exact sequence of coin tosses for the 8 coin tosses being performed each time.
Ahemone
This is all good information to include in the answer itself. My comment doesn't take issue with what you've said so much as the omission of a direct address of OP's source of confusion: the relationship between bits and coin flips.
Sycorax says Reinstate Monica
I should also say in order to get to the OP's expected value of 4 they are trying to find the probability of n many 1's or n many 0's in a given byte. This framing of the question would give the binomial distribution they were expecting in their mind rather than the uniform distribution of finding the probability of obtaining a certain value from those random bits.
Ahemone