how to derive the complexity of the randomization solution to the majority element problem
Given an array of length $n$, which is promised to have an element $x$ which appears more than $n/2$ times, the goal is to find $x$. Note that $x$ is unique.

The randomized solution goes as follows:


Choose a random element $y$.
Check whether $y$ appears more than $n/2$ times, in time $O(n)$.
If so, return $y$.
Otherwise, go back to the first step.


Since $x$ occurs more than $n/2$ times, the probability to select it is more than $1/2$. Hence the probability that we didn't choose it in the first $t$ attempts is less than $2^t$.

In order to calculate the expected time complexity, let us calculate the expect number of attempts until $y = x$; the expected time complexity would be that multiplied by $O(n)$.

Let $E_t$ denote the event the we got to the $t$th round, that is, that the first $t-1$ attempts did not result in choosing $y = x$. Let $X_t$ be the indicator variable for $E_t$. The number of rounds is thus $X = \sum_{t=1}^\infty X_t$. Linearity of expectation shows that
$$ \mathbb{E}[X] = \sum_{t=1}^\infty \mathbb{E}[X_t] = \sum_{t=1}^\infty \Pr[E_t]. $$
We get to the $t$th round if we failed to find $x$ in the first $t-1$ rounds, so $\Pr[E_t] &lt; 2^{-(t-1)}$. Therefore
$$
\mathbb{E}[X] &lt; \sum_{t=1}^\infty 2^{-(t-1)} = \sum_{t=0}^\infty 2^{-t} = 2,
$$
using the formula for the sum of a geometric series. We conclude that the expected running time of the algorithm is at most $2 \cdot O(n) = O(n)$.



Another way to compute $\mathbb{E}[X]$ is using geometric random variables. Suppose that $x$ appears in $pn$ of the elements; so $p &gt; 1/2$. The random variables $X$ has distribution $G(p)$, that is, geometric with success probability $p$, and so
$$ \mathbb{E}[X] = \frac{1}{1-p} &lt; \frac{1}{1-1/2} = 2. $$

A more sophisticated way to express this is that $X$ is stochastically dominated by a $G(1/2)$ random variable, and so $\mathbb{E}[X] \leq \mathbb{E}[G(1/2)] = 2$.