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?
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.