Databases Reference
In-Depth Information
1
1
To do this we use our second requirement that
H
(
n
,...,
n
)
be a monotonically increasing
function of
n
.As
H
1
1
n
n
,...,
=
A
(
n
)
this means that
A
(
n
)
is a monotonically increasing function of
n
.If
k
m
j
l
k
m
+
1
then in order to satisfy our second requirement
k
m
+
1
k
m
j
l
A
(
)
A
(
)
A
(
)
or
mA
(
k
)
lA
(
j
)
(
m
+
1
)
A
(
k
)
Dividing through by
lA
(
k
)
, we get
m
l
A
(
j
)
m
l
+
1
l
)
A
(
k
Using the same arguments as before, we get
<
m
l
−
A
(
j
)
A
(
k
)
where
can be made arbitrarily small.
Now
A
(
j
)
A
away from
l
, and
log
j
log
k
is at most a distance of
is at most a distance of
away
(
k
)
A
(
j
)
away from
log
j
from
l
. Therefore,
is at most a distance of 2
log
k
:
A
(
k
)
<
A
(
j
)
log
j
log
k
)
−
2
A
(
k
We can pick
to be arbitrarily small, and
j
and
k
are arbitrary. The only way this inequality
can be satisfied for arbitrarily small
and arbitrary
j
and
k
is for
A
(
j
)
=
K
log
(
j
)
, where
K
is
an arbitrary constant. In other words,
H
=
K
log
(
n
)
Up to this point we have only looked at equally likely events. We now make the transition
to the more general case of an experiment with outcomes that are not equally likely. We do
that by considering an experiment with
n
i
equally likely outcomes that are grouped in
n
unequal groups of size
n
i
with rational probabilities (if the probabilities are not rational, we
approximate them with rational probabilities and use the continuity requirement):
n
i
j
=
1
n
j
Given that we have
n
i
equally likely events, from the development above we have
=
p
i
K
log
n
j
H
=
(6)
