# Average-case analysis help

I am stuck on trying to understand how to solve the following question. Could someone please explain for a beginner to average-case analysis?

Considering the following algorithm A which takes as input a bit string b = b_1, b_2, ... , b_n (each b_i is either 0 or 1) and does the following:

A(b,n)
k = 0
FOR i = 1 TO n DO
IF b_i = 1 THEN
k = k + 1
j = k mod 2
IF j = 1 THEN
FOR i = 1 TO k DO
PRINT("Hello World")


Assuming each string is bit string b is equally likely, what is the average number of "Hello Worlds" that A will print?

The hint I have so far is I need to express the sum directly on the sample space, where $X$ below represents the number of times "Hello World" is printed, and depends on individual inputs. $$E(X) = \sum_{L \in S_n} X(L) \cdot Pr(L)$$

• And can you simplify that sum?
– Raphael
Sep 27 '15 at 23:57
• This isn't about average case analysis, but rather an exercise in elementary probability. Sep 28 '15 at 6:50

You haven't stated what the distribution of the initial vector is. I'm assuming that each $b_i$ is independently set to $0$ or $1$ with equal probability.

The first step is to find a formula for the expectation $E$. Let $k$ be the value of $k$, that is, the number of 1s in the vector. We know that $k$ has binomial distribution $\mathrm{Bin}(n,1/2)$. Then $$E = \sum_{\ell\text{ odd}} \Pr[k=\ell] \ell = \sum_{\ell\text{ odd}} 2^{-n} \binom{n}{\ell} \ell.$$ A good idea now is to use the binomial identity $\binom{n}{\ell}\ell = \binom{n-1}{\ell-1}n$: $$E = \frac{n}{2^n} \sum_{\ell\text{ odd}} \binom{n-1}{\ell-1} = \frac{n}{2^n} \sum_{r\text{ even}} \binom{n-1}{r}.$$ When $n$ is even, the binomial identity $\binom{n-1}{r} = \binom{n-1}{n-1-r}$ implies that $$\sum_{r\text{ even}} \binom{n-1}{r} = \frac{1}{2} \sum_{r\text{ even}} \left[\binom{n-1}{r} + \binom{n-1}{n-1-r}\right] = \frac{1}{2} \sum_r \binom{n-1}{r} = \frac{1}{2} \cdot 2^{n-1},$$ and so $$E = \frac{n}{2^n} \cdot 2^{n-2} = \frac{n}{4}.$$ I'll leave you the case of $n$ odd (you get the same answer, but a different trick has to be used).

The answer $n/4$ is what we expect. Here's why. If the if wasn't there, then $E$ would equal the expected value of $k$, which is $n/2$. As it is, we are only printing "with probability $1/2$", so we would expect the answer to be roughly half of $n/2$, that is, $n/4$. Since the printing condition depends on $k$, this heuristic calculation is wrong, though it turns out to predict exactly the correct value. Still, it lends credence to our calculation.

• If $n=1$, shouldn't you get $1/2$ for the expectation? Sep 28 '15 at 11:58
• @Louis Yes, there the formula doesn't work. But it works for all larger $n$. Sep 28 '15 at 13:36

The first loop counts $k$, the number of $1$'s, an integer in range $[0,n]$, with a binomial distribution. When $k$ is odd, $k$ PRINTs are performed.

So the answer is the weighted average of the odd integers in range $[0,n]$.

By the symmetry of Pascal's triangle, for odd $n$, the sum of odd $k$'s equals the sum of even $k$'s, while the total sum is $(n+1)\dfrac n2$ (using the mean formula).

Hence the requested expectation, $\dfrac n4$.

• Remains to solve for even $n$. Sep 28 '15 at 23:04