Information Technology Reference
In-Depth Information
edges such that
t
be the number of vertices of even in-degree in each graph after a toss. The
E
i
's are
independent random variables and the total number of even in-degree vertices is
given by
E
d
i
=
d
and
m
i
=
m
. Recall that we assume
d
=
m
.Let
E
i
,
1
≤
i
≤
∑
∑
E
t
. Now, the distribution of each
E
i
is given by the previous
theorem and thus
E
is the sum of independent Bin
=
E
1
+
···
+
random variables. Note
that if these were pure Binomials instead of half-Binomials, then we would be done.
In that case
E
would also be Binomial whose median is known. The problem is that
we have a sum of independent half-Binomials and it is not immediately clear how to
analyze a sum like Bin
(
d
i
,
)
(
,
)+
(
,
)
7
odd
Bin
6
even
. We analyze such sums by breaking
down each term of the sum, Bin
(
s
,
)
,intoasumofBin
(
2
,
)
and Bin
(
3
,
)
.More
specifically, Bin
will be a convex combination (mixture) of such sums. Recall
that a mixture of random variables
Z
i
is defined as a random selection of one of the
Z
i
according to a probability distribution on the index set of
i
's. It is clear that if all
these
Z
i
have a median that is
(
s
,
)
≥
μ
, then also the mixture has a median
≥
μ
.
Lemma 13.
For any s
≥
2
,lets
=
s
1
+
s
2
+
···
+
s
l
be a partition of s into s
i
=
2
or
s
i
=
3
, with at most one part equal to
3
in case s is odd. Then Bin
(
s
,
)
is a mixture
of sums Bin
(
s
1
,
)+
···
+
Bin
(
s
l
,
)
, where the parities of all these half-Binomials,
Bin
(
s
i
,
)
, add up to the given parity of Bin
(
s
,
)
.
(
,
)
Proof.
Suppose we want to decompose a Bin
random variable. The other
case is similar. We get an outcome of such a half-Binomial by tossing
s
s
even
1 indepen-
dent coins and add a deterministic one to fix the parity, i.e., by tossing
s
even-sum
0
−
s
l
,whereall
s
i
are equal
to 2, except possibly one that is equal to 3, and then toss
l
even-sum 0
/
1 fair coins. This is equivalent to partition
s
into
s
1
,...,
/
1 fair coins,
assign the parity of the
j
-th coin,
j
=
1
,...,
l
,to
s
j
and then this parity to Bin
(
s
j
,
)
.
To be more precise, suppose that
Y
j
∈{
even
,
odd
}
is the parity of the
j
-th coin. Then
for each
j
=
1
,...,
l
,toss
s
j
Y
j
-sum coins to get an outcome from Bin
(
s
j
,
Y
j
)
.Then
l
j
l
j
the parity of
1
Y
j
is even and thus the independent sum
1
Bin
(
s
j
,
Y
j
)
has as
∑
∑
=
=
even number of terms of the form Bin
(
s
j
,
odd
)
which means that it is an outcome
from Bin
.
To see that this is equivalent, notice that the probability of each particular out-
come equals
(
s
,
even
)
1
2
l
−
1
1
2
s
1
−
1
1
2
s
2
−
1
1
2
s
l
−
1
1
·
·
···
=
2
s
−
1
, which is exactly the probability of
(
,
)
each particular outcome from Bin
s
even
. So it remains to prove that the number
of outcomes for which Bin
(
s
,
even
)=
k
,forsomeeven
k
, equals the number of out-
i
comes for which
1
Bin
(
s
i
,
Y
i
)=
k
, given the parities
Y
=(
Y
1
,...,
Y
l
)
. But this is
∑
=
immediate. Every outcome of Bin
(
s
,
even
)
, that is, every toss of
s
even-sum 0
/
1fair
coins with
k
1's gives rise to a vector of parities
Y
=(
Y
1
,...,
Y
l
)
such that the parity
l
j
i
of
1
Y
j
is even,
1
Bin
(
s
i
,
Y
i
)=
k
and vice versa.
∑
∑
=
=
If we apply the last Lemma to each
E
i
∼
Bin
(
d
i
,
)
,
i
=
1
,...,
t
we get the fol-
lowing.
Corollary 1.
E is a mixture of sums of independent half-Binomials Bin
(
2
,
)
and
(
,
)
Bin
3
.
The reason to partition each
d
i
into sums of 2's and at most one 3 is the following.
Search WWH ::
Custom Search