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]=sumlimits_{i=0}^{{{2}^{N}}-1}{{{Q}_{i}}({{p}^{N-i}}}{{q}^{i}}) & Rightarrow E[Q]=sumlimits_{i=0}^{15}{{{Q}_{i}}({{p}^{N-i}}}{{q}^{i}}) & Rightarrow E[Q]={{p}^{4}}+4times 5times {{p}^{3}}q+2times 5times {{p}^{2}}{{q}^{2}}+4times 7times {{p}^{2}}{{q}^{2}}+4times 7times p{{q}^{3}}+1times 7times {{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:
[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]=sumlimits_{i=0}^{{{2}^{N}}-1}{{{Q}_{i}}({{p}^{N-i}}}{{q}^{i}}) & Rightarrow E[Q]=sumlimits_{i=0}^{15}{{{Q}_{i}}({{p}^{N-i}}}{{q}^{i}}) & Rightarrow E[Q]={{p}^{4}}+4times 5times {{p}^{3}}q+2times 5times {{p}^{2}}{{q}^{2}}+4times 7times {{p}^{2}}{{q}^{2}}+4times 7times p{{q}^{3}}+1times 7times {{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:
- First question: Is it (i-e 0000 0001) equal to ZERO (i-e 0000 0000) ? The answer is No, for our case.
- 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)?
- 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.
- 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
