# Concentration bounds for a mixture of a fixed value and a uniform distribution

Suppose we have a mixed random variable $$R= (1-p)X + pU$$, where $$X$$ is just a single value $$X \in [-\pi, \pi]$$, $$0 \leq p \leq 1$$, and $$U \sim \text{Uniform}[-\pi, \pi]$$. I.e. a single trial returns $$X$$ with probability $$p$$, otherwise it returns a sample from $$U$$ with probability $$1-p$$.

I would like to give (preferably two-tailed) concentration bounds for the number of trials needed to estimate $$X$$ to additive accuracy $$\epsilon$$ and confidence $$\delta$$. The parameter $$p$$ is known in advance. If we denote trials $$R_i$$ and use an estimator $$\hat{R} = \frac{1}{n(1-p)} \sum_{i=1}^n R_i$$, then naive application of Hoeffding gives, I think, $$n \geq \frac{2\pi p^2}{\epsilon^2(1-p)^2}\log\frac{1}{\delta},$$

But can a tighter bound be derived?

• I wonder if you mean that $R=(1-\alpha)X+\alpha U$ where $\alpha \sim \text{Bernoulli}(p)$.
– JimB
Commented Jul 16 at 19:09
• Sure, this makes sense. Commented Jul 16 at 21:08
• Just curious: Using the mode of a sample if the mode is unique and zero otherwise is a much, much better estimator of $X$. Is there some reason for the estimator in your question?
– JimB
Commented Jul 16 at 22:44
• You write $\delta$ is the "confidence". Can you clarify a little? Commented Jul 16 at 22:52
• One more comment on the estimator $\hat{R}$: when $n<20$ and $p>1/2$ there can be a large fraction of the estimates being way outside of $[-\pi, \pi]$. This is support of my question as to why that estimator. Is that estimator either being used or proposed to be used for any important decisions?
– JimB
Commented Jul 17 at 3:30

Presuming that "$$\delta$$ is the confidence", as the OP writes, implies that we want a confidence interval that includes $$\delta$$ probability mass.

The estimator is $$\hat X = \frac 1{1-p}\frac 1 n\sum_{i=1}^nR_i \implies S_n \equiv \sum_{i=1}^nR_i = n(1-p) \hat X.$$

The range of $$R_i$$ is

$$R_i \in \left[-\pi,\quad \pi\right].$$

Moreover, $$\hat X$$ is unbiased and hence so is $$S_n$$,

$$E(S_n) = n(1-p)X.$$

We examine the probability (since $$\epsilon$$ is the length and $$\delta$$ the confidence), \begin{align} \delta =\Pr\left(|\hat X - X| \leq \epsilon\right)& =1- \Pr\left(|\hat X - X| \geq \epsilon\right)\\ &= 1- \Pr\left(|n(1-p)\hat X - n(1-p) X| \geq n(1-p)\epsilon\right)\\ &\implies \Pr\left(|S_n - E(S_n)|\geq n(1-p)\epsilon\right) = 1-\delta \end{align}

The left hand side is Hoefding's left-hand side, so

$$1-\delta \leq 2\exp\left\{-\frac {2\epsilon^2\cdot n^2\cdot (1-p)^2}{n\cdot 4\pi^2}\right\},$$

$$n \leq \frac{2\pi^2}{\epsilon^2 (1-p)^2} \log\frac{2}{1-\delta}.$$

We obtained a "should not be greater than" result, rather than a "must be greater than" one. This is what Hoeffding's inequality can give us in this case.

Set $$\epsilon = 0.1$$, $$\delta = 0.9$$ and $$p=0.5$$ to get

$$n\leq 23,653.$$

What would happen if we did $$25,000$$ trials with $$\epsilon$$ and $$p$$ as above?

The right-hand side of Hoeffding would become $$\approx 0.084$$ so we would obtain

$$1-\delta \leq 0.084 \implies \delta \geq 0.916.$$

Namely with this specifics and $$25,000$$ trials, we would obtain confidence higher than we required.

But the result is silent as regards with how small $$n$$ we can get away with. Namely, the specific $$(\epsilon, \delta)$$ pair given $$p$$, could possibly be reached with much smaller $$n$$ than $$23,653$$.

If $$\tilde{X}_n$$ is the estimator that JimB is talking about then for $$\epsilon > 0$$

\begin{align} \delta =\Pr\left(|\tilde{X}_n - X| \geq \epsilon\right) &= \Pr\left(|\tilde{X}_n - X| \geq \epsilon, \text{at least n-1 samps from uniform}\right)\\ &\le \binom{n}{n-1} p^{n-1}(1-p)+ p^n . \end{align}

• Should the probability be exactly $\binom{n}{n-1} p^{n-1}(1-p)+ \binom{n}{n} p^n (1-p)^0=p^{n-1} (n (-p)+n+p)$ rather than $\leq p^{n-1}$?
– JimB
Commented Jul 17 at 2:32
• $\binom{n}{n-1} p^{n-1}(1-p)+ p^n = p^{n-1}(n+p-np)$ Commented Jul 17 at 15:30