<p>I'm trying to find a solution for the following problem.</p>

<p>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.</p>

<p>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.</p>

<p>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 &lt; p &lt; 1$.</p>

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

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

<p><strong>update:</strong> 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.</p>

CC BY-SA 3.0
2012-08-15T00:19:28.657Z
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
CC BY-SA 3.0
2012-08-15T12:31:08.867Z
@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
CC BY-SA 3.0
2012-08-15T13:21:01.220Z
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
CC BY-SA 3.0
2012-08-15T13:23:21.233Z
(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
CC BY-SA 3.0
2012-08-15T13:39:27.257Z
@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
CC BY-SA 3.0
2012-08-15T15:44:01.957Z
(In my previous comment, that should be $n = 2$, not $n \geqslant 2$.)
Niel de Beaudrap
CC BY-SA 3.0
2012-08-15T16:46:30.117Z
@Jérémie: Niel is correct - the meaning I am trying to convey is that for $p=0$ the oracle returns a random element from he set. The oracle will always return what it thinks is correct. For instance, if I give the oracle $\{a_0,a_1,a_2\}$ and it returns $a_2$, then if I give the oracle $\{a_0,a_2\}$ it should also return $a_2$ since it believes (correctly or not) that $a_2$ is superior to $a_0$. I think this is equivalent to the oracle providing an ordering of the elements in the set?
Foo Barrigno
<ds.algorithms><pr.probability><tree><search-problem>
Tree search guided by a probabilistic oracle
Foo Barrigno
# Tree search guided by a probabilistic oracle

(Asked by: username_0 on 2012-08-14)

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.

**Tags:** ds.algorithms, pr.probability, tree, search-problem

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1 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.  
> **username_1**: 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.  
> **username_1**: (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?  
> **username_2**: @username_1: 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.  
> **username_2**: (In my previous comment, that should be $n = 2$, not $n \geqslant 2$.)  
> **username_0**: @username_1: Niel is correct - the meaning I am trying to convey is that for $p=0$ the oracle returns a random element from he set. The oracle will always return what it thinks is correct. For instance, if I give the oracle $\{a_0,a_1,a_2\}$ and it returns $a_2$, then if I give the oracle $\{a_0,a_2\}$ it should also return $a_2$ since it believes (correctly or not) that $a_2$ is superior to $a_0$. I think this is equivalent to the oracle providing an ordering of the elements in the set?  

---

## 0 answers

