Timeline for Non-backtracking random walk in regular (finite) graphs
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 23, 2022 at 15:32 | comment | added | trickymaverick | @MarcusM Aperiodicity can be introduced in the walk by making the walk lazy. | |
| Feb 23, 2022 at 15:26 | comment | added | trickymaverick | @LeechLattice A cycle graph with even number of vertices is also bipartite. | |
| Jun 29, 2019 at 14:10 | vote | accept | Johnny Cage | ||
| Jun 28, 2019 at 15:47 | history | edited | user64494 | CC BY-SA 4.0 |
A typo in the title is corrected.
|
| Jun 28, 2019 at 13:02 | answer | added | Yuval Peres | timeline score: 4 | |
| Oct 21, 2018 at 21:08 | vote | accept | Johnny Cage | ||
| Jun 29, 2019 at 14:10 | |||||
| Oct 20, 2018 at 2:38 | answer | added | LeechLattice | timeline score: 2 | |
| S Oct 19, 2018 at 17:21 | history | suggested | LeechLattice |
This problem is basically about markov chains.
|
|
| Oct 19, 2018 at 15:47 | review | Suggested edits | |||
| S Oct 19, 2018 at 17:21 | |||||
| Oct 19, 2018 at 12:01 | comment | added | LeechLattice | What if the graph in question is a cycle graph? | |
| Oct 18, 2018 at 20:15 | comment | added | Johnny Cage | Sure: I forgot to say that we want of course to avoid bipartiteness... apart from this natural condition, are there other obstructions? | |
| Oct 18, 2018 at 13:10 | comment | added | Marcus M | No such universal condition may exist; if a graph is bipartite, then all walks are periodic and no stationary distribution exists. The $d$-cubes are all bipartite (if you view each vertex as a binary string then the parity of each vertex is the parity of the hamming weight), and thus no stationary distribution exists for any random walk on them. | |
| Oct 18, 2018 at 5:34 | comment | added | Johnny Cage | By 'universal' I mean not depending on the graph, but only if it is k-regular or not (for instance, or any other general condition) . The first thing I would like to know (i.e., references) if starting at a fixed vertex there is a uniform distribution to arrive to any other independently of the graph. I am happy with the restriction of the graph to be k-regular. | |
| Oct 18, 2018 at 0:00 | comment | added | Marcus M | What do you mean by 'universal'? Many of these walks will be periodic on regular graphs (the $d$-dimensional hypercube is $d$-regular and bipartite). | |
| Oct 17, 2018 at 19:21 | history | edited | Johnny Cage | CC BY-SA 4.0 |
added 109 characters in body
|
| Oct 17, 2018 at 19:15 | history | asked | Johnny Cage | CC BY-SA 4.0 |