Hacker News Reader

Comment by RuggedPineapple | Hacker News Reader

>Can you roll a fair die a thousand times and only get 6s? Well yes of course. It'll never happen though.

Somewhat related, but humans are also REALLY bad at generating randomness and one of our big tells is an aversion to repeats. If you ask someone to pick 0-9 randomly, repeatedly, they will rarely repeat numbers. But in a truly random sample a repeat is likely 10% of the time, and a three-peat will happen roughly once every 100 numbers. An average person will rarely if ever repeat a number and sure as heck won't ever come up with it three times in a row.

View on HN

Then again i had exactly this in mind and in OP tasks i did repeat a number here and there.

Yeah but even then most people cap the repeats if they’re faking. If 100 people have to roll 10 random numbers, it is very likely some people will have 3-4 in a row of the same number. It’s less likely none will. My brother in law teaches stats and he runs this scenario with a seminar he teaches. He then runs the results through a simple formula he built in excel and can ascertain who faked vs. did it for real with about 95% certainty IIRC. I love little games like that haha

And funnily enough, you'll often hear this trait as being desirable in a pseudo-random number generator. People often want something that will jump around fairly unpredictably but that will come close to outputting all possible numbers once before getting into re-runs.

I’ve coded up this exact algorithm, it’s really fun. It’s useful for “shuffling” in the music sense (not the cards sense).

I think it’s actually the prototypical real-world software engineering problem. User says they want X (random music). X is a term in software, so you give them that (you get a random song). They’re not happy. You dig and find out they really want A, B, and C (next song is unknown, songs don’t repeat too soon or too infrequently). This new problem is harder to verify (how soon is too soon?).

Editing in tips on solving this sort of problem. You can turn vague requirements into precise requirements. Rather than make the precise requirements exactly equivalent to the vague ones, it's easier to make them more restrictive. Is playing a song again within 50% of the length of the playlist "too soon"? Maybe. How about within 80% of the length of the playlist? Definitely not. We can give ourselves the requirement "Songs must always play again between 80% and 125% of the length of the playlist." Much easier to solve, much easier to test.

Sometimes the extra restriction make the problem harder (not usually I've found). Still, this is a great trade because understanding requirements is harder than solving well defined problems.

[To the point of this whole post] Requirements can be turned into testable properties even if it's not programmatic. "When I look at a list of chosen songs, there must be no obvious patterns." Who says what's obvious? You do! Then, have someone else do the same.

Consider extreme cases. Extreme cases tend to be the most or least important. If they're least important, create a new set of easier requirements or drop it all together. "If 3 - 10 songs, always play within double the playlist, no obvious patterns, never twice in a row. If 2 alternate, if 1 repeat."

I actually had an engineering ask from somebody to produce "random sequences" which turned out to be anything but random. Short version: letter sequences, no repeats in a sequence or in adjacent sequences.

Took months and a lot of patience to extract that crucial piece of information from the customer. I actually coded a recursive algorithm which to my surprise generated every possible (three letter) sequence in an acceptable sequence, enough for them for several lifetimes.

> Extreme cases tend to be the most or least important.

Yeah, that's my suspicion.

There's an overlap in meaning between random, strange and unknown. "This random guy came up to me..." Keeping that in mind helps when talking to people about "random".

Yes, it's a very desirable trait in https://en.m.wikipedia.org/wiki/Quasi-Monte_Carlo_method

Quasi-Monte Carlo has a rate of convergence close to O(1/N), whereas the rate for the Monte Carlo method is O(N^(−0.5))

For such applications it's best to use quasi-random numbers (a.k.a. low-discrepancy sequences) such as the Halton sequence or the Sobol sequence instead of pseudorandom numbers.

Thank you for the link - I had not heard of this kind of sequence. It looks like something I'd like to know about, but I think it's beyond my schoolboy-level mathematical abilities. Anyway, I guess I'll have a peek in the rabbit-hole.

What is an example of a situation in which this is desirable:

> come close to outputting all possible numbers once before getting into re-runs

In a dice rolling game, you want as close to true random as your PRNG can get. In card drawing, you typically want EXACTLY all possible cards once before getting "repeats". Where do you want something in between?

> dice rolling.... card drawing...

What you're talking about is "with/without replacement".

Last time I encountered this was creating random IDs for things, either as a random string of characters or when selecting from lists of attributes and animals like all the tools that'll name things like "curious possum". It's not actually a hard requirement to hit every possibility before repeating, but if you do see 2 or 3 clusters in a sample it gives people the impression it isn't random.

Reply on news.ycombinator.com