4
$\begingroup$

How to determine a positive value of variable $m$, so that the following formula is maximized.

$$\frac{(1-q)^m}{\sum_{x=m/c}^{m}{\binom{m}{x} (1-q)^{m-x} q^x}}$$

where $1

  • 0
    Is $m>0$? I guess that $02011-04-11
  • 0
    yes... I edit it accordingly2011-04-11

1 Answers 1

6

Le $R_m$ denote the ratio considered, $R^*=\sup_mR_m$ and $r=(1-q)/q$.

If $r\le1$, $R_m\le1$ for every $m\ge0$ and $R_0=1$ hence $R^*=1$. Note that $R_1=r$ hence $R^*>1$ for any $r>1$.

If $r>2^c$, $R_m\to+\infty$ when $m\to+\infty$ hence $R^*=+\infty$.

Using large deviations estimates, one can refine this last result as follows: for any $c>1$, if $r>\varrho(c)$, then $R_m\ge k(r)^{m/c}$ where $k(r)>1$, hence $R^*=+\infty$, with $$ \varrho(c)=c^c/(c-1)^{c-1}. $$ Likewise, if $r<\varrho(c)$, then $R_m=k(r)^{(m/c)+o(m)}$ where $k(r)<1$, hence $R^*$ is finite.

One can guess that, for every $m\ge0$, $R^*=R_m$ for any $r$ in $(\varrho_{m}(c),\varrho_{m+1}(c))$, where $(\varrho_m(c))_{m\ge0}$ is an increasing sequence such that $\varrho_0(c)=0$, $\varrho_1(c)=1$ and $\varrho_m(c)\to\varrho(c)$ when $m\to+\infty$.


Edit Here is a sketch of the large deviations estimate. Let $X$ and $(X_k)$ denote i.i.d. Bernoulli random variables with $P(X=1)=q$ and $P(X=0)=1-q$, and $S_m=X_1+\cdots+X_m$. Then $$ R_m=(1-q)^m/D_m,\qquad D_m=P(S_m\ge m/c). $$ By the law of large numbers, $D_m\to1$ if $q>1/c$ and $D_m\to0$ if $q<1/c$. From now on, we assume that $q<1/c$. Then $D_m$ is geometricaly small in the sense that $D_m\le a(c)^{m/c}$ where $a(c)<1$ can be determined by a standard application of Cramér inequality, as follows.

Let $u>1$. Then $[S_m\ge m/c]=[u ^{S_m}\ge u^{m/c}]=[u ^{S_m-m/c}\ge 1]$ hence $$ D_m\le u^{-m/c}E(u^{S_m})=\left(u^{-1}E(u^{X})^c\right)^{m/c}. $$ This holds for every $u>1$ hence $D_m\le a(c)^{m/c}$ with $$ a(c)=\inf_{u>1}[u^{-1}E(u^{X})^c]=\inf_{u>1}[u^{-1}(qu+1-q)^c]. $$ The infimum is achieved at $u(c)$ which solves the equation $q(c-1)u=1-q$, and $u(c)>1$ for every $11$, that is, as soon as $r>\varrho(c)$.


Second edit Each $\varrho_m(c)$ is the point where $R_m$ replaces $R_{m-1}$ as the maximum. In particular, at $r=\varrho_m(c)$, $R_m=R_{m-1}$. This is equivalent to $\varphi_m(r)=\varphi_{m-1}(r)$, where $$ \varphi_m(r)=\sum_{x=m/c}^m{m\choose x}r^{-x}. $$ For example, for every positive $r$, $\varphi_0(r)=1$ and $\varphi_1(r)=1/r$. One sees that $\varphi_1(r)>\varphi_0(r)$ until $r=1$ where $\varphi_1(r)=\varphi_0(r)$, hence $\varrho_1(c)=1$.

  • 0
    could you explain how to get the refined results? like how the form of $\varrho(c)$ is obtained? thanks.2011-04-12
  • 0
    See edit. $ $ $ $2011-04-12
  • 0
    This estimate of $R_m$ implies that $R_m\to0$ when $m\to+\infty$ (and even, that the convergence to zero is exponentially fast) and this convergence implies that the sequence $(R_m)$ is bounded. The prerequisite here is the behaviour of the sequence $(a^n)$ for a fixed $a$. Any other question?2011-04-13
  • 0
    Appreciate the edit. I am trying to work out $\varrho_m(c)$. Any ideas if there is a closed form for it...2011-04-13
  • 0
    For previous posted question, why $R_m=k(r)^{(m/c)+o(m)}$ when $r<\varrho(c)$, but not $R_m>k(r)^{(m/c)}$ as shown in the proof...2011-04-13
  • 0
    The large deviations upper bound gives in fact the correct exponential behaviour of $D_m$, hence of $R_m$ when $m\to+\infty$.2011-04-13
  • 0
    Appreciated. Any brief reason why $D_m$ is exponential, or how tight the bound is, since I find no textbook talked about tightness of the Chernoff bound (in this case).2011-04-15
  • 0
    Why exponential: Cramér inequality shows the convergence to zero is at least exponential, it could be even faster. But in many cases (and in yours) the convergence is exactly exponential and one gets the value of the exponent like I did. See the explanations on http://en.wikipedia.org/wiki/Large_deviations_theory and the beginning of the paper by Varadhan cited there.2011-04-15
  • 0
    As I found, rate function explains a lot. Thanks!2011-04-18