Timeline for The power of two random choices with pairwise independence
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Apr 16, 2015 at 10:40 | history | bounty ended | Simd | ||
| S Apr 16, 2015 at 10:40 | history | notice removed | Simd | ||
| Apr 16, 2015 at 10:40 | vote | accept | Simd | ||
| Apr 16, 2015 at 10:40 | vote | accept | Simd | ||
| Apr 16, 2015 at 10:40 | |||||
| Apr 15, 2015 at 20:37 | answer | added | Douglas Zare | timeline score: 3 | |
| Apr 13, 2015 at 15:36 | answer | added | Will Sawin | timeline score: 3 | |
| Apr 10, 2015 at 13:02 | comment | added | Simd | @cardinal The random process I am thinking of samples integers from $\{1,\dots,n\}$ uniformly at random (but with only pairwise independence). Each sample represents a bin. In the "power of two choices" version, two samples are taken at each turn and both bins are inspected. A ball is then placed in the bin which is least full (or a random bin if they are equally full). The whole process terminates when $n$ balls have been placed into bins. Does this clear it up? | |
| Apr 10, 2015 at 11:26 | comment | added | cardinal | A curiously related question posted on math.SE at about the same time. | |
| Apr 10, 2015 at 11:25 | comment | added | cardinal | Can you clarify the pairwise independence selection process you speak of? | |
| S Apr 9, 2015 at 8:18 | history | bounty started | Simd | ||
| S Apr 9, 2015 at 8:18 | history | notice added | Simd | Draw attention | |
| Apr 4, 2015 at 6:14 | history | edited | Simd | CC BY-SA 3.0 |
added 211 characters in body
|
| Apr 3, 2015 at 20:31 | history | asked | Simd | CC BY-SA 3.0 |