Pergunta

I am trying to understand randomized AND-OR Game Tree Evaluation. I am stuck with proving the most basic case, namely, an OR node with two leaves (AND node with two leaves is similar).

                          (OR) = 1
                          /  \
                         /    \
  Possible inputs:      1      1
                        0      1
                        1      0

You can find detailed description of the problem in this lecture notes or in Randomized Algorithms, pg. 29, by Motwani&Raghavan. Basically, given the OR-node and inputs $0$ or $1$ we evaluate the value of the OR-node by inspecting the input values (leaves). For example if the input is $1$ and $0$ then after reading the first value, $1$, we do not need to read the second value, and hence only one read will need to be done. On the other hand, if the input is $0$ and $1$ then after the reading the first value we still need to read the second value (since it may be equal to $1$).

Randomized version of evaluation tosses an unbiased coin and with probability $0.5$ reads the first input value or the second. So, the problem is, given that the OR-gate has output $1$, to compute the expected number of reads.

Both the lecture notes and the book computes it as following

If the node is to return a $1$, then at least one of the leaves must return a $1$. With probability $1/2$ this leaf will be selected first and only one evaluation will need to be done. The other possibility (also occurring with probability $1/2$) is that both leaves will need to be evaluated. The expected number of evaluations, $E^{OR}_1$, is given by $$ E^{OR}_1 = \left(\frac{1}{2} \times 1\right) + \left(\frac{1}{2} \times 2\right) = \frac{3}{2}$$

However, I compute it differently. The probability that a certain leaf is selected is $1/2$, but since we have three possible inputs the probability that the selected leaf has value $0$ is different from the probability that it is $1$. In particular $P(value=1)=2/3$ and $P(value=0)=1/3$. In other words, the probability that a leaf with $1$ will be selected is slightly greater than $1/2$. I'm probably missing something. Could someone explain what is wrong with my approach?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top