<p>Here’s a simple idea: try a certain number <span class="math-container">$s$</span> of samples, and for each vertex, record how many times its colour agreed with the provided bit.</p>

<p>For vertices outside the path, they agree with probability <span class="math-container">$1/2$</span> on each iteration, while for vertices on the path, the probability is <span class="math-container">$1/2+1/2k$</span>, where <span class="math-container">$k$</span> is the number of vertices on the path.</p>

<p>Thus, if <span class="math-container">$s\approx k^2\log n$</span>, the Chernoff–Hoeffding inequality ensures that with probability at least <span class="math-container">$2/3$</span>, all vertices outside the path agree for less than <span class="math-container">$s(1/2+1/4k)$</span> samples, and all vertices on the path agree for more than <span class="math-container">$s(1/2+1/4k)$</span> samples, which lets you pinpoint the path. If you don’t know <span class="math-container">$k$</span> in advance, you can just bound it by <span class="math-container">$n$</span>.</p>

CC BY-SA 4.0
2019-05-28T16:14:04.307Z
2019-05-28T16:14:04.307Z
Emil Jeřábek
<p>Consider an input set of vertices <span class="math-container">$V$</span> and vertices <span class="math-container">$s,t\in V$</span>.
The goal is to learn some unknown shortest path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span>; the set of edges of the graph is hidden at first and there may be multiple shortest paths.</p>

<p>At each iteration, each vertex is randomly colored using <span class="math-container">$0$</span> or <span class="math-container">$1$</span>.
We then get a single bit, that is <span class="math-container">$1$</span> with a probability proportional to the number of <span class="math-container">$1$</span>-vertices along the path.
That is, if <span class="math-container">$6$</span> of the vertices along the path were colored with <span class="math-container">$1$</span> and <span class="math-container">$4$</span> were zero, then the bit will be <span class="math-container">$1$</span> w.p. 3/5.</p>

<p>Importantly, we get to know the coloring of every iteration, and the goal path does not change.</p>

<blockquote>
  <p><strong>How many samples do we need until we can compute the path with, say, probability 2/3?</strong></p>
</blockquote>

<hr>

<p>A very simplistic approach would be to eliminate all monochromatic paths whose color is different than the given bit (e.g., a <span class="math-container">$1$</span>-path can be eliminated if we get a <span class="math-container">$0$</span>-bit). This seems to give a very weak bound.</p>

CC BY-SA 4.0
2019-05-28T16:46:48.007Z
You may as well assume that the graph is just a single path (and a bunch of isolated vertices), as the other edges do not in any way affect the random process. In fact, the edges in the path also do not affect the random process; the path just acts as a subset of $V$.
Emil Jeřábek
<ds.algorithms><graph-theory><graph-algorithms><machine-learning><sample-complexity>
How many samples are needed to reconstruct a path?
R B
# How many samples are needed to reconstruct a path?

(Asked by: username_0 on 2019-05-28)

Consider an input set of vertices $V$ and vertices $s,t\in V$.
The goal is to learn some unknown shortest path from $s$ to $t$; the set of edges of the graph is hidden at first and there may be multiple shortest paths.

At each iteration, each vertex is randomly colored using $0$ or $1$.
We then get a single bit, that is $1$ with a probability proportional to the number of $1$-vertices along the path.
That is, if $6$ of the vertices along the path were colored with $1$ and $4$ were zero, then the bit will be $1$ w.p. 3/5.

Importantly, we get to know the coloring of every iteration, and the goal path does not change.

> **How many samples do we need until we can compute the path with, say, probability 2/3?**

---

A very simplistic approach would be to eliminate all monochromatic paths whose color is different than the given bit (e.g., a $1$-path can be eliminated if we get a $0$-bit). This seems to give a very weak bound.

**Tags:** ds.algorithms, graph-theory, graph-algorithms, machine-learning, sample-complexity
> **Comments:**
> **username_1**: You may as well assume that the graph is just a single path (and a bunch of isolated vertices), as the other edges do not in any way affect the random process. In fact, the edges in the path also do not affect the random process; the path just acts as a subset of $V$.  

---

## 1 answers

### Answer by username_1 on 2019-05-28. Score: 4 | Accepted answer

Here’s a simple idea: try a certain number $s$ of samples, and for each vertex, record how many times its colour agreed with the provided bit.

For vertices outside the path, they agree with probability $1/2$ on each iteration, while for vertices on the path, the probability is $1/2+1/2k$, where $k$ is the number of vertices on the path.

Thus, if $s\approx k^2\log n$, the Chernoff–Hoeffding inequality ensures that with probability at least $2/3$, all vertices outside the path agree for less than $s(1/2+1/4k)$ samples, and all vertices on the path agree for more than $s(1/2+1/4k)$ samples, which lets you pinpoint the path. If you don’t know $k$ in advance, you can just bound it by $n$.


---

