/sci/ - Science & Math

Shamelessly reposting from former thread. Any ideas would be appreciated.

An ant searches an N-by-N grid [math]\mathcal{G}[/math] for some target node [math]\tau[/math]. Each node [math]v \in \mathcal{G}[/math] is equipped with a pointer to one of its neighbours, and following all such pointers forms a shortest path [math]v \longrightarrow \tau[/math]. That is, the pointers guide the ant towards the target. However due to noise, each pointer might point in the wrong direction instead, with some probability [math]q[/math] (independently of other pointers).

For this task, the ant keeps track of a "heat map" of [math]\mathcal{G}[/math], estimating [math]\tau[/math]'s location based on all the advice it has seen so far. It assigns scores to unexplored nodes (nevermind how), and greedily walks to the highest-scoring node, until it discovers [math]\tau[/math] and terminates.

Let [math]d[/math] be the distance from the ant's starting position to the target. How do I even begin to analyze the expected number of moves w.r.t. [math]d[/math]? This isn't quite a random walk - the ant's decisions are deterministic, yet the environment itself is random. Does anyone have a reference for this sort of analysis on graphs? Or any ideas just to get me started?

An ant searches an [math]N \times N[/math] grid [math]\mathcal{G}[/math] for some target node [math]\tau[/math]. Each node [math]v \in \mathcal{G}[/math] is equipped with a pointer to one of its neighbours, and following all such pointers forms a shortest path from [math]v[/math] to [math]\tau[/math]. That is, the pointers guide the ant towards the target. But due to noise, each such pointer points in the wrong direction instead, with some probability [math]q[/math] (independently of other nodes).

For this task, the ant keeps track of a "heat map" of [math]\mathcal{G}[/math], estimating [math]\tau[/math]'s location based on all the advice it has seen so far. It assigns scores to unexplored nodes (nevermind how), and greedily walks to the highest-scoring node, until it discovers [math]\tau[/math] and terminates.

Let [math]d[/math] be the distance from the ant's starting point to the target. How do I even begin to analyze the expected number of moves w.r.t. [math]d[/math]? This isn't a random walk - the ant's decisions are deterministic, yet the environment itself is random. Does anyone have a reference for this sort of analysis on graphs? Or any ideas just to get me started?