4 ms·
The Birthday Paradox – On Jupiter, and Beyond (2012)
- jedberg 8y agoFor those of you who read the comments before the article, this is actually about calculating hash collisions and is pretty interesting.
- ColinWright 8y agoThank you.
- cbsks 8y ago>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?
- robinhouston 8y agoI 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.
- ColinWright 8y agoIn 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_other_names_for_the_exclamation_mark https://en.wikipedia.org/wiki/Exclamation_mark#Slang_and_oth...
- cbsks 8y agoDon’t forget about interrobang, aka “?!” “Shriek” is a new one to me, however. What context is it used in?
- ColinWright 8y agoFrom 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 https://en.wikipedia.org/wiki/Exclamation_mark#Computers [1] https://www.thoughtco.com/multiple-exclamation-points-1691411 https://www.thoughtco.com/multiple-exclamation-points-169141...
- blackholesRhot 8y agothe 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 https://projecteuclid.org/euclid.ss/1177012015
- resource0x 8y agoRelated: 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];
- pavel_lishin 8y ago> In fact, you need much less How many iterations does that take on average? And why?
- resource0x 8y agosee https://math.stackexchange.com/questions/1409862/average-length-of-a-cycle-in-a-n-permutation https://math.stackexchange.com/questions/1409862/average-len... Which gives you 1000/7.48, not 1000/2
- saagarjha 8y agoThis seems to tend to 500 when I run this experimentally.
- resource0x 8y agoIndeed. Never tested it before, took the article in stackexchange for granted.
- deleted 8y ago[deleted]
- bogomipz 8y agoI 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?
- ColinWright 8y ago"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 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.
- bogomipz 8y agoYes 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.