Mathematics Asked on November 2, 2021
In the paper "The Complexity of Parallel Search" (Karp, Upfal and Wigderson; Journal of Computer and System Sciences 36, 225 – 253, 1988) in the appendix, the authors present the iteration procedure
m = n; t = 0;
while m > 0 do
begin m = m - X(m); t = t+1 end
T=t;
where $X(m)$ is a random variable over ${0,dots,m}$ and $T$ is the random variable which represents the number of iterations executed in the above procedure, depending on $X(m)$.
They give the following theorem:
Theorem Suppose $operatorname{E}[X(m)]geq g(m)$ where $g:mathbb R^+tomathbb R^+$ is monotone nondecreasing. Then $operatorname{E}[T]leqint_1^nfrac{1}{g(x)}dx$ and for every $a>0$:
$$operatorname{Pr}left[T>(a+1)int_1^nfrac{1}{g(x)}dxright]<e^{-a}$$
They give no proof but refer to a forthcoming publication. However, I was not able to find any proof of this. The second part of the theorem could be obtained, I think, from Corollary 4.3 of "Probabilistic Recurrence Relations" (Karp; Journal of the ACM, 41 (6), 1136 – 1150, 1994).
However, I can not really wrap my head around why we have
$$operatorname{E}[T]leqint_1^nfrac{1}{g(x)}dx.$$
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP