[Solved]: Closed-form Expression of the Expected value of the Cost of D&C Algorithm?

Problem Detail: 

Let there is a binary-string, $B$, of length $N$. The probability of occurrence of 0 and 1 in this binary-word is $p$ and $q$ , respectively. Each bit in the string is independent of any other bit.

There is an algorithm (divide and conquer) which finds the location of 1's in a given binary-string, in Q # of steps (cost).

I am looking for some close-form solution of the expected # of steps,$E[Q]$, with given probabilities $p$ and $q$ for a string of length $N$.

For instance, for $N=4$ the cost ,${{Q}_{i}}$, for each possible word is:
[\begin{matrix} {{B}_{i}} & {{Q}_{i}} & {{P}_{i}} \\ 0000 & 1 & {{p}^{4}} \\ 0001 & 5 & {{p}^{3}}q \\ 0010 & 5 & {{p}^{3}}q \\ 0011 & 5 & {{p}^{2}}{{q}^{2}} \\ 0100 & 5 & {{p}^{3}}q \\ 0101 & 7 & {{p}^{2}}{{q}^{2}} \\ 0110 & 7 & {{p}^{2}}{{q}^{2}} \\ 0111 & 7 & p{{q}^{3}} \\ 1000 & 5 & {{p}^{3}}q \\ 1001 & 7 & {{p}^{2}}{{q}^{2}} \\ 1010 & 7 & {{p}^{2}}{{q}^{2}} \\ 1011 & 7 & p{{q}^{3}} \\ 1100 & 5 & {{p}^{2}}{{q}^{2}} \\ 1101 & 7 & p{{q}^{3}} \\ 1110 & 7 & p{{q}^{3}} \\ 1111 & 7 & {{q}^{4}} \\ \end{matrix}] From the discrete probability theory, we can evaluate the expected cost of the above case ,$N=4$,as follow $\begin{align} & \therefore E[Q]=\sum\limits_{i=0}^{{{2}^{N}}-1}{{{Q}_{i}}({{p}^{N-i}}}{{q}^{i}}) \\ & \Rightarrow E[Q]=\sum\limits_{i=0}^{15}{{{Q}_{i}}({{p}^{N-i}}}{{q}^{i}}) \\ & \Rightarrow E[Q]={{p}^{4}}+4\times 5\times {{p}^{3}}q+2\times 5\times {{p}^{2}}{{q}^{2}}+4\times 7\times {{p}^{2}}{{q}^{2}}+4\times 7\times p{{q}^{3}}+1\times 7\times {{q}^{4}} \\ & \Rightarrow E[Q]={{p}^{4}}+20{{p}^{3}}q+10{{p}^{2}}{{q}^{2}}+28{{p}^{2}}{{q}^{2}}+28p{{q}^{3}}+7{{q}^{4}} \\ \end{align}$

However, for very large values of N, say 1024, it is computationally not possible to evaluate the cost of each possible binary string (i-e ${{2}^{1024}}=\text{1}\text{.79}\times \text{1}{{\text{0}}^{308}}$ binary words). So, this is the problem I am stuck in.

Is it possible to deduce some analytical/ close-form expression for evaluating the expected value of the cost of this algorithm for a given length N and probabilities p and q (instead of brute-force method defined above)?

I will be very thankful, if someone could help in this regard.

ADDITIONAL INFORMATION:

Divide & Conquer Algorithm: Lets take 0000 0001, for instance:

1. First question: Is it (i-e 0000 0001) equal to ZERO (i-e 0000 0000) ? The answer is No, for our case.

2. Then divide the original 8 bit word into two 4 bit segments, and again ask the same question for each of the two 4 bit words. So for our case it would be YES for the first segment (0000) and NO for the other segment (0001)?

3. Now, this time I will be questioning only the segment where I got NO. In our case it was 0001. Then, I will now again divide this 4-bit segment into two segments and pose the same question. Hence, is 00 equal to ZERO? answer : YES. For the other segment , 01, the answer is NO.

4. This is the final step. I will again divide the 2-bit word into two 1-bits, i-e 0 and 1. So, my first question: is 0 equal to 0? answer is YES. And for the other remaining bit, is 1 equal to 0? Answer is NO.

So, I asked a total of 7 questions to find the location of 1 in a binary word of 0000 0001. Similarly, we will go through other binary words.

Efficient Way for evaluating the cost of Above algorithm: (courtesy to Yuval Filmus)

Here is how to calculate the cost of the algorithm. Start with the bit vector $x$, and consider the following operation $O$, which divides $x$ into pairs of bits and computes their ORs. Thus $|O(x)| = |x|/2$. Compute a sequence $O(x),O(O(x)),O(O(O(x))),\ldots$ until you get a vector of width $1$. Count the total number of 1s in the sequence. If you got $N$, then the cost is $2N+1$.

For example, suppose $x=0101$. Then the sequence is $$ 11,1, $$ and so $N = 3$ and the cost is $7$.

Asked By : kaka

Answered By : Yuval Filmus

Expectation is additive, so your expectation equals $$ E := 2E[w(O(x))] + 2E[w(O(O(x)))] + \cdots + 2E[w(O(\cdots(x)\cdots))] + 1, $$ where $w(\cdot)$ is Hamming weight. Let's calculate $E[w(O(x))]$, again using the fact that expectation is additive. The probability that the $i$th bit of $O(x)$ is $1$ is exactly $1-p^2$, and there are $N/2$ of them, therefore $E[w(O(x))] = (N/2)(1-p^2)$. Similarly, the probability that the $i$th bit of $O(O(x))$ is $1$ is exactly $1-p^4$, and there are $N/4$ of them, and so $E[w(O(O(x))] = (N/4)(1-p^4)$. If $N = 2^n$, then we get $$ E = 2^n (1-p^2) + 2^{n-1}(1-p^4) + \cdots + 2(1-p^{2^n}) + 1.$$ We can simplify this slightly by summing the geometric series: $$ E = 2^{n+1}-1 - 2^n p^2 - 2^{n-1} p^4 - \cdots - 2p^{2^n}. $$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13376