A random walk that moves to less-visited nodes

Question

Consider a random walk on an undirected graph that keeps track of how many times it has visited every node. At each step, it moves to the node among its neighbors which has been visited the least number of times. If there are several such nodes, it chooses one at random. My question is: what is the (worst-case) cover time of this random walk as a function of the number of nodes $n$?

The answer should be at least $\Omega(n^2)$. Consider a star graph where each node has a self-loop. In this graph, the walk starting at the center will visit the leafs in some order, without loss of generality $1,2,3, \ldots, n-1$ (relabel the vertices if necessary). The time spent at leaf $i$ will be at least $i-1$ because the center will have been visited $i-1$ times before leaf $i$. Thus the total cover time will scale as $\Omega (n^2)$. If we want an example without self-loops, we can consider a star-like graph where each leaf is replaced by a path of length $2$.

Alternatively, what is the largest hitting time between any two vertices for this random walk? This feels like asking a very similar question.

For the usual random walk which jumps to each out-neighbor, the largest hitting time will be $O(n^3)$ but the standard proofs rely on resistances, which are not applicable here due to lack of reversibility.

Answer 1

The assumption here is that the input graph is not a disconnected graph. If it is then it will run forever since some of the nodes will never be reached from set of nodes.

Since the graph is undirected, at any point in time, the decision is made solely based on at what node you are and from that node a neighbor with least visited is going to be picked. So, it is possible that the node that is used to reach the current node may very well be next node to be visited (returning). As you visit the node, it increases the node's visited count and forces alternate node at next choice. Each node would have a visited count any where from 1 to N and no more than N without all nodes being visited.

The constraint that the next node to be visited be a least visited tracks whether node is visited or not and forcing to visit all nodes. Let us say that a global variable tracks the number of visited nodes. Whenever a node's visited counts goes from 0 to 1, increment this counter by 1 for the newly visited node. Until this count reaches the number of nodes in the input graph, we know that there exists some nodes that are not yet visited.

At every node, the unvisited node(s) gets priority over already visited nodes since the unvisited node's visited count is 0. So, initially it tracks like DFS and avoids cycle unless there is no other way. As you visit the node that is already visited, it increments the node's visited count there by making it least preferred till every node in the connected component's node weight to be increased as well. If there is another way to reach other unvisited nodes, then those nodes would be preferred and thereby making to find alternate path. If there is no other way, then we would end up back to articulation point which would have at least one node that is least visited. This least visited component would be now explored until all nodes in that component are visited.

The visited count of each articulation point would be number of nodes in the largest component it is connected to plus number of components it is connected to. Eventually, the largest count possible for a node in the graph is one plus the count of articulation point that has maximum of sum of largest component it is connected to plus the number of components it is connected to.

Therefore, the largest hitting time will be O(n^2).