2
$\begingroup$

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

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

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.

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

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

$\endgroup$
  • $\begingroup$ Remains to solve for even $n$. $\endgroup$ – Yves Daoust Sep 28 '15 at 23:04

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.