www-ai.cs.tu-dortmund.de/LEHRE/SEMINARE/SS09/AKTARBEITENDESDM/LITERATUR/tkde08_distributedProductKargupta.pdf
when
m ≥ (b−a)2ln(q′) 2ǫ2
, we have
Pr{Qm − E(X) ≥ ǫ} ≤ q′,
P r{E(X)−Qm ≥ ǫ} ≤ q′. Proof: Following Lemma 4.2, we have
Pr{Qm − E(X) ≥ ǫ} ≤ exp
(
− 2mǫ2
(b− a)2
)
≤ q′.
Therefore,
− 2mǫ2
(b− a)2 ≤ ln (q′) =⇒ [...] (i− 1)× (c− i 2 ) + (j − i)
]
, 1 < i < j < c2−c 2 .
B. Problem definition
Without loss of generality we assume thatA[1] ≥ A[2] ≥ ... ≥ A
[
(i− 1)× (c− i 2 ) + (j − i)
]
≥ ... ≥ A[ c2−c 2 ] is the
non- [...] beQm = 1
m
∑
i xi. Then for anyǫ > 0, we have
Pr{Qm − E(X) ≥ ǫ} ≤ exp
(
− 2mǫ2
(b− a)2
)
,
P r{E(X)−Qm ≥ ǫ} ≤ exp
(
− 2mǫ2
(b− a)2
)
.
Next, we show how the Hoeffding bound can be used to derive an upper …
