<p>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.</p>

<p>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.</p>

<blockquote>
  <p><strong>Average Cost:</strong> Given a probability distribution $d$ on $\mathcal{I}$, the <em>average cost</em> of an algorithm $A\in \mathcal{A}_0$ is $C(A,d)=\sum_{x\in\mathcal{I}} d(x)\cdot r(A,x)$.</p>
  
  <p><strong>Distributional Complexity:</strong> 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)$.</p>
  
  <p><strong>$\lambda$-tolerance:</strong> 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$.</p>
  
  <p><strong>Expected Cost:</strong> For a randomized algorithm $R$, let $q$ be a probability distribution that is $\lambda$-tolerant on $\mathcal{A}_0$. The <em>expected cost</em> of $R$ for a given input $x$ is $E(R,x)=\sum_{A\in \mathcal{A}_0} q(A)\cdot r(A,x)$.</p>
  
  <p><strong>Randomized Complexity:</strong> 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)$.</p>
</blockquote>

<p>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$) </p>

<blockquote>
  <p><strong>Yao's Minimax Principle for Montecarlo Algorithms</strong> \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]$.</p>
</blockquote>

<p>I will follow an approach given by <a href="http://dl.acm.org/citation.cfm?doid=22145.22151" rel="nofollow noreferrer">Fich, Meyer auf der Heide, Ragde and Wigderson</a> (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}$</p>

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

<p>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</p>

<p>\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*}</p>

<p>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}</p>

<p>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.</p>

CC BY-SA 3.0
2012-10-11T02:21:16.237Z
Is there a short explanation for where the factor of 2 comes from?
Robin Kothari
CC BY-SA 3.0
2012-10-11T08:25:16.533Z
in short, it comes from the definition of $\beta(2\lambda)$. The summation in the definition divided by 2 is at most $\lambda$.
Marcos Villagra
CC BY-SA 3.0
2012-10-11T16:39:18.723Z
something seems strange to me. by definition, $\max_{A \in \beta(2\lambda))} \left\{\frac{1}{2} \sum_{x \in \mathcal{I}}{d(x), \epsilon(A,x)}\right\} \leq \lambda$ so why the min?
Sasho Nikolov
CC BY-SA 3.0
2012-10-11T16:40:43.370Z
and i don't understand the last sentence. how did you make an entire argument about $\epsilon$ and then replaced it with $r$?
Sasho Nikolov
CC BY-SA 3.0
2012-10-12T04:43:01.217Z
regarding your first question, I added more details.
Marcos Villagra
CC BY-SA 3.0
2012-10-12T04:58:17.820Z
regarding your second question, I agree that its extremely hand-wavy. First, $\max_{x\in \mathcal{I}} \left\{\sum_{A\in\beta(2\lambda)} q(A)\cdot r(A,x)\right\} \geq \max_{x\in \mathcal{I}} \left\{\sum_{A\in\beta(2\lambda)} q(A)\cdot \epsilon(A,x)\right\}$, and the same for the right side. Then, by Claim 1 (i.e., doing computations similar to the 2 sets of inequalities above ) $\max_{x\in \mathcal{I}} \left\{\sum_{A\in\mathcal{A}_0} q(A)\cdot r(A,x)\right\} \geq \frac{1}{2} \min_{A\in\beta(2\lambda)} \left\{\sum_{x\in \mathcal{I}} d(x)\cdot r(A,x)\right\}$
Marcos Villagra
CC BY-SA 3.0
2012-10-12T04:58:37.790Z
Now, I could have directly argue without recurring to $\epsilon$ like $\max_{x\in \mathcal{I}} \left\{\sum_{A\in\mathcal{A}_0} q(A)\cdot r(A,x)\right\} \geq \min_{A\in\beta(2\lambda)} \left\{\sum_{x\in \mathcal{I}} d(x)\cdot r(A,x)\right\}\geq \frac{1}{2} \min_{A\in\beta(2\lambda)} \left\{\sum_{x\in \mathcal{I}} d(x)\cdot r(A,x)\right\}$. However, I wanted to give a good excuse as to why is 1/2 and not (say) 2/3. If it were 2/3 it would violate the case when we have $\epsilon$ instead of $r$.
Marcos Villagra
CC BY-SA 3.0
2012-10-13T03:14:05.973Z
I still don't understand your answer to my first question. Your derivation is ok, but it is also true that the fact holds quite trivially if you replace the min with a max.
Sasho Nikolov
CC BY-SA 3.0
2012-10-13T03:18:51.993Z
I like your thorough notation, but I think you're complicating this a bit too much. All you need to notice is that the $q$-measure of $\beta(2\lambda)$ is at least 1/2 by Markov's inequality.
Sasho Nikolov
CC BY-SA 3.0
2012-10-10T04:50:33.833Z
2017-12-12T09:31:11.850Z
2017-12-12T09:31:11.850Z
Marcos Villagra
<p>This is just an extended comment on Marcos's answer, using his notation. I am not quite able to follow the details of his argument, and the one below is pretty short and easy.</p>

<p>By averaging, 
$$\sum_A{q(A)\sum_x{d(x)\epsilon(A, x)}} = \sum_x{d(x)\sum_A{q(A)\epsilon(A, x)}} \leq \lambda.$$ </p>

<p>The fact above and Markov's inequality imply $\sum_{A \in \beta(2\lambda)}{q(A)} \geq 1/2$. </p>

<p>So we get:</p>

<p>\begin{align*}
\max_x \sum_A{q(A)r(A,x)} &amp;\geq \sum_x{d(x)\sum_A{q(A)r(A, x)}}\\
&amp;= \sum_A{q(A)\sum_x{d(x)r(A, x)}}\\
&amp;\geq \sum_{A \in \beta(2\lambda)}{q(A)\sum_x{d(x)r(A, x)}}\\
&amp;\geq  \left(\sum_{A \in \beta(2\lambda)}{q(A)}\right) \min_{A \in \beta(2\lambda)}{\sum_x{d(x)r(A, x)}}\\
&amp;\geq \frac{1}{2}\min_{A \in \beta(2\lambda)}{\sum_x{d(x)r(A, x)}}
\end{align*}</p>

CC BY-SA 3.0
2012-10-13T03:32:42.620Z
2012-10-13T04:55:26.463Z
2012-10-13T04:55:26.463Z
Sasho Nikolov
<p>The celebrated <a href="http://en.wikipedia.org/wiki/Yao&#39;s_principle" rel="nofollow noreferrer">Yao's Minimax Principle</a> 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.</p>

<p>Mostly Yao's principle deals with <a href="http://en.wikipedia.org/wiki/Las_Vegas_algorithm" rel="nofollow noreferrer">Las Vegas algorithms</a> only, but it can be generalized to <a href="http://en.wikipedia.org/wiki/Monte_Carlo_algorithm" rel="nofollow noreferrer">Monte Carlo algorithms</a> 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$. </p>

<p>In <a href="http://dx.doi.org/10.1109/SFCS.1977.24" rel="nofollow noreferrer">Yao's original paper</a>, the relation for Monte Carlo algorithms is given at Theorem 3 without proof. Any hint for proving it?</p>

<randomized-algorithms>
Yao's Minimax Principle on Monte Carlo Algorithms
Federico Magallanez
# Yao's Minimax Principle on Monte Carlo Algorithms

(Asked by: username_0 on 2012-01-26)

The celebrated [Yao's Minimax Principle](http://en.wikipedia.org/wiki/Yao's_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](http://en.wikipedia.org/wiki/Las_Vegas_algorithm) only, but it can be generalized to [Monte Carlo algorithms](http://en.wikipedia.org/wiki/Monte_Carlo_algorithm) 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](http://dx.doi.org/10.1109/SFCS.1977.24), the relation for Monte Carlo algorithms is given at Theorem 3 without proof. Any hint for proving it?

**Tags:** randomized-algorithms

---

## 2 answers

### Answer by username_3 on 2012-10-13. Score: 6 | Accepted answer

This is just an extended comment on Marcos's answer, using his notation. I am not quite able to follow the details of his argument, and the one below is pretty short and easy.

By averaging,
$$\sum\_A{q(A)\sum\_x{d(x)\epsilon(A, x)}} = \sum\_x{d(x)\sum\_A{q(A)\epsilon(A, x)}} \leq \lambda.$$

The fact above and Markov's inequality imply $\sum\_{A \in \beta(2\lambda)}{q(A)} \geq 1/2$.

So we get:

\begin{align\*}
\max\_x \sum\_A{q(A)r(A,x)} &\geq \sum\_x{d(x)\sum\_A{q(A)r(A, x)}}\\
&= \sum\_A{q(A)\sum\_x{d(x)r(A, x)}}\\
&\geq \sum\_{A \in \beta(2\lambda)}{q(A)\sum\_x{d(x)r(A, x)}}\\
&\geq \left(\sum\_{A \in \beta(2\lambda)}{q(A)}\right) \min\_{A \in \beta(2\lambda)}{\sum\_x{d(x)r(A, x)}}\\
&\geq \frac{1}{2}\min\_{A \in \beta(2\lambda)}{\sum\_x{d(x)r(A, x)}}
\end{align\*}


---

### Answer by username_1 on 2012-10-10. Score: 8

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](http://dl.acm.org/citation.cfm?doid=22145.22151) (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 &\geq \max\_{x\in \mathcal{I}}\left\{ \sum\_{A\in\mathcal{A}\_0} q(A)\cdot \epsilon(A,x) \right\}\\
&\geq \sum\_{x\in\mathcal{I}} d(x) \sum\_{A\in \mathcal{A}\_0} q(a)\cdot \epsilon(A,x)\\
&= \sum\_{A\in \mathcal{A}\_0} q(a)\sum\_{x\in\mathcal{I}} d(x) \cdot \epsilon(A,x)\\
&\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 &\geq \max\_{x\in \mathcal{I}}\left\{ \sum\_{A\in\mathcal{A}\_0} q(A)\cdot \epsilon(A,x) \right\}\\
&\geq \max\_{x\in \mathcal{I}}\left\{ \sum\_{A\in\beta(2\lambda)} q(A)\cdot \epsilon(A,x) \right\}\\
&\geq \sum\_{x\in\mathcal{I}} d(x) \sum\_{A\in \beta(2\lambda)} q(a)\cdot \epsilon(A,x)\\ &= \sum\_{A\in \beta(2\lambda)} q(a)\sum\_{x\in\mathcal{I}} d(x) \cdot \epsilon(A,x)\\
&\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.

> **Comments:**
> **username_2**: Is there a short explanation for where the factor of 2 comes from?  
> **username_1**: in short, it comes from the definition of $\beta(2\lambda)$. The summation in the definition divided by 2 is at most $\lambda$.  
> **username_3**: something seems strange to me. by definition, $\max_{A \in \beta(2\lambda))} \left\{\frac{1}{2} \sum_{x \in \mathcal{I}}{d(x), \epsilon(A,x)}\right\} \leq \lambda$ so why the min?  
> **username_3**: and i don't understand the last sentence. how did you make an entire argument about $\epsilon$ and then replaced it with $r$?  
> **username_1**: regarding your first question, I added more details.  
> **username_1**: regarding your second question, I agree that its extremely hand-wavy. First, $\max_{x\in \mathcal{I}} \left\{\sum_{A\in\beta(2\lambda)} q(A)\cdot r(A,x)\right\} \geq \max_{x\in \mathcal{I}} \left\{\sum_{A\in\beta(2\lambda)} q(A)\cdot \epsilon(A,x)\right\}$, and the same for the right side. Then, by Claim 1 (i.e., doing computations similar to the 2 sets of inequalities above ) $\max_{x\in \mathcal{I}} \left\{\sum_{A\in\mathcal{A}_0} q(A)\cdot r(A,x)\right\} \geq \frac{1}{2} \min_{A\in\beta(2\lambda)} \left\{\sum_{x\in \mathcal{I}} d(x)\cdot r(A,x)\right\}$  
> **username_1**: Now, I could have directly argue without recurring to $\epsilon$ like $\max_{x\in \mathcal{I}} \left\{\sum_{A\in\mathcal{A}_0} q(A)\cdot r(A,x)\right\} \geq \min_{A\in\beta(2\lambda)} \left\{\sum_{x\in \mathcal{I}} d(x)\cdot r(A,x)\right\}\geq \frac{1}{2} \min_{A\in\beta(2\lambda)} \left\{\sum_{x\in \mathcal{I}} d(x)\cdot r(A,x)\right\}$. However, I wanted to give a good excuse as to why is 1/2 and not (say) 2/3. If it were 2/3 it would violate the case when we have $\epsilon$ instead of $r$.  
> **username_3**: I still don't understand your answer to my first question. Your derivation is ok, but it is also true that the fact holds quite trivially if you replace the min with a max.  
> **username_3**: I like your thorough notation, but I think you're complicating this a bit too much. All you need to notice is that the $q$-measure of $\beta(2\lambda)$ is at least 1/2 by Markov's inequality.  

---

