Hacker News Reader

Comment by hanbura | Hacker News Reader

>Google, for not being able to, "prove a random number is truly random,"

I really hope they just wanted you to argue that the task is impossible.

Reminds me of a question one interviewer asked me to do at the very beginning of the session when I did my first onsite at Google - write a regex for emails. I told him no, and explained why. He then asked me to write a naive email regex to catch a simple situation, which I subsequently did.

This makes sense as an interview question.

Will the interviewee push back when asked to do something impossible?

Will they then demonstrate that they can do some simpler case (which will minimize mental switching costs for both the interviewee and interviewer)?

Writing a regex at a Google onsite? For SWE?

I actually would argue that a single number alone is always random. This is because a pattern is a recognizable arrangement of elements. A single number is a single element and cannot be arranged, and so it has no pattern. Since the definition of randomness is the lack of a pattern, and a single number can never have a pattern then a single number is always random.

Yeah, my first reaction to that prompt is "it can't be done. Saying whether or a not /a/ number is random is meaningless, only sequences of numbers can be treated with statistical methods"

Or maybe bring up some heuristics (https://en.wikipedia.org/wiki/Diehard_tests) – but of course proving a negative is always a futile exercise.

You can't run statistical methods on a single number though

> I really hope they just wanted you to argue that the task is impossible.

Pretty dumb fucking thing to ask a front end engineer to do, if you ask me.

If the last 'n' generated numbers were also given to you, this seems like a fair task - to check the randomness of a sequence of numbers. Wikipedia has an article about "randomness tests". [1]

An example algorithm could determine if a run of integers represents a random sequence with some probability 'p'.

[1]: https://en.m.wikipedia.org/wiki/Randomness_tests

Those tests can "disprove" that a sequence is random (quotes because of course a true random generator will occasionally generate suspicious sequences of arbitrary length)

But you can't prove that a sequence is indeed random: the sequence [sha256(1), sha256(2), sha256(3), ...] passes the usual tests and isn't even clever. For any set of tests you can write a pseudo random generator that passes them

To prove a random number is truly random you would have to prove the random number generator that gave it to you is truly random.

If the output was plotted (from the minimum possible output to the maximum) and run a sufficient number of times, I would expect the chart of the output to have a very good distribution, and not have any serious hotspots.

To prove this, my solution would probably go something like: Probability of number N being output = 1 / MaxPossibleNumber

Then I would run a test a sufficient number of times (depends on what MaxPossibleNumber is) such that as the amount of numbers generated approaches infinity, the percentage of times any particular number is output approaches 1/MaxNumber.

The harder part would be making sure sequences of numbers don't repeat. In addition to looking at the total distribution, I think I would also want to log the order in which the numbers were generated and then run an algorithm that looks for sequence repeats.

I am NOT familiar with how random number generators work, so this is a naive solution off the top of my head and could be completely wrong, but w/e.

It's not impossible: make a dice with all the numbers up to that number; throw the dice until it falls on that number; done.

Define a PDF thus:

1 when n = number, 0 everywhere else

Won’t that be true for any number though? Might as well cut out steps and say accept all numbers as random.

Of course. But now you proved it.

Reply on news.ycombinator.com