Энтропия и короткие сообщения

Eliezer Yudkowsky, “ Entropy, and Short Codes ”, public translation into Russian from English More about this translation.

Translate into another language.

Participants

Muyyd1 964 points
Join Translated.by to translate! If you already have a Translated.by account, please sign in.
If you do not want to register an account, you can sign in with OpenID.
Pages: ← previous Ctrl next
1 2 3

Entropy, and Short Codes

Энтропия и короткие сообщения

History of edits (Latest: Muyyd1 1 month, 3 weeks ago) §

Suppose you have a system X that's equally likely to be in any of 8 possible states:

Предположим, у нас есть система Х, которая с одинаковой вероятностью может находиться в любом из 8 возможных состояний:

History of edits (Latest: Muyyd1 1 month, 2 weeks ago) §

{X1, X2, X3, X4, X5, X6, X7, X8.}

{X1, X2, X3, X4, X5, X6, X7, X8.}

History of edits (Latest: Muyyd1 1 month, 3 weeks ago) §

There's an extraordinarily ubiquitous quantity—in physics, mathematics, and even biology—called entropy; and the entropy of X is 3 bits. This means that, on average, we'll have to ask 3 yes-or-no questions to find out X's value. For example, someone could tell us X's value using this code:

Есть такая экстраординарно распространенная мера --- в физике, математике, и даже в биологии, называется она "энтропия". И энтропия Х составляет 3 бита. Это значит, что для выяснения состояния Х нам в среднем понадобиться 3 да/нет вопроса. Например, кто-то может нам рассказать о значении Х с помощью такого кода:

History of edits (Latest: Muyyd1 1 month, 2 weeks ago) §

X1: 001 X2: 010 X3: 011 X4: 100

X1: 001 X2: 010 X3: 011 X4: 100

History of edits (Latest: Muyyd1 1 month, 3 weeks ago) §

X5: 101 X6: 110 X7: 111 X8: 000

X5: 101 X6: 110 X7: 111 X8: 000

History of edits (Latest: Muyyd1 1 month, 3 weeks ago) §

So if I asked "Is the first symbol 1?" and heard "yes", then asked "Is the second symbol 1?" and heard "no", then asked "Is the third symbol 1?" and heard "no", I would know that X was in state 4.

Так что если я спросил бы "Первый символ 1?" и получил бы ответ "да"; "второй символ 1?" и услышал бы "нет"; "третий символ 1?" --- "нет"; то я бы знал, что Х находится в состоянии 4.

History of edits (Latest: Muyyd1 1 month, 2 weeks ago) §

Now suppose that the system Y has four possible states with the following probabilities:

Теперь предположим, что у системы Y есть четыре возможных состояния с таким распределением вероятностей:

History of edits (Latest: Muyyd1 1 month, 3 weeks ago) §

Y1: 1/2 (50%) Y2: 1/4 (25%) Y3: 1/8 (12.5%) Y4: 1/8 (12.5%)

Y1: 1/2 (50%) Y2: 1/4 (25%) Y3: 1/8 (12.5%) Y4: 1/8 (12.5%)

History of edits (Latest: Muyyd1 1 month, 3 weeks ago) §

Then the entropy of Y would be 1.75 bits, meaning that we can find out its value by asking 1.75 yes-or-no questions.

Тогда энтропия Y будет равна 1, 75 бит, что значит нам понадобится 1, 75 вопросов в среднем, чтобы узнать значение Y.

History of edits (Latest: Muyyd1 1 month, 3 weeks ago) §

What does it mean to talk about asking one and three-fourths of a question? Imagine that we designate the states of Y using the following code:

В каком смысле можно задать один и три-четвертых вопроса? Представьте, что мы используем следующий код для описания состояния Y:

History of edits (Latest: Muyyd1 1 month, 3 weeks ago) §

Y1: 1 Y2: 01 Y3: 001 Y4: 000

Y1: 1 Y2: 01 Y3: 001 Y4: 000

History of edits (Latest: Muyyd1 1 month, 3 weeks ago) §

First you ask, "Is the first symbol 1?" If the answer is "yes", you're done: Y is in state 1. This happens half the time, so 50% of the time, it takes 1 yes-or-no question to find out Y's state.

Сначала вы спросите "первый символ 1?", и если ответ "да", то задача решена: Y находится в состоянии 1. И такое происходит в половине случаев --- состояние Y можно вычислить с помощью одного вопроса.

History of edits (Latest: Muyyd1 1 month, 3 weeks ago) §

Suppose that instead the answer is "No". Then you ask, "Is the second symbol 1?" If the answer is "yes", you're done: Y is in state 2. Y is in state 2 with probability 1/4, and each time Y is in state 2 we discover this fact using two yes-or-no questions, so 25% of the time it takes 2 questions to discover Y's state.

Предположим, что вы получили ответ "нет". Тогда вы спрашиваете: "второй символ 1?" Если ответ "да", то вы закончили: Y находится в состоянии 2. И это происходит с вероятностью в 1/4, и каждый раз, когда Y в состоянии 2, мы можем узнать это с помощью двух да/нет вопросов --- в 25% случаев понадобится два вопроса для определения состояния Y.

History of edits (Latest: Muyyd1 1 month, 3 weeks ago) §

If the answer is "No" twice in a row, you ask "Is the third symbol 1?" If "yes", you're done and Y is in state 3; if "no", you're done and Y is in state 4. The 1/8 of the time that Y is in state 3, it takes three questions; and the 1/8 of the time that Y is in state 4, it takes three questions.

Если же вы получили ответ "нет" два раза подряд, и, спросив "третий символ 1?", получили ответ "да", то задача решена и Y в состоянии 3; если нет, то Y в состоянии 4. В 1/8 случаев Y в состоянии 3 и понадобится три вопроса. И в 1/8 случаев Y в состоянии 4 и понадобится три вопроса.

History of edits (Latest: Muyyd1 1 month, 2 weeks ago) §
Pages: ← previous Ctrl next
1 2 3