|
|
Entropy |
|
||||||||||||||||
|
The last example
in Mixed Strategies was the
game of Catching the Queen:
It was also stated that a fully random frequency
(ie1/ 2) gives South the smallest amount of information
but it wasn't explained what in fact information is and how to measure it.
Let's try to make up for this. |
||||||||||||||||||
Information
When do we get more information, when do we get less
information?
It depends on the probability of the event we were informed about – the
more unexpected the outcome, the more information we get. If the opponents are kind
enough to inform us that the five missing trumps are not divided 5-0, this will
hardly be sensational news since it happens most often. However, if one of the
opponents reveals he's void of the suit, the information we get will be more
substantial since void occurs relatively seldom.
The other consideration is the
usefulness of the information received. It may happen that the information
about the void is hardly useful since the contract is doomed anyway. In
general, though, the more information we have, the better.
The amount of information is measured by the following formula:
|
lob |
1 |
where: |
P = the
probability of the event we were informed about lob = binary
logarithm (the base = 2) |
|
P |
Let's calculate how much information we receive being given the answer
YES where both YES and NO are equally likely (both have P = 1/ 2).
We get exactly 1 (since 1/ P = 2 and lob 2 =
1 (2 to the power of 1 = 2) ), and since
the unit of information is called bit we say we
received 1 bit of information.
The word bit
is derived from binary unit.
The digits in binary system,
0 and 1, are also commonly, though incorrectly, called bits.They should be
called binits from binary digit .
As the probability of YES grows, the information
received diminishes (eg for P = 70% we get half a bit) and when it finally
reaches 100% the information shrinks to 0 (bits). As the probability of YES
diminishes, the number of bits grows (indefinitely).
That the above formula for the amount of information is a reasonable one
is at once seen if we consider a set of more events: A, B, C... We can be
informed about A either immediately or gradually (eg first that it's either A
or B and then that of the two it's A). In both cases we should receive the same
number of bits and, what can be easily checked, this is really so.
Entropy or Uncertainty
Facing a dilemma “Does such and such happen?” we are
in the state of uncertainty: YES or NO? This uncertainty can be measured
by calculating the average number of bits we'll receive when we are informed
what happened:
|
p( YES ) • lob |
1 |
+ p( NO ) • lob |
1 |
p( YES ) p( NO ) = probability of events ( of course p( YES ) + p( NO ) = 1 ) |
|
p( YES
) |
p( NO ) |
The uncertainty calculated in such way is called entropy and one can say it measures our need for information or the degree of
our lack of information. It's believed that the entropy of the universe as a whole
is relentlessly growing everything is moving towards chaos and uncertainty of
what? where? is grows.
( entropy is artificial word: Greek en-tropia
means turning towards the center )
Playing
bridge we should strive to make opponent's entropy the biggest possible.
Let's watch this in the fight
for tricks below:
|
|
K109 |
a priori probability: |
South plays a small to the 9 and regardless of the frequency
East chooses to win with the Q (or the J) a small to the 10 remains the
optimal play in trick two (since the probability of QJx will
never be greater than that any other) |
|
|
Jxx |
N W E S |
AQx |
1/ 3 |
|
|
Axx |
QJx |
1/ 3 |
||
|
Qxx |
AJx |
1/ 3 |
||
|
|
xxxx |
|
|
|
Thus, East is given complete freedom in departing from
randomness he can take the trick with, say, the Queen with any frequency:
0–100%. And doing so he won't loose anything since the optimal strategy for South
remains the same. But... does East really lose nothing?
Let's calculate the average entropy for South as a
function of P = the frequency of East playing the Queen:
If East played the Queen (P) the ratio of probabilities AQJ:QJx
changes from1:1 to 1:P, and entropy = ...
If East played the Jack (1–P) the ratio of probabilities QJx:AJx
changes from 1:1 to 1–P:1, and entropy = ...
Thus, the average entropy is given by the formula ...
(we are skipping the details. Writing a small
program seems best.)
And, finally, we can draw a table:
|
P = |
0 |
.1 |
.2 |
.3 |
.4 |
.5 |
.6 |
.7 |
.8 |
.9 |
1 |
|
average entropy = |
0.667 |
0.793 |
0.855 |
0.892 |
0.912 |
0.918 |
0.912 |
0.892 |
0.855 |
0.793 |
0.667 |
Thus, South is the least certain how things really
are, ie he faces the greatest entropy, if East, holding QJx, chooses his honor
at random (50% the Queen, 50% the Jack). That's what we anticipated since the
problem is a symmetrical one and the Queen and the Jack are equals.
There are more subtle problems, however:
|
Catching the King with the Ten |
Let's
consider the following fight for tricks:
South, the declarer, plays the Queen from dummy:
(let's consider
600 random deals for each case)
|
|
QJ9x |
|
Deals with given discards: |
For example, in the first layout West can reveal his
two cards in six ways. Thus, two given discards are six
times less probable. |
|
|
876 |
N W E S |
K10 |
E has to
play the King |
600
: 6 = 100 |
|
|
1087 |
K6 |
??? |
600
: 2 = 300 |
||
|
108 |
K76 |
E
has to play a spot |
600
: 2 = 300 |
||
|
|
Axxx |
|
|
|
|
The
South strategy depends on the frequency of East's playing the King in all
dubious layouts (K6).
If less than 100 times (out of 300)
South
leads to the Jack next and guarantees himself victory on 400 deals.
If exactly 100 times
after
taking the King with the Ace South can as well finesse on the next round but he
wins the same 400 times.
If more than 100 times
South
finesses next and wins more often than 400 times!
Thus, East should play the King with any frequency not exceeding 1/ 3.
The game above was analyzed in the book “Bez impasu” (Andrzej
Macieszczak and Janusz Mikke, 1980). The authors made a mistake, though
(assuming, it's hard to tell why, that West has one given spot card), obtaining
a false frequency of 1/2. Apart from that effort it seems that there were no
published analyses of similar problems although frequencies are sometimes given
(the Bridge Encyclopedia gives the correct frequency of 1/3 for a twin problem
so one can assume it also applies to the present one).
The
question arises:
Is it irrelevant
how often East covers with the King ?
( provided he does so less often than 1 time in 3 ).
It
turns out that he should cover in a manner that makes the South entropy the
greatest possible!
The scheme of calculations is like
in the last problem. The results are:
|
p = |
0 |
0.1 |
0.2 |
0.249 |
0.250 |
0.251 |
0.3 |
1/3 |
|
average entropy = |
0.857 |
0.957 |
0.983 |
0.985227 |
0.985228 |
0.985227 |
0.983 |
0.978 |
Thus, East should play the
King with the frequency = 1/ 4 !
In the 300 deals analyzed he should play the king 75
times and a small card 225 times, making South face the following dilemma:
if the King appeared it's 100
against 75 for K10 ie 4:3
if a small card appeared it's
300 against 225 for K76 ie again 4:3 !
It
turns out that this result is not accidental. It can be easily proved that
(theorem):
In such trilemma the entropy is the
greatest when the dilemmas
have the equal proportion of
probabilities.
This
will spare us laborious calculations in the future.
At the time of writing the author hadn't
any similar deliberations as a model at his disposal. Everything he had were
the definitions of information and entropy. Some verification of the present
material, and especially of the notion of average entropy, would be welcome.
Guessability
That's
how entropy could be called for bridge purposes.
Since
the entropy of a dilemma falls within the range from 0 to 1 bit, it can be
expressed in percentages: 0% =
everything is known, 100% = nothing is known (pure guess).
If
there are more than 2 events, the entropy should be divided by the binary
logarithm of the number of events.
|
|
|