Average-case analysis help

Question

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) $$

Answer 1

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.

Answer 2

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$.