Let the function \mathbf{B}(p) return a random number X \sim \operatorname{Bernoulli}(p), and let the function \mathbf{D}(N) return a random number X \sim \operatorname{Discrete} \operatorname{Uniform}(N).
With these two basic functions, we can simulate many complex probabilistic events. For example, suppose we want to generate a random number X according to the following distribution:
\begin{array}{cccc}
\hline
value & 0 & 1 & 2 \\
\operatorname{Pr}[X= value ] & 1 / 4 & 1 / 2 & 1 / 4 \\
\hline
\end{array}
One algorithm that can simulate such a distribution is:
\textbf{Data}: none
\textbf{Result}: a random number with the above distribution
u \leftarrow \mathbf{B}(1 / 2)
v \leftarrow \mathbf{B}(1 / 2)
\textbf{return} \ u+v
Prove that this algorithm accurately returns a random number with the above distribution.