When computing the expected value for a random variable I reached the following series: $$\sum_{i=n}^{\infty}\frac{i}{2^i}$$

I am confident it is convergent, but have no idea how to compute it.

  • $\begingroup$ I have changed the formatting of the title so as to make it take up less vertical space -- this is a policy to ensure that the scarce space on the main page is distributed evenly over the questions. See here for more information. Please take this into consideration for future questions. Thanks in advance. $\endgroup$ – Lord_Farin Oct 19 '13 at 7:46
  • $\begingroup$ @Lord_Farin Thank you. $\endgroup$ – Andrei I Oct 19 '13 at 7:51
  • $\begingroup$ What is your random variable $I$? I'm sure its expected value can be computed without summing such a hard series. $\endgroup$ – bof Oct 19 '13 at 8:00
  • $\begingroup$ It is the expected number of steps to reach $crt.Value = n$ in a random walk. In a random walk you either make a step to left (crt.Value decreases) or to right (crt.Value increases), both directions are with 50% probability. $\endgroup$ – Andrei I Oct 19 '13 at 8:23
  • 1
    $\begingroup$ This is called Arithmetico-geometric series (artofproblemsolving.com/Wiki/index.php/… or en.wikipedia.org/wiki/Arithmetico-geometric_sequence) and it has standard formula for summation $\endgroup$ – lab bhattacharjee Oct 19 '13 at 12:02

There are a few standard tricks that one can use. For example:

Let $\displaystyle f(x) = \sum_{i=n}^\infty i x^{i-1} = \frac{d}{dx} \sum_{i=n}^\infty x^i = \frac{d}{dx} \frac{x^n}{1-x} = \frac{nx^{n-1}(1-x) + x^n }{(1-x)^2}$.

So $\displaystyle \sum_{i=n}^\infty \frac{i}{2^i} = \frac{1}{2} \sum_{i=n}^\infty i \left(\frac{1}{2}\right)^{i-1} = \frac{1}{2} f\left(\frac{1}{2}\right) = \frac{1}{2} \frac{n(1/2)^{n-1} (1/2)+(1/2)^n}{1/4} = \frac{n+1}{2^{n-1}}$.


$$ \sum_{i = n}^{\infty} \frac{i}{2^i}$$ $$\frac{i}{2^i} < 1, \space \forall i \ge 0$$

$$ \lim_{i\to\infty}{\frac{i}{2^i}} \to0$$

And apply ratio test of Convergence

$$ \lim_{n\to\infty}\frac{U_{n+1}}{U_n} = \frac{n\times{2^{n+1}}}{(n+1)\times{2^n}} = \frac{n}{(n+1)}\times 2 = 2 < M$$ Here $M$ is finite positive no. Hence the given series will converge.


We can sum your series by interpreting it as the expectation of a random variable, and then computing that expectation in another way.

Suppose a fair coin is tossed repeatedly until it comes up heads. Let $X$ be the number of tosses, up to and including the first head. Let $I=X[X\ge n]$, i.e., $I=X$ if $X\ge n$, and $I=0$ otherwise. It's easy to see that$$E[I]=\sum_{i=n}^{\infty}\frac i{2^i}$$which is the series you asked about.

Let $Y_i$ be the indicator variable whose value is $1$ if $X\ge i$ and $0$ otherwise. Clearly $E[Y_i]=\dfrac1{2^{i-1}}$, the probability of no heads in the first $i-1$ tosses. Moreover, it's easy to see that$$I=nY_n+\sum_{i=n+1}^{\infty}Y_i,$$whence$$E[I]=nE[Y_n]+\sum_{i=n+1}^{\infty}E[Y_i]=\frac n{2^{n-1}}+\sum_{i=n+1}^{\infty}\frac1{2^{i-1}}=\frac n{2^{n-1}}+\frac1{2^{n-1}}=\frac{n+1}{2^{n-1}}.$$

Edit. $n$ is a fixed natural number; $X$ is a certain discrete random variable whose values are nonnegative integers.

For each $i\in\mathbb N$, the random variable $Y_i$ is a function of $X$, namely, $Y_i$ takes the value $0$ when $X\lt i$, the value $1$ when $X\ge i$. In terms of the discrete form of the Heaviside step function, $Y_i=H[X-i]$; in the Iverson bracket notation, $Y_i=[X\ge i]$.

We also defined a random variable $I=XY_n$; when $X\lt n$ we have $I=X\cdot0=0$, when $X\ge n$ we have $I=X\cdot1=X$.

Now we verify the identity$$I=nY_n+\sum_{i=n+1}^{\infty}Y_i.$$Let $k$ be the observed value of the random variable $X$. By our definition of $Y_i$, we have $Y_i=1$ for all $i\le k$, and $Y_i=0$ for all $i\gt k$.

If $k\lt n$, then all terms on both sides of the identity are zero.

If $k=n$, then the identity reduces to $$n=n\cdot1+\sum_{i=n+1}^{\infty}0.$$

If $k=n+r$ for some $r\in\mathbb N$, then the identity reduces to $$n+r=n\cdot1+\sum_{i=n+1}^{n+r}1+\sum_{i=n+r+1}^{\infty}0.$$

  • $\begingroup$ In the penultimate equality you mean $I=nY_n+...$ instead of $Y=nY_n+...$ ? $\endgroup$ – Andrei I Oct 21 '13 at 8:53
  • $\begingroup$ @AndreiI Thanks for the correction! $\endgroup$ – bof Oct 21 '13 at 8:58
  • $\begingroup$ I have some difficulties to comprehend the penultimate equality $I=nY_n+\sum_{i=n+1}^{\infty}Y_i$ (what are each terms?). Could you please elaborate on it? $\endgroup$ – Andrei I Oct 21 '13 at 15:13

Assume we know that (see this link)

$\tag 1 \displaystyle{\sum_{i=0}^{\infty}\frac{i}{2^i} = 2}$

For any integer fixed integer $n \ge 0$ we have a statement $S(n)$ defined by

$\tag 2 S(n): \quad \displaystyle{\sum_{i=n}^{\infty}\frac{i}{2^i} = \frac{n+1}{2^{n-1}}}$

We will prove that

$\tag 3 k \ge 0 \text{ implies } S(k)$

Using $\text{(1)}$ and the fact that

$\quad 2 = \frac{0+1}{2^{0-1}}$

it follows that $S(0)$ is true.

Assume $S(n)$ is true. This is equivalent to writing

$\tag 4 \displaystyle{\sum_{i=n}^{\infty}\frac{i}{2^i} - \frac{n}{2^n} = \frac{n+1}{2^{n-1}} - \frac{n}{2^n} }$

The LHS of $\text{(4)}$ is equal to $\displaystyle{\sum_{i=n+1}^{\infty}\frac{i}{2^i}}$.

As for the RHS, applying algebra we can write

$\quad \frac{n+1}{2^{n-1}} - \frac{n}{2^n} = \frac{(n+1)+1}{2^{(n+1)-1}}$

We have shown that $S(n+1)$ must also be true.

By induction we conclude the veracity of $\text{(3)}$.


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.