Simple recursion question While reading these lecture notes: http://www.cc.gatech.edu/%7Evigoda/7530-Spring10/Kargers-MinCut.pdf, there is an recurrance relation:
$$
{\rm P}\left(n\right) \geq
1 - \left[1 - {1 \over 2}\,{\rm P}\left(\lfloor{n \over \sqrt{\,2\,}\,}\rfloor + 1\right)\right]^{2}
$$
where ${\rm P}(n)$ is some constant (probability) for small enough $n$,
which is solved to
$\displaystyle{{\rm P}\left(n\right)=\Omega\left(1 \over \log\left(n\right)\right)}$
I'm not sure how this is derived, anybody give me a clue?
 A: Variable sub to make things a bit easier:
$$\begin{align}
Q(m) & = P\left(\sqrt 2 ^ m\right)\\
& \approx 1 - \left(1 - k\, Q(m - 1)\right)^2 \text{ for } k = {1\over 2}, 0 \le Q \le 1 \\
\end{align}$$
So I did a little research on this type of recursion, apparently it is called a "quadratic map".  And apparently these are pretty hard, and usually unsolvable.  Change of variables again to $R(m) = k - k^2\,Q(m)$, so $Q(m) = \frac{k - R(m)}{k^2}$:
$$\frac{k - R(m)}{k^2} = 1 - \left(1 - \frac{k - R(m-1)}{k^2}\right)^2$$
$$R(m) = R(m - 1)^2 + c$$
$c = \frac 14$ and $\frac 14 \le R(m) \le \frac 12$ and it is increasing towards $\frac 12$.  (You might notice that this is a special case of the Mandlebrot Fractal recurrence, fun how unexpected acquaintances are always showing up in math problems).
The best I can do for finding the asymptotic behavior myself (abusing notation a lot) is $P \in \Omega\left(\frac {1} {\log n}\right) \equiv Q \in \left(\frac {1} {n^{\Omega(1)}}\right) \equiv R \in \left(-n^{-O(1)}\right)$, finding a bound on $R$ like $0.5 - \frac{z_1}{m^y} \le R(m) \le 0.5 - {z_2 \over m^{y+1}}$ for some $z_1$, $z_2$ and $y$ would satisfy the bounds.  Taking $y = 1$:
$$0.5 - \frac{z_1}{m} \le R(m) \le 0.5 - \frac{z_2}{m^2}$$
$$0.5 - \frac{z_1}{m} \le R(m - 1)^2 + 0.25 \le 0.5 - \frac{z_2}{m^2}$$
$$0.5 - \frac{z_1}{m} \le \left(0.5 - \frac{z_1}{m - 1}\right)^2 + 0.25  \land 
\left(0.5 - \frac{z_2}{(m-1)^2}\right)^2 + 0.25   \le 0.5 - \frac{z_2}{m^2}$$
$$0 \le \frac{m(z_1^2 - z_1) +z_1}{m^3 - 2m^2 + m} \land 0 \le \frac{2m^3z_2-m^2z_2^2-5m^2z_2+4mz_2-z_2}{m^6-4m^5+6m^4-4m^3+m^2}$$
Which eventually holds for $z_1 > 1$ and $z_2 > 0$, so the bounds are correct.
It might be worth messaging (or if you are a student, or can fake being a student, visiting) the professor directly.  This could be a simple case of some more well known statistical relation.  I've never had a Gatech prof be less than helpful when asked directly.
