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?

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.
• There is a simpler way. Marginalize out the $y$ vector. You then have a generative model. $p \rightarrow x \rightarrow \hat \theta$. The Cramer-Rao, which be though of as a data processing inequality, applies and gives you your result. (also, IMO it's best to apply CRao to all estimators, even the biased ones, but with the corrected formula) – Guillaume Dehaene Aug 10 '15 at 8:41