Information Technology Reference
In-Depth Information
Lemma 14.
Bin
can be interpreted as Binomials of biased
coins. More precisely, they are distributed like the sum of a Binomial and a scalar.
(
2
,
)
and Bin
(
3
,
)
1
4
Proof.
It is easy to check that Bin
(
3
,
odd
)
∼
1
+
2
·
Bin
(
1
,
)
and Bin
(
2
,
odd
)
∼
3
4
)
1
2
)
Bin
(
1
,
1
)
,aswellasBin
(
3
,
even
)
∼
2
·
Bin
(
1
,
and Bin
(
2
,
even
)
∼
2
·
Bin
(
1
,
.
Corollary 2.
E has the distribution of a mixture of a sum of a scalar and a sum of
independent Binomials.
Having this corollary, we can then apply a well known result of Hoeffding [
8
].
Theorem 5 (Hoeffding).
If X
p
1
,
X
p
2
,...,
X
p
are independent Bernoulli trials with
,
,...,
parameters p
1
p
2
p
respectively, then
i
=
1
X
p
i
≤
c
]
≥
P
[
b
≤
Bin
(
,
p
)
≤
c
]
,
when
0
≤
b
≤
p
≤
c
≤ ,
P
[
b
≤
1
∑
i
=
1
p
i
.
where p
=
Recall that we are interested in a lower bound on the median of the independent
sum
E
t
i
=
t
i
=
∼
∑
∼
∑
(
,
)
1
E
i
1
Bin
d
i
. We know that
E
is a mixture of independent
sums of Bin
, which are (rescaled) biased coins. We finish the
proof of Theorem
2
by proving that every particular independent sum of this mixture
has a median that is
(
2
,
)
and Bin
(
3
,
)
d
−
2
≥
. Suppose that we have an independent sum,
Ξ
, consist-
2
ing of
r
,
z
,
a
,
w
∈{
0
,
1
,
2
,...}
terms from Bin
(
3
,
odd
)
,Bin
(
3
,
even
)
,Bin
(
2
,
even
)
and
Bin
(
2
,
odd
)
respectively. Notice that 3
r
+
3
z
+
2
a
+
2
w
=
d
.
d
−
2
2
Lemma 15.
Amedianof
Ξ
is
≥
.
d
−
1
Proof.
Suppose first that
z
≥
r
. In that case we show that Med
(
Ξ
)
≥
. Denote
2
1
4
)+
1
2
)+
3
4
)
by
Ψ
the independent sum Bin
(
r
,
Bin
(
a
,
Bin
(
z
,
.Then
Ψ
=
j
if and only
if
Ξ
=
r
+
2
j
+
w
. Thus a median of
Ξ
can be estimated through a median of
Ψ
and
d
−
1
r
+
2
a
+
3
z
−
1
so a median of
Ξ
is
≥
if and only if a median of
Ψ
is
≥
. We apply
z
r
+
2
a
+
3
z
,
=
2
4
1
Hoeffding's result with
p
=
r
+
a
+
z
and
c
=
r
+
a
+
z
,
b
=
r
+
a
+
4
r
+
2
a
+
3
z
−
1
. This gives that
4
r
+
2
a
+
3
z
−
1
r
+
2
a
+
3
z
−
1
P
[
Ψ
≥
]
≥
P
[
Bin
(
r
+
a
+
z
,
p
)
≥
]
4
4
r
+
2
a
+
3
z
≥
P
[
Bin
(
r
+
a
+
z
,
p
)
≥
]
.
4
r
+
2
a
+
3
z
1
2
.
Hence the lemma will follow once we prove that
P
[
Bin
(
r
+
a
+
z
,
p
)
≥
]
≥
4
r
+
2
a
+
3
z
1
2
Note that the mean of Bin
(
r
+
a
+
z
,
p
)
equals
.Now,if
z
≥
r
then
p
≥
and
4
1
thus Bin
(
r
+
a
+
z
,
p
)
is stochastically larger than Bin
(
r
+
a
+
z
,
2
)
. This means that
1
2
(
+
+
,
)
(
+
+
,
)
a median of Bin
r
a
z
p
is bigger than or equal to a median of Bin
r
a
z
.
Search WWH ::
Custom Search