Abstract: We develop lagged Metropolis-Hastings walk (LMHW) in simple undirected graphs, where the transition to the next state (i.e. node) depends on both the current and previous states, i.e. lagged, and each proposed transition to an adjacent node is subject to an acceptance mechanism — hence the term LMHW. The LMHW can be specified according to given stationary sampling probabilities. Various existing random walks in graphs can be incorporated as special cases.
We consider two different types of applications. In the first case, one is interested in a genuine graph problem, for which we propose a novel LMHW-sampling approach to the estimation of graph parameters that are given as functions of values associated with finite-order subgraphs, such as edge, triangle, 4-cycle and others. In the second case, one is interested in a ‘traditional’ finite-population sampling problem, such as spatial sampling from a population of units-in-space. We propose a graph spatial sampling (GSS) approach, where we first design a graph which include the finite population units as the nodes in the graph and then apply LMHW-sampling to select the nodes. We illustrate how the GSS approach can be more flexible for improving the design efficiency compared to the existing spatial sampling methods.