1
$\begingroup$

Let $Q(\epsilon, n, p)$ be the $\epsilon$-quantile of a binomially distributed random variable with $n$ trials and success probability $p$. I am interested in the following question: Fix $0 < \epsilon < \frac{1}{2}$ and $0<\delta<p$. Then is it true that for some $n^\star$ the quantiles are equal: \begin{eqnarray} Q\left(\epsilon, n^\star, p - \delta\right) = Q\left(1-\epsilon, n^\star, p\right)? \end{eqnarray}

I have done a number of numerical solutions in R and have been unable to find an instance where such an $n^\star$ does not exist. I am interested if anyone has any intuition for why this equation might always have a solution.

$\endgroup$
3
  • $\begingroup$ Could you show a numerical example and perhaps the R code to demonstrate what you are saying? $\endgroup$
    – Henry
    Nov 29, 2014 at 0:04
  • $\begingroup$ Here is some R Code: minimum.bits <- function(n, p, delta, epsilon) { for (k in 1:n) { ## For each value of k, test if it satisfies the required conditions. if (qbinom(1 - epsilon, k, p - delta) == qbinom(epsilon, k, p)) { ## If it does, do not bother continuing. break } } ## Using the selected k, compute the necessary threshold. C <- qbinom(1 - epsilon, k, p - delta) ## Return the number of bits and the threshold. return(data.frame(C = C, k = k)) } $\endgroup$ Nov 29, 2014 at 1:10
  • $\begingroup$ In your code you are actually testing $Q\left(1-\epsilon, n, p - \delta\right)$ against $Q\left(\epsilon, n, p\right)$ while your question asks about equality between $Q\left(\epsilon, n, p - \delta\right)$ and $Q\left(1-\epsilon, n, p\right)$. I think you intended the version in your code. $\endgroup$
    – Henry
    Nov 29, 2014 at 10:56

1 Answer 1

1
$\begingroup$

In your code you are actually testing $Q\left(1-\epsilon, n, p - \delta\right)$ against $Q\left(\epsilon, n, p\right)$ while your question asks about equality between $Q\left(\epsilon, n, p - \delta\right)$ and $Q\left(1-\epsilon, n, p\right)$. I think you intended the version in your code.

For $\epsilon \ge p-\delta$ you will have $Q\left(1-\epsilon, 1, p - \delta\right) = 0 = Q\left(\epsilon, 1, p\right)$ which provides an immediate solution of $n=1$. Otherwise, with $\epsilon \lt p-\delta$, you will have $Q\left(1-\epsilon, 1, p - \delta\right) = 1$ but $Q\left(\epsilon, 1, p\right)=0$.

For very large $n$ you have $Q\left(1-\epsilon, n, p - \delta\right) \approx n(p-\delta)$ and $Q\left(\epsilon, n, p\right) \approx np$ thanks to the law of large numbers, so somewhere the difference between them switches from non-negative to negative.

$Q\left(\alpha, n, r\right)$ is a weakly increasing function of $n$ since $Q\left(\alpha, n+1, r\right)-Q\left(\alpha, n, r\right)$ is $0$ or $1$. This means that as $n$ increases by $1$, then the change in $Q\left(1-\epsilon, n, p - \delta\right) - Q\left(\epsilon, n, p\right)$ is one of $-1,0,+1$ as one or other can change by $1$ or both can or neither can.

So the difference $Q\left(1-\epsilon, n, p - \delta\right) - Q\left(\epsilon, n, p\right)$ starts at $0$ or $+1$ but ends up negative and takes unit steps when it changes, meaning that for some value(s) of $n$ it must be zero and $Q\left(1-\epsilon, n, p - \delta\right) = Q\left(\epsilon, n, p\right)$.

$\endgroup$
2
  • $\begingroup$ Thanks -- very helpful. I believe in the second paragraph you switched your cases for $\epsilon$. $\endgroup$ Nov 30, 2014 at 23:13
  • $\begingroup$ @user1936768: I suspect you are correct - I will edit $\endgroup$
    – Henry
    Dec 1, 2014 at 7:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .