<p>You can make a state machine from this as follows. </p>

<p>Let the set of points generated be $V$. </p>

<p>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. </p>

<p>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. </p>

<p>This now forms a state diagram like <a href="http://en.wikipedia.org/wiki/Markov_chain#Example" rel="nofollow">http://en.wikipedia.org/wiki/Markov_chain#Example</a></p>

<p>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$. </p>

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

<p>$(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. </p>

CC BY-SA 3.0
2015-05-20T02:57:01.290Z
Thanks for the idea. I wonder if there's a way to account for the following situation using a state machine. As I understand, the matrix G is constant at each step, but in my example, the nearest neighbour of a point depends on **all** previously selected points. If we start at point 4, its nearest neighbour is point 3. But if point 3 was selected before point 4, then point 2 is now the nearest neighbour of point 4.
Maria Reyes
CC BY-SA 3.0
2015-05-19T16:31:04.123Z
2015-05-19T16:31:04.123Z
Pratik Deoghare
<p>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.</p>

<p>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)\}$$</p>

<p><img src="https://i.sstatic.net/lkqIy.png" alt="enter image description here">
<em>(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$)</em></p>

<p>Here are my two approaches:</p>

<ol>
<li><p>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.</p></li>
<li><p>Repeatedly take samples then calculate the proportion of paths that include a particular node.</p></li>
</ol>

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

<p>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?</p>

CC BY-SA 3.0
2015-05-18T22:36:38.580Z
How many nodes are there that have multiple neighbors at the same distance?  Note that if there aren't any such nodes, then the path is entirely determined by the choice of starting node, so there are only $N$ possible paths, and all paths can be easily enumerated.  If we let $k$ be the number of nodes that have multiple neighbors at the same distance, and if $k$ is sufficiently small, the number of possible paths might not be too bad (and there might be even more efficient algorithms).  Do you have any reason to expect $k$ to be especially small?
D.W.
CC BY-SA 3.0
2015-05-19T01:02:57.830Z
Yes, that's a good point. The example above has 25 nodes (I edited the post to give the coordinates). If I take a sample of 3 nodes, there are 41 possible paths and if I take a sample of 24 nodes, there are 1036 paths, so it isn't too bad to compute. Later though, I'll be analyzing several populations, each with 80-200 nodes, where I will sample 10-180 nodes per population. I haven't yet decided how many nodes will have multiple neighbours, but it would probably be a sizeable portion.
Maria Reyes
CC BY-SA 3.0
2015-05-19T03:30:27.523Z
It is not clear to me from what distribution the $N$ points are picked? Are they uniformly random points in a square? Are they uniformly random points from an $m\times m$ grid, and if so how big is $m$ with respect to $N$? Depending on your answer, it may be the case that with very high probability each point has a unique nearest neighbor, and, as DW noted, that means you'd only need to consider N paths. Also, how did you arrive at 41 length 3 paths for your example input?
Sasho Nikolov
CC BY-SA 3.0
2015-05-20T02:54:12.950Z
That's right, the points will be uniformly distributed on an $m \times m$ grid. I haven't thought about how big my grid will be. I'm glad you brought up this point. I'm guessing that for a fixed value of N, if I increase the grid size then the probability that each point has a unique neighbour will be higher. Is this correct?
Maria Reyes
CC BY-SA 3.0
2015-05-20T02:54:20.043Z
By the way, here's what I did to count the number of length-3 paths. First, I constructed a matrix of distances ($ij^{th}$ entry is the distance between point $i$ and point $j$). If I start at point 1, then in the matrix, I delete column 1 and search row 1 for the minimum. It happens to be in column 3. Next, I delete column 3 from the matrix, and seach row 3 for the minimum. I end up with the sequence 1-3-4. I try all possible starting points to get the other paths 2-4-3, 2-5-6, ..., 25-21-19.
Maria Reyes
CC BY-SA 3.0
2015-05-21T18:37:14.560Z
Yes, surely bigger values of $m$ give you a higher probability that each point has a unique nearest neighbor, and in the limit the probability is 1 if you have a continuous distribution on the square. For your case, a heuristic calculation suggests that for $m$ slightly bigger than $N$, say about $N\log N$, with high probability all points have unique nearest neighbors.
Sasho Nikolov
<graph-theory><graph-algorithms><pr.probability><random-walks>
Paths and Probabilities for a Random Walk on a Graph
Maria Reyes
# Paths and Probabilities for a Random Walk on a Graph

(Asked by: username_0 on 2015-05-18)

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)\}$$

![enter image description here](https://i.sstatic.net/lkqIy.png)
*(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:

1. 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.
2. 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?

**Tags:** graph-theory, graph-algorithms, pr.probability, random-walks

> **Comments:**
> **username_1**: How many nodes are there that have multiple neighbors at the same distance?  Note that if there aren't any such nodes, then the path is entirely determined by the choice of starting node, so there are only $N$ possible paths, and all paths can be easily enumerated.  If we let $k$ be the number of nodes that have multiple neighbors at the same distance, and if $k$ is sufficiently small, the number of possible paths might not be too bad (and there might be even more efficient algorithms).  Do you have any reason to expect $k$ to be especially small?  
> **username_0**: Yes, that's a good point. The example above has 25 nodes (I edited the post to give the coordinates). If I take a sample of 3 nodes, there are 41 possible paths and if I take a sample of 24 nodes, there are 1036 paths, so it isn't too bad to compute. Later though, I'll be analyzing several populations, each with 80-200 nodes, where I will sample 10-180 nodes per population. I haven't yet decided how many nodes will have multiple neighbours, but it would probably be a sizeable portion.  
> **username_2**: It is not clear to me from what distribution the $N$ points are picked? Are they uniformly random points in a square? Are they uniformly random points from an $m\times m$ grid, and if so how big is $m$ with respect to $N$? Depending on your answer, it may be the case that with very high probability each point has a unique nearest neighbor, and, as DW noted, that means you'd only need to consider N paths. Also, how did you arrive at 41 length 3 paths for your example input?  
> **username_0**: That's right, the points will be uniformly distributed on an $m \times m$ grid. I haven't thought about how big my grid will be. I'm glad you brought up this point. I'm guessing that for a fixed value of N, if I increase the grid size then the probability that each point has a unique neighbour will be higher. Is this correct?  
> **username_0**: By the way, here's what I did to count the number of length-3 paths. First, I constructed a matrix of distances ($ij^{th}$ entry is the distance between point $i$ and point $j$). If I start at point 1, then in the matrix, I delete column 1 and search row 1 for the minimum. It happens to be in column 3. Next, I delete column 3 from the matrix, and seach row 3 for the minimum. I end up with the sequence 1-3-4. I try all possible starting points to get the other paths 2-4-3, 2-5-6, ..., 25-21-19.  
> **username_2**: Yes, surely bigger values of $m$ give you a higher probability that each point has a unique nearest neighbor, and in the limit the probability is 1 if you have a continuous distribution on the square. For your case, a heuristic calculation suggests that for $m$ slightly bigger than $N$, say about $N\log N$, with high probability all points have unique nearest neighbors.  

---

## 1 answers

### Answer by username_3 on 2015-05-19. Score: 1

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.

> **Comments:**
> **username_0**: Thanks for the idea. I wonder if there's a way to account for the following situation using a state machine. As I understand, the matrix G is constant at each step, but in my example, the nearest neighbour of a point depends on **all** previously selected points. If we start at point 4, its nearest neighbour is point 3. But if point 3 was selected before point 4, then point 2 is now the nearest neighbour of point 4.  

---

