The Birthday Paradox – On Jupiter, and Beyond (2012) | Hacker News Reader

The Birthday Paradox – On Jupiter, and Beyond (2012)

solipsys.co.uk

39 pointsColinWright16 comments

For those of you who read the comments before the article, this is actually about calculating hash collisions and is pretty interesting.

Thank you.

the authors are basically rediscovering Chen-Stein’s concept of Poisson approximation... which can be used to almost trivially approximate any birthday problem variant. For example, how many people do you need to have a 50% Probability that at least 6 people were born on the same day on Jupiter? Ez w/ Poisson approximation. I first learned about this in Persi Diaconis’ graduate probability class but the method is very simple

https://projecteuclid.org/euclid.ss/1177012015

>Just as a reminder, we use n! to mean n(n−1)(n−2)(n−3)...3.2.1, so that means 6!=6.5.4.3.2.1=720. The exclamation mark is sometimes pronounced "pling" and this operation is called "factorial".

I’ve never heard the factorial symbol called “pling” before, I think we pronounced “6!” as “six factorial” in my undergraduate math classes in the US. Is “pling” a common term that I completely overlooked? Or is it more common in the UK?

In various circles it can be called pling, bang, or shriek. These are names for the symbol, whereas "factorial" is the name for the function.

In particular the opening line of a (U|Li)nix script is:

    #!<path>

and that's sometimes called the "hash bang".

From wikipedia[0]:

    In the printing world, the exclamation
    mark can be called a screamer, a gasper,
    a slammer, or a startler.

    In hacker culture, the exclamation mark
    is called "bang", "shriek", or, in the
    British slang known as Commonwealth
    Hackish, "pling".

[0] https://en.wikipedia.org/wiki/Exclamation_mark#Slang_and_oth...

Don’t forget about interrobang, aka “?!”

“Shriek” is a new one to me, however. What context is it used in?

From Wikipedia[0]:

> The name given to "!" by programmers varies according to their background. In the UK the term pling was popular in the earlier days of computing, whilst in the United States, the term shriek was used. It is claimed that these word usages were invented in the US and shriek is from Stanford or MIT; however, shriek for the ! sign is found in the Oxford English Dictionary dating from the 1860s.

From another web site[1]:

> It is also called an exclamation mark or tellingly, in newspaper jargon, a shriek.

================

References:

[0] https://en.wikipedia.org/wiki/Exclamation_mark#Computers

[1] https://www.thoughtco.com/multiple-exclamation-points-169141...

I think it’s a rather old-fashioned British term. I haven’t heard it for years, but it used to be fairly common in sufficiently nerdy circles over here.

I have a question. Under the section "Where did that come from?" The author states:

>"But after a bit of futzing about I found it to be remarkably close ..."

And the number under the radicand symbol he shows "ln(4)"

What is this exactly? Why is it significant?

"ln(4)" is the natural log of 4, so it's the solution to the equation e^x=4, where e ~ 2.71828... also known as Euler's number[0].

Reading further in the post will explain where that quantity comes from, and why it's significant, but if you have any questions you can ask them via the comment box on the article.

[0] The constant "e" turns up in lots of places, you can read more about it here: https://en.wikipedia.org/wiki/E_%28mathematical_constant%29

The usual examples for how Euler's number turns up are to do with calculus and compound interest, but there are many other.

Yes of course, thank you. I am so used to seeing the word "log" written out in things like time complexity/Big O analysis that I forgot about the natural log - ln. Cheers.

Related: given a permutation of numbers 0..999, find out the position of a given number (e.g. number 5). It may seem that on average, you need 500 iterations. In fact, you need much less:

let index = 5; while (element[index] != 5) index = element[index];

> In fact, you need much less

How many iterations does that take on average? And why?

see https://math.stackexchange.com/questions/1409862/average-len... Which gives you 1000/7.48, not 1000/2

This seems to tend to 500 when I run this experimentally.

Indeed. Never tested it before, took the article in stackexchange for granted.

Reply on news.ycombinator.com