Information Technology Reference
In-Depth Information
The evaluation of this ratio allows us the evaluation of
b
(
n
)
as
n
goes to infinity.
2
b
(
2
n
)
has to be a sub-linear function of
n
, because otherwise the ratio
(
b
(
n
))
In fact,
b
(
n
)
could not be of type
c
√
n
. Therefore,
b
(
2
n
)=
qb
(
n
)
, with
q
<
2, and the following
equation holds:
2
(
b
(
n
))
b
(
n
)
)
=
.
b
(
2
n
q
Now, if the above ratios have to equal
√
π
has to be asymptotically
k
√
n
for some suitable
k
. If we replace this value in the above equation, then we get:
n
,then
b
(
n
)
2
k
2
n
k
√
2
n
→
→
∞
√
π
(
b
(
n
))
)
=
n
n
b
(
2
n
therefore
k
√
n
√
2
→
n
→
∞
√
π
n
√
2
√
2
=
(
)
→
which means that
k
n
. This concludes the proof of
Stirling's approximation (more precise forms of this approximation can be found in
Feller's topic [221]).
π
and
b
n
π
n
→
∞
7.6
“Ars Conjectandi” and Statistical Tests
A
statistical distribution
on a population of objects is obtained by associating to
each of them a numerical value. These values over the population naturally provide
a population of numbers, for which many important concepts can be defined.
For example, let us consider a text seen as a multiset of words (ignoring their
order), if we assign to each word its length, we get a statistical distribution (of word
lengths) taking values in the positive integers.
Given a statistical distribution
X
,the
frequency
X
is the
ratio between the multiplicity of
x
in
X
and the size of
X
.The
range
of
X
is the inter-
val between the
minimum
and the
maximum
values occurring in
X
.The
majority
and the
minority
of
X
are the maximum multiplicity and minimum multiplicity of
X
, respectively. The
mode
is the value (or the values) having the majority as multi-
plicity, while the
median
is the value in the middle position, when values of
X
are
arranged in increasing order (if the elements of
X
are an even number, either the last
value of the first half, or the first one of the second half is chosen as median).
A
discrete statistical distribution
or
interval statistical distribution
, is a statis-
tical distribution where the range of the distribution is partitioned into disjoint inter-
vals (usually having the same length) and only one value for each interval occurs in
the distribution, for example, the middle point of each interval.
Given a statistical distribution
X
ν
(
x
)
of an element
x
∈
=(
x
1
,
x
2
,...,
x
n
)
, its
mean
μ
(
X
)
is given by:
x
1
+
x
2
+
...
+
x
n
=
x
∈
X
ν
(
x
)
x
.
μ
(
X
)=
(7.10)
n
