Let $p\in(0,1)$ and $n$ be a finite positive integer. How to compute the following sum \begin{equation} \frac{1}{(\frac{1}{n}-p)^{2}}+\frac{1}{(\frac{2}{n}-p)^{2}}+\ldots+\frac{1}{(\frac{n-1}{n}-p)^{2}}+\frac{1}{(1-p)^{2}}? \end{equation}

I tried substitution and expanding the denominator terms, but it doesn't seem to work. Any hints?

Edit $1$:

So here is why I want to compute this sum. Let $Z\sim\text{Bin}(n,p)$. I want to compute $\mathbb{E}|\frac{Z}{n}-p|$. Since $U:=|\frac{Z}{n}-p|$ is a non negative random variable taking values in $A:=\{p,|\frac{1}{n}-p|,\ldots,1-p\}$, I have \begin{align} \mathbb{E}|\frac{Z}{n}-p|&=\sum_{t\in A}\mathbb{P}(U>t)\\ &\le \text{var}(U)\sum_{t\in A}\frac{1}{t^{2}}\quad (\text{Chebyshev's inequality}) \end{align} This summation is what appears above. Another way could be to use an exponential bound in the second step.

Edit $2$

So a simple upper bound is the following: \begin{align} \mathbb{E}|\frac{Z}{n}-p|&\le \frac{1}{n}\sqrt{\mathbb{E}(Z-np)^{2}}\\ &=\frac{\sqrt{p(1-p)}}{\sqrt{n}}, \end{align} which would be okay for my calculation.

Any techniques to compute the sum in question are still welcome.

  • $\begingroup$ I don't know if this "simplifies".. are you trying to do a riemann sum? $\endgroup$ – Akababa Feb 25 '18 at 6:44
  • $\begingroup$ Yes. An upper bound on this would also do.. $\endgroup$ – nemo Feb 25 '18 at 7:11
  • 1
    $\begingroup$ If $p=k/n+\epsilon$ the sum becomes unbounded $\endgroup$ – Akababa Feb 25 '18 at 7:27
  • 1
    $\begingroup$ If $p=\frac12$ then it seems $\mathbb{E}\Big|\frac{Z}{n}-p\Big| = {n-1 \choose [(n-1)/2]}2^{-n}$ but surprisingly this is not a bound for all $p$ given even $n$. Your simple upper bound of $\frac{\sqrt{p(1-p)}}{\sqrt{n}}$ looks good, as for large $n$ and for $p$ not close to $0$ it seems to be only about $\sqrt{\frac{\pi}2} \approx 1.25$ times too high and that more than covers the extreme cases $\endgroup$ – Henry Feb 25 '18 at 10:33
  • 1
    $\begingroup$ Mathematica provides the exact result $$\sum_{k=1}^n\frac{1}{(k/n-p)^2}=n^2 \psi ^{(1)}(1-n p)-n^2 \psi ^{(1)}(-p n+n+1)$$, in terms of a polygamma function. $\endgroup$ – Pierpaolo Vivo Feb 25 '18 at 12:49

Denote by $\lfloor{x}\rfloor$ the largest integer smaller than $x$. It seems to me that your expectation can be computed exactly without too much effort: $$ \sum_{k=0}^n {n\choose k}p^k (1-p)^{n-k}\Big|\frac{k}{n}-p\Big|=\frac{1}{n}\left[\sum_{k=\lfloor{np}\rfloor+1}^n {n\choose k}p^k (1-p)^{n-k}(k-np)+\sum_{k=0}^{\lfloor{np}\rfloor} {n\choose k}p^k (1-p)^{n-k}(np-k)\right] $$ $$ =\boxed{\frac{2 (\lfloor{np}\rfloor+1) p^{\lfloor{np}\rfloor+1} \binom{n}{\lfloor{np}\rfloor+1} (1-p)^{n-\lfloor{np}\rfloor}}{n}}\ . $$

  • $\begingroup$ Indeed..thanks for your answer! $\endgroup$ – nemo Feb 25 '18 at 15:17

Treating this as a Riemann approximation to $n\int_0^1 dx/(x-p)^2$ and ignoring the singularity at $x=p$ gives (doing it mentally) $n/(p(1-p))$.


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.