# Computing the sum $\frac{1}{(\frac{1}{n}-p)^{2}}+\frac{1}{(\frac{2}{n}-p)^{2}}+\ldots+\frac{1}{(1-p)^{2}}$

Let $p\in(0,1)$ and $n$ be a finite positive integer. How to compute the following sum $$\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}}?$$

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.

• I don't know if this "simplifies".. are you trying to do a riemann sum? – Akababa Feb 25 '18 at 6:44
• Yes. An upper bound on this would also do.. – nemo Feb 25 '18 at 7:11
• If $p=k/n+\epsilon$ the sum becomes unbounded – Akababa Feb 25 '18 at 7:27
• 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 – Henry Feb 25 '18 at 10:33
• 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. – 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}}\ .$$
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))$.