Hacker News Reader

Comment by mrleinad | Hacker News Reader

Yeah, can't imagine how this submission made it to the front page of HN.

I think it's fairly understandable why - of all of Asimov's shorts - The Last Question tends to have so much gravity with HN readers. For those that haven't read the story before, I can also see why it's worth the up vote. I do find it perplexing, however, to learn how many times it has landed on the front page. This is personally the third time I've found it front page in the last 3-4 years - and I'm not a die-hard HN reader.

At any rate, given how many readers are probably new to the The Last Question, it's probably worth citing another Asimov piece that is oft-mistaken for The Last Question - The Last Answer. It's a more recent work, and a bit more obscure, but worth the read if you're into Asimov.

http://www.thrivenotes.com/the-last-answer/

I can't tell if you're being sarcastic or not. If you are, then please consider that myself and many others feel that linking to previous submissions is a service, since it's interesting to see previous discussions.

Things have a tendency to resurface. I personally had not read it before. Though since the HN search is so good (Probably in the top ten I've seen so far for content search on a site.) theres not as much of an excuse for resubmission.

An implementation of exponential decay could quite possibly solve this problem, but it might mean that they'd have to dramatically rethink the "new" page.

Exponential decay is important because it is, as they say in statistics, "memoryless": it has a simple geometric property that adding a new point today has the exact same effect as adding a new point on the first day. It can therefore be implemented as follows: when you add points to a link, you add them not just to the total points, but also to some accumulator which I will call Hotness. This number is a double; we increment by 1 when someone adds a point.

Every half-hour, some independent process working over still-Hot threads multiplies their Hotness by 0.97153. This gives a half-life of about 12 hours: your rating has hotness 0.5 after half a day, 0.25 after a whole day, and so on. We could tune that if we wanted finer granularity. When something gets below 0.001 Hot we can probably just reset it to 0 Hot abruptly so that we don't check it anymore. (Because doubles will try to go to -infinity if you use them multiplicatively in this way, and if you get to, say, 1000 points this will still mean that we can stop paying attention to you in, say, 10 days.)

Suddenly, adding points to a dead article is the exact same as sponsoring a new article. So we store articles under their URLs as keys, and if you resubmit an existing news story you merely bump it up to 1 Hot.

The "new" page would be very peculiar in this system, though. It might work by listing only those 1 Hot posts which were 0 Hot previously, I don't know.

As for a major con to this approach, I think HN uses polynomial decay rather than exponential decay because exponential decay somehow didn't feel like it had the right "shape" to it or so. This is probably because they didn't implement it in the "memoryless" configuration, though, where each point has value 1 from the moment it's added, and decays slowly.

Better still, increment hotness by 2^(dt/λ) where dt is the time since the site was launched (epoch), and λ the halflife of an upvote. No worker process needed.

Doubles will go to infinity after a few years, but you can either reset the epoch at that time, or store the significand and the exponent seperately.

I agree partways with what you're saying; the normal fears of losing precision in your floats don't really apply because you're always adding the smallest numbers first. On the other hand, your worker process is still in my view a worker process, processing every article by multiplying its hotness by 1.77e-220, and resetting t0. I mean, I believe it's a single SQL query, so it probably shouldn't impact site performance too much even for databases as large as Hacker News, so I'm not so worried about the sudden inconsistency while the worker is doing its thing -- but it's still a dedicated thing-on-the-side which has to be scheduled e.g. via cron job, and which you'd have to audit every once in a while to make sure that it did its job successfully and didn't accidentally get pushed out of sync by, say, server reboots.

An off-topic question: I've studied statistics in my course (engineering) but I haven't gone deep. I know the concepts superficially, like exponencial, polinomial and stuff.

In this situation: what book do you recommend to me? I want to able to reason a thought like that, more real-world stuff.

That's a little bit harder for me to answer, because I'm not familiar with anything which explained it to me the way that I presently understand it. Most of the really insightful books start with sigma-algebras and Borel sets, which are a little hard to understand at first and then get promptly ignored for most of the rest of the book. Basically, in some proofs you need to say that a statement is "almost surely" true because you can always add outcomes to which you assign probability 0, and you can often use those to 'technically' break a theorem.

I would say that the most key ideas for an engineer to know about probability and statistics are: (1) continuous random variables [i.e. a probability density f so that Pr(x < X < x + dx) = f(x) dx], and (2) the Dirac delta-function, which allows all of the statements about continuous random variables to carry over to discrete random variables and half-discrete half-continuous random variables and all of that stuff.

Once you know those, you can start to define mean and variance and you can begin to get a handle on independence [f(x, y) = g(x) h(y)] and how to add two random variables [int dx f(x, z - x) gives a distribution for Z = X + Y].

Most importantly, you get as a near-freebie this important theorem, which I very rarely see in the textbooks. It allows you to construct arbitrary random variables with Math.random(). let F⁻¹(p) be the inverse cumulative distribution function for a density f(x). Let U be uniformly chosen on [0, 1]. Then F⁻¹(U) is distributed according to f(x), Proof: because F is always-increasing, it the inequality x < F⁻¹(U) < x + dx is the same as the inequality F(x) < U < F(x + dx). Therefore Pr(x < F⁻¹(U) < x + dx) = Pr(F(x) < U < F(x + dx)) = F(x + dx) - F(x), due to properties of uniform distributions and the fact that F() is in both cases on [0, 1]. For vanishing dx, F(x + dx) - F(x) = f(x) dx, QED.

This actually also helps when you realize that U doesn't have to be chosen just once; you can also have a uniform sampling of (0, 1), and under the transform F⁻¹(p) that sampling will have density f(x). So if you wanted a density defined on [0, Z] for which asymptotically, f(10 x) = 0.1 f(x), but you also wanted it to be evenly spaced for x < b, then you might want density f(x) ~ 1 / (b + x), x > 0. Then you have F(x) = log(1 + x/b) / log(1 + Z/b), and inverting this gives x(F) = b [(1 + Z/b)^F - 1].

That's the function you would use to create a lattice of points distributed with this density, plugging in F = k/N for k = 0, 1, ..., N. It's a very useful theorem. ^_^

Once you can do that sort of stuff, your textbook should return to the basics of discrete events: Bernoulli trials (aka weighted-coin flips where heads is 1 and tails is 0), Geometric variables (the number of Bernoulli trials before you get a 1), Binomial variables (the sum of N Bernoulli trials), and their continuous limits (exponential, Poisson, Normal).

Don't get too caught up, I'd caution, on Normal random variables. They're useful but the standard-normal tables come with a lot of pointless overhead. (Most of the overhead goes away when you realize that a "Z-score" is the "number of standard deviations away from the mean." -- X = mu + Z sigma. And the rest of it is looking numbers up in tables and making sure that you look for where the table says "0" so that you know what area you're actually calculated.

The reason I'm saying all of that out loud is that I don't know a textbook which will give you all of that material, sorry.

Really thanks for this answer.

I didn't get very well the theorem you mention, but I'll ask a math guy friend of mine.

Many Kudos for you.

Agreed, though I'd say posts like this one are something of an exception; if you weren't already aware of the story, you wouldn't even think to search for it. So it serves as a sort of "hey, HN users, you might be interested in this" post, rather than a discussion area for an article which people might well find via other sources, and want to see discussions about.

Reply on news.ycombinator.com