1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Please state the algorithm, the recurrence and your attempts. As it is, the question is ill-posed (and I wonder where Yuval's answer comes from). $\endgroup$ – Raphael Jul 29 '13 at 18:46
  • $\begingroup$ This question is connected with my previous question $\endgroup$ – kaka Jul 29 '13 at 18:52
  • $\begingroup$ You should make that connection explicit. Aside from that, the previous comment stands: please include algorithm and recurrence. $\endgroup$ – Raphael Jul 29 '13 at 22:17
  • $\begingroup$ plz wait for few days I ll have to write up, again all the stuff. $\endgroup$ – kaka Jul 30 '13 at 13:07
  • $\begingroup$ Please add the algorithm. (An example is not an algorithm.) $\endgroup$ – JeffE Aug 2 '13 at 14:28
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ You can probably also calculate the other moments (variance and so on) this way, but it's probably a bit more complicated. $\endgroup$ – Yuval Filmus Jul 21 '13 at 20:24

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.