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$
  • $\begingroup$ Could you show a numerical example and perhaps the R code to demonstrate what you are saying? $\endgroup$ – Henry Nov 29 '14 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$ – user1936768 Nov 29 '14 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 '14 at 10:56
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$
  • $\begingroup$ Thanks -- very helpful. I believe in the second paragraph you switched your cases for $\epsilon$. $\endgroup$ – user1936768 Nov 30 '14 at 23:13
  • $\begingroup$ @user1936768: I suspect you are correct - I will edit $\endgroup$ – Henry Dec 1 '14 at 7:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.