Cramér-Rao bound for randomized estimator As is well known, the Cramér-Rao bound (or information inequality) sets a lower bound on the variance of estimators of a parameter.
Consider the case when the parameter is a scalar, the estimator is unbiased, and sample size is fixed. From the Wikipedia, suppose $\theta$ is an unknown (deterministic) parameter which is to be estimated from a vector of (random) measurements $x$, distributed according to some probability density function $f(x;\theta)$. Then the variance of any unbiased estimator $\hat{\theta}$ of $\theta$ is bounded by the reciprocal of the Fisher information. 
My focus is on the case when the measurements $x$ are $n$ i.i.d Bernoulli variables with parameter $p$, and $p$ which is to be estimated from $x$. In this case, the bound becomes
$$
\mathrm{Var}(\hat p) \geq \frac{p(1-p)}{n}.
$$
There's also a sequential version of the Cramér-Rao bound, in the which sample size $n$ is a random stopping time with respect to a sequence of observations $x$. See for example Wolfowitz, 1957. The bound holds with sample size replaced by its expected value $\mathrm E[n]$, under some regularity conditions. So, in the Bernoulli case,
$$
\mathrm{Var}(\hat p) \geq \frac{p(1-p)}{\mathrm E[n]}.
$$
Consider now that, in the sequential Bernoulli case, $\hat p$ is a function not only of the observations $x$, but also of $y$, where $y$ is a set of auxiliary random variables independent of $x$. The estimator is then randomized, in the sense that given $x$ the value of $\hat p$ is still random, by virtue of $y$. The variance of $\hat p$ is defined with respect to both $x$ and $y$.
My question: Does the Cramér-Rao bound hold for randomized estimators? (i.e. when the estimator depends on $y$ in addition to $x$) I'm interested in the Bernoulli case, unbiased estimator; ideally in a sequential estimation setting, but a fixed-size result would also be interesting.
If this hasn't been studied before, or no result is known, could you point me in an appropriate direction to establish a randomized-estimator version of the Cramer-Rao bound?
 A: I think I got an affirmative answer for the fixed-size (i.e. non-sequential) case.
Let $\hat \theta$ be an estimator of the parameter $\theta$. The estimate is obtained as a (deterministic) function of $n$ observations $x_1, \ldots, x_n$ and $m$ auxiliary random variables $y_1, \ldots, y_m$. $\hat \theta$ is a randomized estimator, in the sense that the estimate depends not only on the observations $x_1, \ldots, x_n$ but also on the random variables $y_1, \ldots, y_m$.
Consider first the case $m=1$. From the law of total variance, 
$$
\mathrm{Var}[\hat \theta] = \mathrm E_{y_1}(\mathrm{Var}[\hat \theta \,|\, y_1]) + \mathrm{Var}_{y_1}(\mathrm E[\hat \theta \,|\, y_1]).
$$
The term $\mathrm{Var}[\hat \theta \,|\, y_1]$ is the variance of a deterministic estimator obtained from conditioning on $y_1$; and therefore satisfies the Cramér-Rao bound with respect to the observations $x_1, \ldots, x_n$. Thus $\mathrm E_{y_1}(\mathrm{Var}[\hat \theta \,|\, y_1])$ also satisfies the Cramér-Rao bound.
The second summand on the right-hand side is clearly non-negative. Consequently, $\mathrm{Var}[\hat \theta]$ satisfies the Cramér-Rao bound.
For $m>1$ the reasoning is similar. The formula for the (total) variance now contains more terms. The first is the expected value of the conditional variance, $\mathrm E_{y_1,\ldots,y_m}(\mathrm{Var}[\hat \theta \,|\, y_1,\ldots,y_m])$, for which the standard Cramér-Rao bound applies; and the remaining terms are again non-negative.
