[HN Gopher] An RNG that runs in your brain
___________________________________________________________________
An RNG that runs in your brain
Author : nalgeon
Score : 229 points
Date : 2024-01-22 17:00 UTC (1 days ago)
(HTM) web link (www.hillelwayne.com)
(TXT) w3m dump (www.hillelwayne.com)
| aredox wrote:
| See also: the Solitaire cipher[0] (requires a deck of cards)
| Geomantic charts[1], which are... kinda binary encoding and
| shuffling?
|
| [0]https://en.wikipedia.org/wiki/Solitaire_%28cipher%29
|
| [1]https://digitalambler.com/2020/05/08/how-to-construct-the-
| sh...
|
| Related : how to debias a biased coin[2] (aka. a Von Neumann
| extractor).
|
| It is not exactly the same (randomness extractor vs. PRNG), but
| there are similarities[3].
|
| [2]https://carlos.bueno.org/2011/10/fair-coin.html
|
| [3]https://en.wikipedia.org/wiki/Randomness_extractor
|
| I want to take this opportunity to recommend Hillel's writing and
| depth of analysis (on top of the quirkiness of doing it in a
| weird lang). Compared to the equivalent answers on
| stackoverflow[4], there is just no comparison.
|
| [4]https://stackoverflow.com/questions/3919597/is-there-a-
| pseud...
| camel-cdr wrote:
| I stumbled over marsaglias usenet post before.
|
| One thing this article didn't discuss is choosing a seed, I think
| humans are better at coming up with a single random number than
| with a sequence of random numbers, but I still like to
| incorporate some "randomness" from the environment.
|
| You can e.g. add the count of something you don't know the count
| of until you count it to the seed. For example: floor tiles in a
| room, books with the color red in a book shelve, ... you can
| obviously also throw a coin or something like that, but that's a
| more involved action.
|
| If you are really dedicated, then you could mix in some
| environmental randomness after ever n iterations.
| aredox wrote:
| A good seed under 60 is simply the second or minutes when you
| check the time.
| kqr wrote:
| And as long as you don't need numbers at a high rate, you can
| just use the seed as the random number. I rarely need more
| than one in sequence so I just use the second hand.
|
| Come to think of it, I rarely need to choose between more
| than 10 alternatives so it's realistic to get at least two
| somewhat random alternatives per minute out of this idea.
| ajb wrote:
| If we're talking about something what can be done by a human,
| then Othello counters or coins are each 1 bit. If not, then a
| hash of a new photo is probably simplest
| DeathArrow wrote:
| Why are people bad at coming up with random numbers?
| TonyTrapp wrote:
| Mathematical randomness is not exactly a skill required for
| survival. In fact, our ability to produce random numbers is so
| bad that our brains consider true randomness to not be random,
| as this blog post from Spotify shows:
| https://engineering.atspotify.com/2014/02/how-to-shuffle-son...
| photonthug wrote:
| Doesn't Spotify basically need to pay nonrandom royalties on
| stuff inside any given playlist such that streaming some
| content costs them more than others, while the users payment
| is constant? If that is true it defies belief that they would
| avoid cost optimization on their side and give users a truly
| random shuffle. Especially if they can argue that users don't
| know randomness when they see it
| TonyTrapp wrote:
| I'm not sure that has anything to with the algorithm
| described in the blog post. I posted it because it's a
| popular, often-referenced example for this type of problem.
| The problem exists outside of Spotify, in any music player.
| And I believe that back when this was written, Spotify was
| paying the same amount of money for all streams, as it was
| way before the whole problem with people streaming white
| noise to launder money arose that they currently try to
| combat by essentially not paying artists with little
| exposure at all.
| xnorswap wrote:
| We're bad at generating randomness because we're bad at
| detecting randomness.
|
| Given a sequence, and asked to grade how closely it fits
| sampling from uniform random, we typically get it very wrong.
|
| For example we underestimate how often streaks or clustering
| happens in uniform data.
|
| We are wired to find patterns. This gives us an advantage for
| some tasks, but for assessing the randomness of data, makes us
| very bad.
| magicalhippo wrote:
| Reminds me of a rather lively IRC debate I had on a
| programming channel about how 1,2,3,4,5 was a perfectly fine
| random sequence of digits. Some just flat out refused to
| accept that, even though I repeatedly highlighted that it was
| just very unlikely.
| koolba wrote:
| As always there's a relevant xkcd: https://xkcd.com/221/
| h4kor wrote:
| I had a math teacher who trolled the entire class.
|
| We (the class) wanted to go outside instead of having a regular
| lecture. He made a deal that if we win his game we go outside,
| otherwise we had to be extra focused for the rest of the
| period.
|
| Everyone in the class had to pick a random number between 1 and
| 100 and write it down. He told us that he would get one guess
| for each pupil (around 30) and if he managed to guess all
| numbers he would win. If any number was left we go outside.
|
| Knowing how bad humans (and especially 12 year olds) are at
| picking random numbers, and knowing which numbers were mostly
| picked, he guessed all numbers with still a handful of guesses
| left.
| mewpmewp2 wrote:
| If he had done it enough times with different kids in the
| past, he would have the perfect data to know the likelihood
| of certain numbers picked and him winning.
|
| That from a teacher's perspective seems like a fascinating
| idea to try out.
| Vvector wrote:
| Those odds are 4 quadrillion to one, if the numbers are
| picked randomly.
| jmilloy wrote:
| I think it's much better because the teacher doesn't have
| to match guesses to students. For example, for each student
| the odds are 30/100, roughly one in three. And any
| duplicates can be matched by a single guess.
| mewpmewp2 wrote:
| I think odds should be 0.3 to the power of the amount of
| students.
|
| E.g. teacher picking 1-30 and then each student has 0.3
| odds of picking 1-30 or 31-100.
|
| The issue is I think all it would take to beat the
| teacher is one unusual student.
| aidenn0 wrote:
| That formula is missing something because for over 100
| students the teacher can't lose. (they get over 100
| guesses and there are only 100 numbers possible)
| mewpmewp2 wrote:
| If the teacher does have 100 guesses then they wouldn't
| lose right.
|
| Then it would be 1 to the power of 100.
|
| I guess I should've clarified that the 0.3 refers to
| being able to choose 30 out of 100 numbers?
| svat wrote:
| More precisely, if there are N students, the probability
| is (min(N,100)/100)^N. This is 1 for N >= 100. And the
| probability at N=30 is indeed a tiny 2e-16, which shows
| that the children's "random" picks were far from
| uniformly random.
|
| (Incidentally, even with N=99 the probability is 0.37 [?]
| 1/e, and the probability is lowest at N=37 [?] 100/e.
| This is not a coincidence.)
| Vvector wrote:
| Reverse it, and it becomes clear.
|
| The teacher picks 30 numbers out of 100. Then each
| student (independently) picks one number. If random, that
| is 0.3 ^ 30. Obviously, the students are not picking
| random.
|
| If I had to pick for the teacher:
|
| multiples of 10: 10,20,30,40,50,60,70,80,90
|
| double digits: 11,22,33,44,55,66,77,88,99
|
| Not sure where to go next.
| me_me_me wrote:
| 3 and 7 are most common digits people come up with with a
| random number 1-10
|
| i would pick a 3-7, 30-37, 70-77, then some other fews
| from there like 1, 100, 50 etc
| ihaveajob wrote:
| This sounds like a great teacher. The fact that you got this
| gem to think about years (decades?) later tells so much about
| his craft.
| h4kor wrote:
| 2 decades now. He was the best teacher I had. Sadly only
| for 2 years as he came temporarily out of retirement when
| our math teacher at the time died.
| dhosek wrote:
| At Pomona College, there's a bit of folklore around a talk a
| math professor gave in which he "proved" that all numbers are
| equal to 47.1 Consequently, students started noticing 47
| everywhere since psychologically, it's a popular number to
| choose as a "random" number between 1 and 100,2 although some
| of the coincidences (the number of trees on the quad, the exit
| number on the 10 to get to Claremont) don't fit into that
| schema.
|
| [?]
|
| 1. Spoiler: there was a divide by zero in his proof.
|
| 2. Why? Because it's near the middle of the interval and is
| prime, two things that will happen if you unthinkingly just
| grab for a number.
| defrost wrote:
| > Marsaglia is most famous for the diehard suite of RNG tests, so
| he knows his stuff.
|
| Fame is relative, for my part Marsaglia is most famous for _The
| Ziggurat Method for Generating Random Variables_ and _numerous_
| other PRNG delights .. the testsuite comes way down the list.
|
| * https://www.jstatsoft.org/article/view/v005i08
|
| * https://en.wikipedia.org/wiki/Ziggurat_algorithm
|
| _Once upon a time I made a branchless generator of large blocks
| of random points on S2 (the surface of a unit sphere) for an
| astrophysics sim, it was a fun exercise_
| camel-cdr wrote:
| Marsaglia was also behind the MWC, SWB, xorshift and KISS
| PRNGs.
|
| Edit: removed a bit because I confused the polar with the ratio
| method
| gcr wrote:
| Oooo post it post it!
|
| Was it "generate a multivariate Gaussian distribution and then
| divide each point by its norm"?
| whyever wrote:
| That works for N dimensions, but for N=2 or 3 there are
| faster methods:
|
| For N=3, there is a method by Marsaglia:
| https://doi.org/10.1214/aoms/1177692644 For N=2, there is a
| method by von Neumann:
| https://mcnp.lanl.gov/pdf_files/nbs_vonneumann.pdf
|
| All of these use rejection sampling, so they are not
| branchless.
| seanhunter wrote:
| The Ziggurat algorithm is fantastic, and is way faster than the
| conventional methods (like Box-Muller) for generating normally-
| distributed variants from a uniform pseudorandom source. I
| implemented it a while back and it was one of those things that
| was a great pleasure to do.
|
| I have also used the diehard suite a while back to convince
| myself that a random mixer thing I came up with was suitably
| random. Basically I wrote a thing to read from various sources
| of entropy, bleach them a bit and then mix them all together in
| a way that was extremely chaotic before feeding them into the
| kernel entropy pool. This was because it used to be a problem
| (back circa 1998 or so) that if you had headless servers
| serving a lot of ssl sessions they would run out of entropy and
| block from time to time. At the time, diehard had been
| implemented in fortran and then compiled to C using a gnu
| fortran transpiler so it was completely impossible to
| understand what each of the tests were actually doing.
|
| On the topic of tfa, one of the most practical "RNG in your
| brain" techniques I heard of was suggested by the poker player
| Dan Harrington in his books, which is for sampling at random
| with some probability between some discrete choices. So say you
| have something you want to do at random 1/3rd of the time and
| the other 2/3rds of the time you're going to do another
| thing[1], the way he says to do this is base it on your watch
| face. So you decide [2] that if the second hand of your watch
| is between 1 and 20 then you will do thing A and if it's
| between 20 and 60 you'll do thing B. Then you look and you do
| whatever thing. The good part about this is clearly even if
| people know you're doing it they can't exploit it because they
| don't know the set of choices you've given yourself, what the
| boundaries are where you choose between strategies etc. It
| doesn't work if you need to sample rapidly but in the context
| he gave it (tournament poker) you would have a random amount of
| time more than a minute between decisions anyway so its fine in
| that context.
|
| [1] From a game theory point of view, it can be shown that in
| games with randomness and hidden information like poker, the
| optimal strategy is a Nash equilibrium in mixed strategies
| which means you need to sample a probability distribution to
| choose your actions in this way.
|
| [2] before looking. This is important.
| bno1 wrote:
| Isn't inverse transform sampling even faster than ziggurat?
| Most languages have an approximate erf^-1 implementation,
| everything is straight forward from there. I needed to
| generate random numbers from a truncated normal distribution
| and found inverse transform sampling easier to implement than
| trying to understand and adapt the ziggurat algorithm.
|
| A nice blog on this:
| https://stackedboxes.org/2017/05/01/acklams-normal-
| quantile-...
| seanhunter wrote:
| Quite possibly. Iirc the benefit of ziggurat is that you
| get a "real" Gaussian with infinite tails in both
| directions vs inverse transform truncates it but it has
| been a very long time.
| weinzierl wrote:
| This is about an interesting way to produce a pseudo random
| sequence. From the title I was expecting something a little
| different, more akin to Diceware [1], but without dice. Thinking
| of random numbers, but debiasing with John von Neumann's method
| sprung to my mind.
|
| [1] https://en.m.wikipedia.org/wiki/Diceware
| bsza wrote:
| We might be bad at generating _uniform, independent_ random
| numbers, but I submit that we're still capable of generating
| _some_ true randomness. Perhaps take the best of both worlds and
| mix in new entropy at each step? Something like, take the
| previous 2-digit value, add a "random" digit and generate the
| next output from that?
| aquafox wrote:
| I've memorized the first 130 digits of pi. Should be good enough
| for most tasks that require a human RNG.
| mark-r wrote:
| Same here. There's that long string of 9's in a row, but that's
| well beyond 130 digits.
|
| I can recite pi faster than a person can make up random digits.
| Try it some time and see how fast you start to totally run out
| of randomness.
| basil-rash wrote:
| Technically any RNG should be very able to produce a king
| string of the same digit, and artificially filtering that out
| would be a very bad sign indeed.
| keepamovin wrote:
| I've always been partial to Von Neumann's middle square method
| myself.
|
| https://en.wikipedia.org/wiki/Middle-square_method
| robobro wrote:
| Huh, I remember writing that python snippet for the page about
| 10 years ago. Nice to see it's still there!
| memming wrote:
| I used this to shuffle my MTG deck when I was a kid.
| zanfr wrote:
| why just use the center digits all the time? just randomize it
| too
| alanbernstein wrote:
| Here is my idea: pick a longish phrase of words, "at random". A
| song lyric, a book quote, etc. Count the number of words or the
| number of letters. Apply modulus if necessary. Repeat.
| andrewla wrote:
| I often use the Fibonacci numbers mod 10 when I need to do this
| in my head. It isn't great -- odd numbers are twice as frequent
| (because mod 2 they're [1,1,0]) and you get sequences like
| [7,0,7,7], but easy to keep track of and the cycle is 60 elements
| long.
|
| The other one I use sometimes is the powers of 2 mod 100 and use
| the leading digit. This gives a cycle length of 20 with a flat
| distribution.
| librasteve wrote:
| can try that in raku like this
|
| > (1, 1, * + * ... Inf)[^42].pick mod 10
| gilbetron wrote:
| One I use for random gaming needs, but requires two brains, if I
| want to emulate a dN die (d6, d10, d20, whatever) is I think of a
| number between 1 and N, and the other person does the same. Then
| add them together and mod by N. Works well enough, although you
| can get into game theory and the results aren't very random
| because we tend to pick certain numbers.
|
| Thinking about it, I wonder if both people picking multiple
| numbers and adding them all up mod N would improve things.
| jetrink wrote:
| > Thinking about it, I wonder if both people picking multiple
| numbers and adding them all up mod N would improve things.
|
| I bet that our bias against clustering and repetition when
| creating a pseudo-random list of numbers would mean that a list
| would be less random than an individual pick. As a simple
| example, if picking two numbers, people would probably be more
| likely to pick one even and one odd number than two even or odd
| numbers, since a mix of even and odd feels more authentically
| random, resulting in an excess of odd sums.
|
| As an alternative, what if each person created a short list and
| then blindly chose one number from the other person's list?
| RugnirViking wrote:
| blindly picking from a shortish list of values then doing the
| addition and mod thing only seems better than the naive case
| of blindly picking from a list of 1 to N when we are talking
| about large values of N
| drdrek wrote:
| When I want to be random enough I pick a large number than mod by
| another random number that is bigger then the max option. (mod
| again in the max number if needed) This seems unpredictable
| enough I've been unable to see any patterns in it.
|
| lets say you need to pick a number from 1 to 20, if you take 1235
| and mod 22. mod is easy to do in your head as you can just
| subtract in steps until you get there. so 50 times 22 is 1100, we
| are left with 135. 5 * 22 is 110 so we are left with 25. 25 - 22
| is 3.
|
| I picked 3 and I would be hard pressed to guess it would end up
| 3.
| sega_sai wrote:
| Great method! It's better though to choose prime numbers for
| mod X operation, that'll make biases less likely.
| chrisshroba wrote:
| In your example, 1 and 2 are twice as likely as any other
| number, because of the 22 possible results of n%22, 3 through
| 20 all only have one result that yields them, but 1 gets
| generated by 1 and 21, and 2 gets generated by 2 and 22. You
| could adapt your algorithm by adding "if the result is greater
| than the range of values you're picking from (i.e. 21 or 22 in
| your case), try again with a new number." >>>
| import collections, random, pprint >>> pprint.pprint(
| sorted( list( collections.Counter(
| [ ((random.randint(1,10000000) % 22) % 20)
| for x in range(10000000) ]
| ).items() ) ) ) [(0,
| 908920), (1, 908264), (2, 454167), (3,
| 456019), (4, 454551), (5, 455183), (6,
| 454127), (7, 454308), (8, 454939), (9,
| 454602), (10, 454963), (11, 453117),
| (12, 454046), (13, 453812), (14, 456243),
| (15, 455025), (16, 454101), (17, 455072),
| (18, 454409), (19, 454132)]
| bumbledraven wrote:
| This is the most in-depth analysis of Marsaglia's mental PRNG
| I've seen.
|
| A question, though. The author writes:
|
| > So what other numbers work? ... if n is a good multiplier, then
| the period of the orbit starting from 1 should be 10n - 2.
|
| > (2 3 6 11 15 18 23 27 38 39 42 50 51 62 66 71)
|
| > The last interesting number is 18. It has a respectable period
| of 178 and has every possible digit transition. The downside is
| that you have to learn the 18 times-table. This isn't too bad: I
| internalized it with maybe 10 minutes of practice.
|
| Why is 18 the "last" interesting number? The largest number on
| the list, 71, has a period of 708 (10n - 2). Given that he is
| willing to memorize the first 10 multiples of a 2-digit number,
| why didn't he choose 71 over 18, which has a period of only 178?
|
| The 2-digit transitions for 71 are pretty evenly distributed:
| 7 7 7 7 7 7 7 7 7 7 7 8 7 7 7 7 7 7 7 7 7 7 8 7 7
| 7 7 7 7 7 7 7 7 8 7 7 7 7 7 7 7 7 7 7 8 7 7 7 7 7
| 7 7 7 7 7 8 7 7 7 7 7 7 7 7 7 7 8 7 7 7 7 7 7 7 7
| 7 7 8 7 7 7 7 7 7 7 7 7 7 8 7 7 7 7 7 7 7 7 7 7 7
| librasteve wrote:
| in case you were wondering, raku DOES have built in proper random
| number generation: > (^6).roll #picks a random number from range
| 0..5
___________________________________________________________________
(page generated 2024-01-23 23:02 UTC)