Hacker News Reader

Comment by Patient0 | Hacker News Reader

I disagree - I think if you described this to a layman they would always be more interested in optimising for the worst case. For example if I had an algorithm that on average will get me out in 1 mile but in the worst case might take me 100 miles then that's not very useful if I was trying to decide how much supplies to take.

The concept of an arithmetic mean is quite artificial - there's other ways you could define "average" such as the median.

Also, in my experience, optimising for the average case is often the easier problem to solve.

View on HN

> The concept of an arithmetic mean is quite artificial - there's other ways you could define "average" such as the median.

I'd give some pushback on that. It is the only linear mean, and linearity matters.

More importantly though, it corresponds to the Expected Value. That is, the average of n samples of a distribution f converges to E[f]. In fact, I believe the arithmetic mean is the best unbiased estimator for the expected value of a distribution.

Now, expected values matter because they are the basis of robust decision-making.

You can consider mean, mode, and the other centrality measures as points that minimise some sort of average deviation. And depending on which norm you use to measure your deviation, you get different centrality measures:

* L_0 -> mode

* L_1 -> median

* L_2 -> mean

* L_infinity -> midrange, I think

where roughly L_p(x) = [ sum_i |x-x_i|^p]^(1/p) ]

Among these norms, again the L_2 norm stands out. It being the standard measure of distance. Here, it is important because it is invariant under rotation. We can define rotation without any appeal to length as the "special linear group". This consists of all matrices that have determinant 1.

I wonder where exactly the connection between 'rotation invariance' and 'estimate of the expected value' comes from.

What is the practical benefit of betting you landed in the worst spot? When computer scientists talk about Quicksort, we regularly talk about it being a O(N*LogN) operation. But by this logic, we should be treating it as N^2. That doesn't make sense, because in practical applications, we generally are dealing with random inputs, not adversarial inputs.

I'm not convinced what a lay-person is interested in solving matters. We're talking about Bellman, who is a mathematician and well known for attacking problems relevant to computer scientists. A lay person would just bring a compass and call it good.

Plus, it would depend on the probability measure over your initial position and orientation. It might seem obvious that you'd want it uniform over location and orientation, but you could argue that a more realistic measure would be obtained by eg picking a point on the boundary, then picking a direction, then looking for the next exit in that direction, and picking a point uniformly on that line (or exponentially with rejection if you end up outside), etc.

Reply on news.ycombinator.com