# Tree search guided by a probabilistic oracle

I'm trying to find a solution for the following problem.

I have a tree $T$ of branching factor $b$ and depth $d$. For the moment, I only care about the case where I restrict $b=2$, but I would be interested in the general case as well.

I am looking for an element in $T$ guaranteed to be somewhere at depth $d$, but I can't directly compare with the nodes in $T$. Instead, I must consult a probabilistic oracle $O$. Given a set of nodes, $S=\{n_0,n_1,\dotsc\}$, the oracle $O$ gives me the correct subtree with some probability $p$, where $0 \le p \le 1$, and a random subtree from the set with probability $1-p$. Furthermore, the oracle always gives the same answer when comparing two nodes, even if that answer might be wrong.

Given $\{b,d,p\}$, what might b the most efficient search technique to find the desired element at depth $d$? The cases where $p = 0$ (random search, since the oracle provides no information) and $p = 1$ (the oracle is perfect - just follow the directions from the oracle) are straight-forward, so I'm interested in $0 < p < 1$.

My first thought was at each branch, consult the oracle with all frontier nodes seen thus far and choose the one the oracle rated as best as my current optim the cases where the oracle provides some information, but not perfect knowledge.um subtree, remove it from the list of frontier nodes, and examine its children to see if they match. I wasn't sure if this is optimal or not. Obviously, for $p = 1$ this algorithm is optimal, and reduces to a $b$-ary search, but for $p = 0$, I think it might spend more time opening up the frontier than checking nodes at depth $d$.

edit: I've updated the oracle's probabilities to be more correct in the behavior where it is truly random and provides no information content.

update: To clarify the desired problem soluion, what I am looking for is an algorithm for, say $p = 0.5$ where I can locate a desired element a known depth $d$ with a greater than $0.5$ probability by examining as few nodes as possible. For now, the running time of the oracle isn't that important compared to exploring the tree, but I believe the oracle gives me a solution in $O(m)$ where $m$ is the size of the set given to the oracle.

• Maybe I am being dense, but I don't understand how your oracle works. On the one hand, you say it takes as input a set of nodes $S$, but you don't give any restriction on this set. In this context, if the oracle chooses the correct subtree with probability 1/2, then this is not random search. Consider you first query your oracle with S={ll, lr, rl, rr} (l = left, r = right) i.e. all nodes at depth 2, then it will give you the correct node with probability 1/2, which is considerably better than picking one at random - with probability 1/4 of being correct. – Jérémie Aug 15 '12 at 0:19
• @Jérémie Good point. I was focusing more on treating them as bernoulli trials, but when you give the oracle moe than 2 nodes, you get more information than that. I will update the oracle's probability accordingly. – Foo Barrigno Aug 15 '12 at 12:31
• Some more nitpicking: 1) I still don't think $p=0$ is random search, because if the oracle returns the correct node with probability $p=0$, then you know, when asking the oracle to pick one out of two nodes, to choose the opposite one! 2) It would be useful if you were a little bit more detailed about the oracle's behavior: you say that the answer is always the same given the same two nodes. – Jérémie Aug 15 '12 at 13:21
• (cont'd) For instance, what about this scenario. I have several sets, $S_1=\{a, o_1\}$ and $S_2=\{a, o_2\}$ and $S_3 =\{a, o_3\}$, where $a$ and the $o_i$ do not have any subtree in common. Can I force the oracle to give me more information on $a$, by querying it with $S_1$, $S_2$ and $S_3$? In other words, if it picks $a$ all three times, are each of these choices independent? – Jérémie Aug 15 '12 at 13:23
• @Jérémie: I think he says that with probability $1-p$, the oracle gives a (uniformly?) random subtree. So in the case $n \geqslant 2$, the probability of definitely getting it right is $p$, and the probability of getting it right by accident is $\tfrac{1}{2}(1-p)$, for a total probability of $\tfrac{1}{2}(1+p)$ of getting it right, and a probability of $\tfrac{1}{2}(1-p)$ of getting it wrong. So $p$ represents a bias towards the correct answer rather than the probability of success. – Niel de Beaudrap Aug 15 '12 at 13:39