Timeline for Paths and Probabilities for a Random Walk on a Graph
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 21, 2015 at 18:37 | comment | added | Sasho Nikolov | 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. | |
| May 20, 2015 at 2:54 | comment | added | Maria Reyes | 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. | |
| May 20, 2015 at 2:54 | comment | added | Maria Reyes | 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? | |
| May 19, 2015 at 16:31 | answer | added | Pratik Deoghare | timeline score: 1 | |
| May 19, 2015 at 10:33 | history | tweeted | twitter.com/#!/StackCSTheory/status/600610329731686400 | ||
| May 19, 2015 at 3:30 | comment | added | Sasho Nikolov | 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? | |
| May 19, 2015 at 1:02 | comment | added | Maria Reyes | 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. | |
| May 19, 2015 at 0:58 | history | edited | Maria Reyes | CC BY-SA 3.0 |
added 179 characters in body
|
| May 18, 2015 at 22:36 | comment | added | D.W. | 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? | |
| May 18, 2015 at 21:04 | review | First posts | |||
| May 19, 2015 at 7:30 | |||||
| May 18, 2015 at 20:57 | history | asked | Maria Reyes | CC BY-SA 3.0 |