Yao's Minimax Principle on Monte Carlo Algorithms The celebrated Yao's Minimax Principle states the relation between distributional complexity and randomized complexity. Let $P$ be a problem with a finite set $\mathcal{X}$ of inputs and a finite set $\mathcal{A}$ of deterministic algorithm to solve $P$.
Also let $\mathcal{D}$ denote the input distribution and let $\mathcal{R}$ denote the probability distribution on $\mathcal{A}$.
Then the principle states
$$\min_{A\in\mathcal{A}}\quad\mathbb{E} cost(A,\mathcal{D}) \leq \max_{x\in\mathcal{X}}\quad\mathbb{E} cost(\mathcal{R},x) \quad\quad\text{for all $\mathcal{D}$ and $\mathcal{R}$}.$$
This proof directly follows from von Neumann's minimax theorem for zero-sum games.

Mostly Yao's principle deals with Las Vegas algorithms only, but it can be generalized to Monte Carlo algorithms as follows.
$$\frac12 \min_{A\in\mathcal{A}}\quad\mathbb{E} cost_{2\epsilon}(A,\mathcal{D}) \leq \max_{x\in\mathcal{X}}\quad\mathbb{E} cost_{\epsilon}(\mathcal{R},x)\quad\quad\text{for all $\mathcal{D}$, $\mathcal{R}$ and $\epsilon\in [0,1/2]$}$$
where $cost_\epsilon(\cdot,\cdot)$ denotes the cost of Monte Carlo algorithms that errs probability at most $\epsilon$. 

In Yao's original paper, the relation for Monte Carlo algorithms is given at Theorem 3 without proof. Any hint for proving it?
I'll give it a try on this. I'm going to use Yao's original notation. This way it will be easier to contrast with his paper and his definitions.

Let $\mathcal{I}$ be a finite set of inputs, and let $\mathcal{A}_0$ be a finite set of deterministic algorithms that may fail to give a correct answer for some inputs. Let also $\epsilon(A,x)=0$ if $A$ gives the correct answer for $x$, and $\epsilon(A,x)=1$ otherwise. Also denote by $r(A,x)$ the number of queries made by $A$ on input $x$, or equivalently, the depth of $A$'s decision tree.


  Average Cost: Given a probability distribution $d$ on $\mathcal{I}$, the average cost of an algorithm $A\in \mathcal{A}_0$ is $C(A,d)=\sum_{x\in\mathcal{I}} d(x)\cdot r(A,x)$.
  
  Distributional Complexity: Let $\lambda\in[0,1]$. For any distribution $d$ on the inputs, let $\beta(\lambda)$ be the subset of $\mathcal{A}_0$ given by $\beta(\lambda)=\{A : A\in \mathcal{A}_0, \sum_{x\in\mathcal{I}} d(x)\cdot \epsilon(A,x)\leq \lambda\}$. The distributional complexity with error $\lambda$ for a computational problem $P$ is defined as $F_{1,\lambda}(P)=\max_{d} \min_{A\in \beta(\lambda)} C(A,d)$.
  
  $\lambda$-tolerance: A distribution $q$ on the family $\mathcal{A}_0$ is $\lambda$-tolerant if $\max_{x\in \mathcal{I}} \sum_{A\in\mathcal{A}_0} q(A)\cdot \epsilon(A,x)\leq \lambda$.
  
  Expected Cost: For a randomized algorithm $R$, let $q$ be a probability distribution that is $\lambda$-tolerant on $\mathcal{A}_0$. The expected cost of $R$ for a given input $x$ is $E(R,x)=\sum_{A\in \mathcal{A}_0} q(A)\cdot r(A,x)$.
  
  Randomized Complexity: Let $\lambda\in[0,1]$. The randomized complexity with error $\lambda$ is $F_{2,\lambda}=\min_R \max_{x\in\mathcal{I}} E(R,x)$.


Now we are ready to go into business. What we want to prove is given a distribution $d$ on the inputs and a randomized algorithm $R$ (i.e., a distribution $q$ on $\mathcal{A}_0$) 


  Yao's Minimax Principle for Montecarlo Algorithms \begin{equation}\max_{x\in\mathcal{I}} E(R,x)\geq \frac{1}{2}\min_{A\in \beta(2\lambda)} C(A,d) \end{equation}
  for $\lambda\in[0,1/2]$.


I will follow an approach given by Fich, Meyer auf der Heide, Ragde and Wigderson (see Lemma 4). Their approach does not yield a characterization for Las Vegas algorithms (only the lower bound), but it is sufficient for our purposes. From their proof, it easy to see that for any $\mathcal{A}_0$ and $\mathcal{I}$

Claim 1. $\max_{x\in \mathcal{I}} E(R,x)\geq \min_{A\in \mathcal{A}_0} C(A,d)$.

To get the correct numbers there, we'll do something similar. Given that the probability distribution $q$ given by the randomized algorithm $R$ is $\lambda$-tolerant on $\mathcal{A}_0$ we have that
\begin{align*}
\lambda &amp;\geq \max_{x\in \mathcal{I}}\left\{ \sum_{A\in\mathcal{A}_0} q(A)\cdot \epsilon(A,x) \right\}\\
  &amp;\geq \sum_{x\in\mathcal{I}} d(x) \sum_{A\in \mathcal{A}_0} q(a)\cdot \epsilon(A,x)\\
  &amp;= \sum_{A\in \mathcal{A}_0} q(a)\sum_{x\in\mathcal{I}} d(x) \cdot \epsilon(A,x)\\
  &amp;\geq \min_{A\in \mathcal{A}_0}\left\{ \sum_{x\in\mathcal{I}} d(x) \cdot \epsilon(A,x) \right\}.
\end{align*}
If we replace the family $\mathcal{A}_0$ with $\beta(2\lambda)$ we see that

\begin{align*}
\lambda &amp;\geq \max_{x\in \mathcal{I}}\left\{ \sum_{A\in\mathcal{A}_0} q(A)\cdot \epsilon(A,x) \right\}\\
     &amp;\geq \max_{x\in \mathcal{I}}\left\{ \sum_{A\in\beta(2\lambda)} q(A)\cdot \epsilon(A,x) \right\}\\
     &amp;\geq \sum_{x\in\mathcal{I}} d(x) \sum_{A\in \beta(2\lambda)} q(a)\cdot \epsilon(A,x)\\ &amp;= \sum_{A\in \beta(2\lambda)} q(a)\sum_{x\in\mathcal{I}} d(x) \cdot \epsilon(A,x)\\
     &amp;\geq \min_{A\in \beta(2\lambda)}\left\{ \frac{1}{2}\sum_{x\in\mathcal{I}} d(x) \cdot \epsilon(A,x) \right\},
\end{align*}

where the second inequality follows because $\beta(2\lambda) \subseteq \mathcal{A}_0$, and the last inequality is given by the definition of $\beta(2\lambda)$ where the summation divided by 2 cannot be greater than $\lambda$. Hence, 
\begin{equation}\max_{x\in \mathcal{I}}\left\{ \sum_{A\in\mathcal{A}_0} q(A)\cdot \epsilon(A,x) \right\}\geq\frac{1}{2} \min_{A\in \beta(2\lambda)}\left\{ \sum_{x\in\mathcal{I}} d(x) \cdot \epsilon(A,x) \right\}. \end{equation}

By noting that $\epsilon$ maps to $\{0,1\}$ and $r$ maps to $\mathbb{N}$ and Claim 1 above, now we can safely replace the function $\epsilon$ in the inequality above by $r(A,x)$ to obtain the desired inequality.