0
$\begingroup$

I am trying to compute the average length of a bit string from all bit strings of $\{0,1\}^n$. By length n I mean a bit string of length n where the most significant bit is 1. I know there is $2^0$ strings of length 1, $2^1$ strings of length 2 ... $2^{n-1}$ strings of length n.

So the average length over all strings can be computed as the # of strings of lenght n times n, over the total # of strings in $\{0,1\}^n$.

$\frac{\sum_{i=0}^{n} 2^{i}(i +1) }{2^n}$

I feel that this sum should be equal to (n - 1). However I can not simplify this sum into an expression.

Any ideas how to simplify this sum or maybe a different approach to computing the average length of all bitstrings.

$\endgroup$
0
$\begingroup$

The result should be $2n+2^{-n}$.

$\sum_{i=0}^n 2^i \cdot (i+1)=\sum_{i=0}^n i\cdot 2^i + \sum_{i=0}^n 2^i$, where the right summand is just the geometric sum. The left one is $\sum_{i=0}^n \sum_{j=i}^n 2^j$ and now you have a sum of geometric sums. And so on.

Does that help?

$\endgroup$
0
$\begingroup$

Let $$ f(x)=\sum_{i=0}^{n-1}x^i(i+1) $$ Note that f(x)=g'(x) where $$ g(x)=\sum_{i=0}^n x^i=\frac{1-x^{n+1}}{1-x}$$ (this is a sum of geometric series). Take the derivative g'(2) to obtain the sum $$\sum_{i=0}^{n-1}2^i(i+1)$$ and divide the result by 2^n.

$\endgroup$

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.