Consider a Cayley graph of some big finite group. Consider random walk on such a graph - think of it as drunk driver. Fix some number $N$ which is much smaller than group size.
Question 1: How to choose $N$ nodes on Cayley graph such that the probability that random walk making $k$ steps intersect these $N$ nodes would be maximum among all possible other choices of $N$ nodes ? Any ideas or references are welcome.
Think of these nodes as policemen who are catching drunk drivers if they pass throw the node.
Technically - average over all possible starting points of the random walk - since group is finite - there is no problem. So probability of intersection is well-defined for any subset of nodes and any fixed $k$ (number of steps). Intersection may happen on step 0, step 1, step 2 - any step <= k.
Similar question in a more complicated setup.
Imagine drunk drivers - which all wanna go to the same place - identity of the group. (Starting place is again arbitrary.) But since they are drunk their way is partly random - partly follow the trend. It is like a Brownian particle in a electric field. And ask a same question.
To make it more formal:
Consider a distance on a graph: d(g) - distance from identity to g. Add some noise to that function get $d_{noisy}$. Now consider quasi-random walk - where sometimes the move is made randomly and sometimes to minimize $d_{noisy}$.
Question 2: How to choose policemen positions to catch such a "semi-drunk" drivers ?
Of course, detailed answer would depend on details of noise etc... But it can be that there are some universality classes where answer is similar. Any way any information on any kind of noise is appreciated.
