Information Technology Reference
In-Depth Information
among input variables and since for each position that it occupies there are
(
n
−
1
)
n−
1
ways to fill the remaining
n
1 positions so that the
i
th value is unique, we have that
E
[
X
i
]=
f
(
n
)
where
f
(
n
)=
n
(
n
−
1
)
n−
1
/n
n
=(
1
1
/n
)
n
/
(
1
1
/n
)
.But
f
(
n
)
is
a decreasing function of
n
, as is shown by calculating its derivative and using the inequality
(
1
−
−
−
e
−x
(see Problem
10.5
). The limit of
f
(
n
)
for large
n
is
e
−
1
because in the limit
of small
x
the function
e
−x
has value 1
−
x
)
≤
−
x
. It follows that
E
[
u
(
x
)]
>n/e
.
Let
π
=
P
r
[
u
(
x
)
≥
n/
(
2
e
)]
be the fraction (or probability) of the input
n
-tuples
for which
u
(
x
)
≥
n/
(
2
e
)
). Because
u
(
x
)
≤
n
, it follows that
πn
+(
1
−
π
)
n/
(
2
e
)
≥
E
[
u
(
x
)]
≥
n/e
, from which we conclude that
π>
1
/
(
2
e
−
1
)
. (This is known as
Markov's
inequality
.)
LEMMA
10.13.7
Let
|S|
=
n
.Then
f
(
n
)
n
m
,
m
=
n/
(
2
e
)
,is
(
φ
,
λ
,
μ
,
ν
,
τ
)
-
restricted
:
S
→S
distinguishable for
φ
=
1
/
(
2
e
−
1
)
,
λ
=
μ
=
1
,
ν
=(
1
−
1
/
(
2
e
))
/
log
2
n
,and
τ
(
b
)=
n
.
Proof
If
f
(
n
)
restricted
is
(
φ
,
λ
,
μ
,
ν
,
τ
)
-distinguishable for
φ
=
1
/
(
2
e
−
1
)
,
λ
=
μ
=
1
/
2,
ν
=(
1
−
1
/
(
2
e
))
/
log
2
n
,and
τ
(
b
)=
n
, then for at least
φn
n
input tuples and any
a
≤
λn
μm
output variables and specified values for them,
f
(
n
)
input and
b
≤
restricted
has at most
n
n−a−νb
=
n
n−a
e
−
(
1
−
1
/
(
2
e
))
b
input
n
-tuples that are consistent with these assignments.
The order of output values to
f
(
n
)
restricted
is irrelevant.
B
be the values of the
b
selected and specified unique outputs,
b
≤
m
,andlet
A
Let
be the values of the
a
selected and specified input values. The
k
values in
B−A
appear in
input positions that are not specified.
r
=
n
−
k
−
a
inputs are in neither
A
B
.We
overestimate the number of patterns of inputs consistent with the
a
inputs and
b
outputs
that are specified if we allow these
a
inputs to assume any value not in
nor
B
, since all values in
b
)
r
ways to assign values to these
r
inputs. The
B
are unique. Thus, there are at most
(
n
−
k
values in
are fixed, but their positions among the
r
+
k
non-selected inputs are
not fixed. Since there are
(
r
+
k
)!
/r
!
ways for these ordered
k
values to appear among any
specific ordering of the remaining
r
non-selected inputs (see Problem
10.6
), the number
Q
of input patterns consistent with the selected and specified
a
inputs and
b
outputs satisfies
the following inequality:
B−A
(
r
+
k
)!
r
!
b
)
r
Q
≤
(
n
−
b
. Below we bound
(
r
+
k
)!
/r
!
by
(
r
+
k
)
k
and use the
Here
r
+
k
=
n
−
a
≤
n
and
k
≤
e
−x
:
inequality
(
1
−
x
)
≤
k
1
r
n
r
+
k
1
a
n
b
n
(
r
+
k
)
k
(
n
b
)
r
Q
≤
−
≤
−
−
n
n−a
e
−
(
ka/n
+
rb/n
)
n
n−a
e
−
(
ka/n
+(
n−a−k
)
b/n
)
≤
≤
The exponent
e
(
a
,
b
,
k
)=
ka/n
+(
n
−
a
−
k
)
b/n
is a decreasing function of
a
whose
smallest value is
(
1
−
k/n
)
b
. In turn, this function is a decreasing function of
k
whose
smallest value is
(
1
−
b/n
)
b
≥
(
1
−
1
/
(
2
e
))
b
. As a consequence, we have
n
n−a
e
−
(
1
−
1
/
(
2
e
))
b
Q
≤
It follows that
f
(
n
)
restricted
is
(
φ
,
λ
,
μ
,
ν
,
τ
)
-distinguishable for
φ
=
1
/
(
2
e
−
1
)
,
λ
=
μ
=
1,
ν
=(
1
−
1
/
(
2
e
))
/
log
2
n
,and
τ
(
b
)=
n
.
Search WWH ::
Custom Search