www-ai.cs.tu-dortmund.de/LEHRE/SEMINARE/SS09/AKTARBEITENDESDM/LITERATUR/tkde08_distributedProductKargupta.pdf
Hastings algorithm for random walk.
5
0 50 100 150 0
1
2
3
4
5
6
7
8x 10 −3
Node Degree
P ro
ba bi
lit y
of S
el ec
tio n
(a) Simple Random Walk
0 50 100 150 0
0.2
0.4
0.6
0.8
1
1.2
1.4x 10 −3
Node Degree
P [...] the true mean and the mean of the population is greater than 0.5 is less than by 0.05 (i.e. Pr (Qm − E[X] ≥ 0.5) ≤ 0.05 andPr (E[X]−Qm ≥ 0.5) ≤ 0.05). Note that, as bothǫ and q′ decreases,m increases.
In [...] =⇒ m ≥
(b− a)2ln (
1 q′
)
2ǫ2 . (2)
Note that0 < q′ < 1, 0 < ǫ < 1 and both are parameters determined by the user. For example, ifb− a = 5, q′ = 0.05 andǫ = 0.5, we havem ≥ 150. In other words, if we take …