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](https://en.wikipedia.org/wiki/Cram%C3%A9r%E2%80%93Rao_bound#Scalar_unbiased_case), 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](http://projecteuclid.org/euclid.aoms/1177730439). 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?



Cramér-Rao bound for randomized estimator
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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Law_of_total_variance#General_variance_decomposition_applicable_to_dynamic_systems) 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.


