Hacker News
new
|
past
|
comments
|
ask
|
show
|
jobs
|
submit
login
The Alias Method is an O(1) algorithm to select elements from a distribution
(
github.com/cantino
)
5 points
by
tectonic
on March 5, 2013
|
hide
|
past
|
favorite
|
4 comments
filpen
on March 5, 2013
|
next
[–]
While looking up Walker's Alias Method I ended up here
http://forums.udacity.com/questions/1012915/resampling-walke...
, where people say it is not Walker's method, but Vode's. I can't verify it right now but I thought it might be of interest anyway.
pgsandstrom
on March 5, 2013
|
prev
|
next
[–]
"You could also use ranges, picking a random number between 0.0 and 1.0 and returning :win when the number is below 0.8, :lose otherwise. But, these algorithms are still O(n)"
Maybe my math is a bit rusty, but is this really O(n)? Why is that?
andreer
on March 5, 2013
|
parent
|
next
[–]
n here is the number of different elements you can choose from. If there was a third alternative, you'd have to add another if statement.
andreer
on March 5, 2013
|
prev
[–]
An excellent writeup on different techniques to do this:
http://www.keithschwarz.com/darts-dice-coins/
Guidelines
|
FAQ
|
Lists
|
API
|
Security
|
Legal
|
Apply to YC
|
Contact
Search: