Timeline for Random grid point in a d-dimensional ball
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 11, 2016 at 6:30 | history | tweeted | twitter.com/StackCSTheory/status/697668978135691264 | ||
| Feb 7, 2016 at 21:40 | comment | added | Thomas Steinke | @BinFu Please update your question to be precise about what you want. You have not clearly defined the distribution you want to sample from. | |
| Feb 7, 2016 at 15:29 | answer | added | Thomas Steinke | timeline score: 1 | |
| Feb 7, 2016 at 15:24 | comment | added | Peter Shor | @BinFu: the easiest way to improve may be to not use a cube, but to use a slightly larger ball. If the radius is too small, it's still exponential. See my answer. | |
| Feb 7, 2016 at 15:05 | answer | added | Peter Shor | timeline score: 3 | |
| Feb 7, 2016 at 15:04 | comment | added | Bin Fu | I look for random lattice point under uniform distribution, but allow a small bias. Currently I put the ball in a cube and generate random lattice points until one of them is in the ball. It still takes exponential time. | |
| Feb 7, 2016 at 14:51 | comment | added | Bin Fu | Yes, I am interested in lattice point as you pointed out. Your algorithm makes some sense. We need to control time and bias. | |
| Feb 7, 2016 at 14:21 | comment | added | usul | What distribution? Uniform? | |
| Feb 7, 2016 at 8:20 | comment | added | Rahul Savani | If you do not require lattice points, then you can do the following (for sampling uniformly from the L2 ball): Pick a random direction with any spherically symmetric distribution, e.g. picking d coordinates using identical independent normal distributions and using the resulting direction, and then choose the radius, which needs to be chosen with a density for radius $r$ that is proportional to $r^{d-1}$. I suppose you are actually are interested in lattice points (integer points) that lie within the hyperball, but as Thomas requested, please clarify. | |
| Feb 7, 2016 at 6:49 | answer | added | Jaeba | timeline score: 0 | |
| Feb 7, 2016 at 6:13 | review | First posts | |||
| Feb 7, 2016 at 13:23 | |||||
| Feb 7, 2016 at 6:07 | comment | added | Thomas Steinke | What do you mean by "grid point"? Do you just want to sample uniformly from the L2 ball? | |
| Feb 7, 2016 at 6:06 | history | asked | Bin Fu | CC BY-SA 3.0 |