6

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^+\to\mathbb R^+$ is monotone nondecreasing. Then $\operatorname{E}[T]\leq\int_1^n\frac{1}{g(x)}dx$ and for every $a>0$:

$$\operatorname{Pr}\left[T>(a+1)\int_1^n\frac{1}{g(x)}dx\right]<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]\leq\int_1^n\frac{1}{g(x)}dx.$$

Daniele Tampieri
  • 9,727
blub
  • 4,794
  • 3
    It seems to me that if you let $P(X(m)=1)=1$, and $g(m)=1$, then $E[T]=n$, but the integral evaluates to $n-1$. – Joe Jul 01 '20 at 11:00
  • @Joe Indeed. However, do you have some intuitive reasons for why some inequality like this should hold, modulo some modifications to the integral. – blub Jul 01 '20 at 11:18
  • Could you express $T$ relatively to $X$? – EDX Jul 01 '20 at 11:36
  • @EDX I tried but I was not successful. – blub Jul 01 '20 at 11:38
  • Hint : what about finding expression $P(T=k)$ in function of $X$? Or if your preferabout writing the definition of $T$ mathematically speaking? Showing $E(T) $ exists first. – EDX Jul 01 '20 at 12:19
  • @EDX How could you express $T$ in terms of $X$ formally? – blub Jul 01 '20 at 12:26
  • I’m not sure if an inequality like this should hold, but perhaps some intuition why it might could come from replacing the integral with a sum from 1 to $n$. If for each $i$ from 1 to $n$ the expected value (and $g$) was 1, then the sum would be $n$. If the expected value (and $g$) was 1/2, the sum would be $2n$. Loosely speaking this seems to match expectations for $E[T]$ (no pun intended). – Joe Jul 01 '20 at 14:00
  • Define $X_1=X(n)$ then for each $i$ $X_{i+1}=X(X(i))$.

    Then we can define $T$ as follow :

    $$ T(\omega)= \min{p \in \mathbb{N}, \sum_{i=1}^p X_i(\omega)=n} $$

     – EDX Jul 01 '20 at 15:50
  • @EDX With X(X(i)), you mean the variable $X(k)$ with $X(i)=k$? Or did you mean to write $X_{i+1}=X\circ X_{i}$ where $\circ$ is composition? As a second question, shouldn't it be rather $\sum_{i=1}^pX_i(\omega)\geq n$? – blub Jul 01 '20 at 18:08
  • @EDX Also, I don't quite see how you can use this to show the desired inequality ... Maybe you can formulate an answer outlining some details. – blub Jul 01 '20 at 18:13
  • @EDX, for $t=0$ we take $m = n - X(n)$, but for $t=1$ we take $m = [n - X(n)] - X([n - X(n)])$, right? So we’re not taking $X(X(n))$. – Joe Jul 01 '20 at 19:27
  • Yes absolutely. It must be corrected into $X_{i+1}=X_i-X(X_i).$ where I mean the composition $\circ$ here. And no we want the equality because its gives us the time when it ends – EDX Jul 01 '20 at 19:45
  • I think there are more hypotheses needed. If $X(m)$ is deterministically $m$ then $T$ is infinite. – D. Ungaretti Jul 10 '20 at 16:09
  • @Daniel if $P{X(m) = m} = 1$ then $P{T = 1} = 1$. However if $P{X(m) = 0} = 1$ then $P{T = +\infty} = 1$. But in this case $g(m) \le 0 = \mathcal{E} X(m)$, i. e. $g(m) = 0$ so the integral is also infinite. – Smylic Jul 13 '20 at 10:59
  • It is not helpful to think of $ g $ as a function on the reals. We only ever care about its values on the integers. I would indeed conjecture $ \mathbb{E}[T] \leq \sum_{j=1}^m{\frac{1}{g(j)}} $. – Jake Mirra Jul 18 '20 at 13:15

0 Answers0