How to show that this variation of the algorithm (that runs until it finds a solution) still has linear expected running time?

Question

In the last section of chapter 3 (page 57) in Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal, a randomized algorithm is discussed for finding the median of a set $S$ of distinct elements in $O(n)$ time. The algorithm discussed is a Monte Carlo algorithm. As such if we would like to run this variation of algorithm till we find a solution, how do we show that it still has a linear running time?

The Algorithm (source, starts on slide 66, page 53):

Input: A set $S$ of $n$ elements over a totally ordered universe$^{***}$.

Output: The median of set $S$, denoted by $m$.

1. Pick a (multi-)set $R$ of $\lceil n^\frac{3}{4} \rceil$ elements in $S$ chosen independently and uniformly at random with replacement.

2. Sort the set $R$.

3. Let $d$ be the $(\lfloor \frac{1}{2} n^\frac{3}{4} - \sqrt{n} \rfloor)$-th smallest element in sorted set $R$.

4. Let $d$ be the $(\lceil \frac{1}{2} n^\frac{3}{4} + \sqrt{n} \rceil)$-th smallest element in sorted set $R$.

5. By comparing every element in $S$ to $d$ and $u$, compute the set: $$C = \left\{ x \in S : d \leq x \leq u \right\}$$ and the numbers $$\ell_d = |\{x \in S : x < d\}|$$ and the numbers $$\ell_u = |\{x \in S : x > u\}|$$

6. If $\ell_d > \frac{n}{2}$ or $\ell_u > \frac{n}{2}$ then $FAIL$.

7. If $|C| \leq 4n^\frac{3}{4}$ then sort the set $C$, otherwise $FAIL$.

8. Output the $(\lfloor \frac{n}{2} \rfloor - \ell_d + 1)$th element in the sorted order of $C$.

Answer 1

I'm assuming you're referring to this as your source.

Short answer: The algorithm terminates in linear time. This does not mean it identifies a median in linear time.

The text first proves, by Theorem 3.9 on page 54, that the algorithm terminates in linear time.

Then it proves, by Theorem 3.13 on page 57, that the probability of failure is bounded by $n^{-1/4}$.

Then the text mentions (page 57):

By repeating Algorithm 3.1 until it succeeds in finding the median, we can obtain an iterative algorithm that never fails but has a random running time. The samples taken in successive runs of the algorithm are independent, so the success of each run is independent of other runs, and hence the number of runs until success is achieved is a geometric random variable. As an exercise, you may wish to show that this variation of the algorithm (that runs until it finds a solution) still has linear expected running time.

The algorithm merely terminates in linear time, making it a Monte Carlo Algorithm. Although by successive runs and a bound on the probability of failure, we can guarantee a success at some point, making it a Las Vegas Algorithm. This successive trial algorithm is what you would attempt to show has an expected linear running time, by working on the geometric random variable represented by $k$ successive trials with bounded failure probability $n^{-1/4}$.