Choose X s.t. $\Pr[X \geq k] = 1/k$ I am trying to implement an algorithm to approximate the weight of a Minimum Spanning Tree, as described here (p. 8-10). In the pseudo-code ApproxConnectedComps(G, s), p. 9, there is a passage where they choose a random maximum number of iterations, $X$, such that $\Pr[X \geq k] = 1/k$.
With my rather limited skills in probability, I was trying to work this out, but found myself stumped. The only way I found to solve it was to estimate the number of vertices $k$, and then choose $X$ uniformly random in the range $[1,k]$, which gives $\Pr[X = k] = 1/k$. If I'm not entirely mistaken, this should satisfy the condition stated in the pseudo-code, but it feels.. a bit off. Am I on the right track, or am I missing something?
 A: Generally speaking, $$\Pr[X \ge k] \ne \Pr[X = k],$$ unless $\Pr[X > k] = 0$.  So your use of a uniform distribution does not satisfy the stated criterion.
Let's consider what the condition $$\Pr[X \ge k] = 1/k$$ would imply about an integer-valued random variable $X$.  Clearly, $X \ge 1$, so $X$ is a positive integer.  Then $$\Pr[X = k] = \Pr[X \ge k] - \Pr[X \ge k+1] = \frac{1}{k} - \frac{1}{k+1} = \frac{1}{k(k+1)},$$ and we specifically have $$\begin{align*}
\Pr[X = 1] &= \frac{1}{2}, \\ \Pr[X = 2] &= \frac{1}{6}, \\ \Pr[X = 3] &= \frac{1}{12}, \\ \Pr[X = 4] &= \frac{1}{20}, \end{align*}$$  and so forth.
If the goal is to simulate this random variable--that is to say, create an algorithm that will produce realizations of $X$ that follow this distribution--then one simple method is to generate a continuous uniform random variable $U$ between $0$ and $1$ (e.g., some function like rand()).  Then take the reciprocal of this number to get $1/U$, and round downward to the nearest integer.  So for example, floor(1/rand()) is what you might use on a computer.  This will give you the desired realization of $X$.  I leave it to you as an exercise to show that this actually works.
