Paths and Probabilities for a Random Walk on a Graph I'm working on a problem about $N$ nodes that are randomly positioned on a rectangular grid. I want to take a sample of $n\leq N$ nodes by randomly selecting the first node then visiting the nearest neighbour of the last selected node. Once a node is visited, it is excluded from future selctions. If a node has there multiple nearest neighbours, one is randomly picked among them.

I'm interested in the probability that a node is visited (I'm also interested in the probability that a pair of nodes appear in the same sample). I'm using the following population as an example: $$\{(-4,6),(0,5),(-3,4),(-2,4),(2,4),(3,4),(1,3),(5,3),(3,2),(2,1),(-1,0),(-3,1),(1,-1),(-4,-2),(-3,-2),(-1,-2),(3,-2),(4,-2),(2,-3),(4,-3),(2,-4),(4,-4),(5,-4),(-5,-5),(2,-5)\}$$


(Note: The numbers above the points are just identifying labels. They do not indicate anything about the order in which they are visited. A sample of three points would be something like $6 \rightarrow 5 \rightarrow 7$)

Here are my two approaches:


Enumerate all the possible paths of a specified length, calculate the probability of each path, then sum up the probabilities of the paths that include a particular node.
Repeatedly take samples then calculate the proportion of paths that include a particular node.


Is there a better way to solve my problem? By the way, I'm using R to do the computing.

I don't have any background in graph theory whatsoever. I'd like to look up terms and concepts that would be relevant to what I'm doing, but I'm not even sure where to begin. Do you have any ideas for a solution or do you know of any resources that can be understood by a novice?
You can make a state machine from this as follows. 

Let the set of points generated be $V$. 

Add extra dummy start node $s$. Add edges $(s, v)$ for all $v \in V$. And add edge 
from $(u, v)$ where $u, v \in V$ are nearest neighbors. 

Assuming points to visit are chosen uniformly assign probability $1/|V|$ to edges $(s,v)$ 
and probability of $1/\text{number of nearest neighbors}$ to edges that connect nearest neighbors. 

This now forms a state diagram like http://en.wikipedia.org/wiki/Markov_chain#Example

The graph can be represented as matrix $G$ where $G_{ij} =1$ if there is edge between $i$ and $j$. 
And probabilities can be put in a matrix $P$ of size $N + 1 \times N + 1$. 

$G^k_{ij}$ gives number of paths of length $k$ from $i$  to $j$. 

$(P^k x)_j$ gives probability of reaching $j$ from $i$ in $k$ steps where $x$ is a vector where only $i^{th}$ entry is 1 and others are 0.