Timeline for Random sample of spanning trees
Current License: CC BY-SA 4.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 17, 2023 at 6:45 | vote | accept | Paul R | ||
| Nov 15, 2023 at 18:58 | comment | added | Paul R | @JukkaKohonen , each tree has the same probability of being picked. | |
| Nov 15, 2023 at 14:42 | comment | added | Sam Hopkins | @ManfredWeis: generating (uniformly) random unlabeled trees is a much more difficult problem than this one of generating (uniformly) random labeled trees. | |
| Nov 15, 2023 at 14:39 | comment | added | Manfred Weis | Except for dealing with unlabelled trees instead of with labelled ones the paper cited in this MO question seems to be closely related | |
| Nov 15, 2023 at 13:49 | answer | added | HenrikRüping | timeline score: 0 | |
| Nov 15, 2023 at 8:29 | comment | added | Jukka Kohonen | Uniform distribution, over a discrete set such as "all spanning trees of this graph", simply means that when you pick one element (one tree), each tree has the same probability of being picked. I have no idea what "normal" might be in this context, and if you don't know that either, I guess we can safely ignore that suggestion. | |
| Nov 15, 2023 at 8:19 | comment | added | Paul R | @JukkaKohonen, I'm not an expert in this field. I mean that sample can have uniform or normal distribution. | |
| Nov 15, 2023 at 7:52 | comment | added | Jukka Kohonen | @Paul, I don't understand what is "normal" distribution over trees. Can you clarify? | |
| Nov 14, 2023 at 23:23 | comment | added | Dan Piponi | Propp and Wilson have a nice Monte Carlo method using coupling from the past to ensure you know when to terminate the iteration: "How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph" www2.stat.duke.edu/~scs/Projects/Trees/Theory/… | |
| Nov 14, 2023 at 22:19 | answer | added | Gordon Royle | timeline score: 1 | |
| Nov 14, 2023 at 19:43 | history | became hot network question | |||
| Nov 14, 2023 at 19:22 | comment | added | Paul R | @JukkaKohonen , two options: uniform and normal. | |
| Nov 14, 2023 at 18:31 | comment | added | Jukka Kohonen | Some methods might give you a nonuniform random sample, i.e. some trees might be more probable than some others. | |
| Nov 14, 2023 at 15:41 | answer | added | Manfred Weis | timeline score: 0 | |
| Nov 14, 2023 at 14:23 | comment | added | Paul R | @JukkaKohonen , can you explain the difference? | |
| Nov 14, 2023 at 12:32 | comment | added | Jukka Kohonen | Do you want just random, or uniformly random among the $n^{n-2}$ trees? | |
| Nov 14, 2023 at 11:51 | answer | added | Tony Huynh | timeline score: 11 | |
| S Nov 14, 2023 at 11:41 | review | First questions | |||
| Nov 14, 2023 at 12:06 | |||||
| S Nov 14, 2023 at 11:41 | history | asked | Paul R | CC BY-SA 4.0 |