Is the probability of getting at least the average number of heads monotone?

91 Views Asked by At

Let $f(n,k)$ be the probability of getting heads at least $n$ times with $nk$ coins that independently show heads with probability $1/k$. For $k$ fixed, is $f(n,k)$ monotone in $n$?

With the central limit theorem it is easy to show that $f(n,k)$ converges to $1/2$ as $n\to\infty$. By experimentation and intuition I expect this convergence to be monotone, but I can not come up with a proof.

2

There are 2 best solutions below

2
On BEST ANSWER

$P(nk+k,\ge(n+1)) = P(nk,\ge(n+1))+\sum_{j=1}^k P(nk,n-j+1)P(k,\ge j)$. Note $P(nk,\ge(n+1)) = P(nk,\ge n)-P(nk,n)$, so suffices to show $P(nk,n) \ge \sum_{j=1}^k P(nk,n-j+1)P(k, \ge j)$. Easy to show $P(nk,n-j+1) \le P(nk,n)$ for each $j$, so suffices to show $\sum_{j=1}^k P(k, \ge j) \le 1$, but LHS is expected number of heads, which is $1$.

2
On

Let $X \sim Bin(nk, 1/k)$ and $F_X$ the CDF of $X$. Let $H_{nk}$ be number of heads in $nk$ tosses. $$f(n,k)=P(H_{nk} \geq n )= 1 -P(H_{nk} \leq n-1 )=1-F_X(n-1)= 1- \sum_{i=0}^{n-1} {nk \choose i}(\frac{1}{k})^i (\frac{k-1}{k})^{nk-i}.$$ This gives an expression for $f(n,k)$. Determine if it is monotone in $n$ (perhaps by induction on $n$).

Inductive hyp $f(n+1,k) > f(n,k) $.

base: $f(2,k) = 1-(2k\frac{1}{k}(\frac{k-1}{k})^{2k-1}+(\frac{k-1}{k})^{2k})$ $ = 1-(\frac{k-1}{k})^{2k}(2\frac{1}{k-1}+\frac{k-1}{k-1})$ $= 1-(\frac{k-1}{k})^{2k}(\frac{k+1}{k-1}) =1-(k+1)\frac{(k-1)^{2k-1}}{k^{2k}}$ $ > f(1,k)= 1-(\frac{k-1}{k})^{k} $.

since $(k+1)(k-1)^{k-1}/k^k < 1 $ for $k\geq 2$.

Now try to do the inductive step.