Generating random spheres

So when I was in the shower earlier and I wondered to myself “Hm. How would I generate random points on an N-sphere?” (true story).

I thought about it for a bit and generated the two obvious solutions. Unfortunately the two obvious solutions are, respectively, wrong and massively inefficient (actually the inefficient one isn’t too bad for low dimensions, but I was interested in the high dimensional case where it rapidly becomes massively inefficient). Once out of the shower I looked the answer up, and found the whole thing interesting enough that I figured someone else might too, so this is a post about that.

Obvious but wrong solution

Generate N random uniform numbers between -1 and 1. Divide the resulting vector by its norm.

Why is this wrong? Well, the initial N random numbers will lie uniformly in the N cube. So the probability density at a given point is proportional to the length of the line that goes from the zero, through that point and out to the N sphere. This line is not of uniform length for the very simple reason that cubes aren’t spheres.

Obvious but slow solution

Generate N uniform random numbers between -1 and 1. Retry this until the resulting norm is <= 1. Divide the resulting vector by its norm. Why does this work? Because we're using a rejection method to make sure we get points inside the unit ball. The result is not uniformly distributed inside the unit ball but it is (evidently) spherically symmetrical. By dividing by the norm we’re then projecting the spherically symmetrical distribution onto the sphere and thus getting a uniform distribution on it.

Why is it slow? Because of the curse of dimensionality. When we do the rejection we’re effectively generating a geometric distribution with probability of success equal to the proportion of the N-cube the N-ball occupies. This means we expect to perform the generation 1 / that probability times, which tends towards infinity quite rapidly as N gets large.

Obvious in retrospect solution

At this point I looked up the answer, though I should have been able to figure it out.

What we want is a spherically symmetric distribution a la the previous solution but which is more efficient to calculate.

It turns out that a good choice for this is an N dimensional normal distribution, which can be obtained by simply generating N Normal(0, 1) random variables. You can then divide by the norm of those variables and get a distribution on the unit sphere.

This is apparently not the best solution (generating normal random numbers is a little expensive), but I couldn’t find a reference to a version which works in N dimensions for any N.

Here’s some C code implementing this: https://gist.github.com/1354700.

Constraints for wish construction

Charles Stross has recently had two posts about your classic “three wishes” style problem. The only constraint he lists is “No, you do not get to wish for further wishes”

Of course if you give a geek this constraint they will immediately do their best to subvert it.

His wishes:

1. That the outcome of my three wishes will be positive for everyone affected by them (with the definition of “positive outcome” provided by the individual so affected),

2. That anything that can be obtained by one of these magic wishes can be obtained by non-magical human efforts,

3. That nobody ever gets any more magic wishes

Personally, I feel this is cheating a bit. Anything which messes with the mechanism of wishing to this extent really feels like it’s violating the spirit of “No wishing for more wishes”. So I started thinking about how I would construct wish provisioning systems that were immune to this sort of twisting.

The following is the rules set I came up with:

The implementer of the wishes is completely unable to use its abilities outside of the constraints of wishing. No coercion to obtain more wishes is thus possible
Wishes are magical. That is, non-physical.
Wishes may only have physical effects (effects solely in peoples’ minds count as physical. A Cartesian dualist I am not. Similarly the provision of information is totally kosher – he just hands you a book or a hard drive or writes the information into your brain or whatever) and things created as a result of wishing may not have any magical effects (no wishing for a second genie)
In particular, while the mechanism for implementing wishes is not subject to physical laws, the results must be. There is no ongoing magical intervention to maintain the results of the wish

So essentially we have a two-category system for effects: While the genie may use its magical powers to achieve any physical effect, the effect of wishing is not subject to that.

In the case of a magic lamp where there is a token you can pass from person to person you are of course still able to get infinite wishes by e.g. wishing for an army of utterly loyal minions and passing the lamp from minion to minion. This is a problem easily solved by requiring an ever-growing cool-down time between new owners, which at leasts drastically limits the rate at which wishes can be performed.

Ethical Calculus

This is an idea that’s been brewing in my head for a while. I was waiting for it to be more fully formed before posting it, but it doesn’t seem to be going anywhere so I figured I’d just throw it out now and see what people thought. Hence this is largely a collection of half formed ideas.

The idea is this:

We have some sort of value function which measures something good about a situation for an individual. This isn’t necessarily the economists’ magic “capture everything this person cares about” sort of value function (I don’t believe in those). This is something more concrete like “life expectancy” or “cost of living adjusted wealth”. All that we care about is:

A value function f takes an individual i and an event E and assigns a real valued score f(i, E)
All other things being equal, if f(i, E) < f(i, E'), E' is "better" for that individual than E

The question is this: Given such a value function and a population, how should we create a corresponding value function F which captures the best behaviour for the population? Note that it is extremely likely that the answer to this depends on the choice of f.

(Note that it is not a priori obvious that it is reasonable to do so. I suspect it is not, but that there may be useful group value functions we can assign)

The traditional measure used by certain groups (who I shall not name lest they appear) is that of averaging the values. i.e. given a population P we choose

F(P, E) = 1/|P| sum_{i in P} F(i, E)

I consider this to be a terrible choice. Why? Because it’s completely insensitive to value distribution. If you “steal” value from someone and give it to another person, F doesn’t change. Thus F is entirely ok with the exploitation of the poor at the hands of the rich, for example.

So if we don’t like that, what do we like? How do we go about choosing a good way of assigning F?

I claim that this is an ethical question, and that the decisions you make have to be heavily informed by your code of ethics.

Do I have a concrete proof of that? No, not really. I don’t think I could provide a proof of that without an actual definition of code of ethics, and I thing it would end up a bit circular. But most of the reasons I’ve ended up judging specific examples as unacceptable are purely ethical ones – e.g. consider the reason I dislike averaging.

Let’s consider some other ethical aspects and perhaps you’ll see what I mean.

Let Q be some subset of the population P, and suppose I define F(P, E) = F(Q, E).

Consider Q to be “white people” or “men”.

That seems like a pretty awful way to judge value for a population, doesn’t it?

It could of course be even worse. You could define F(P, E) = F(Q, E) – F(P \ Q, E). i.e. doing good for anyone outside that group is considered actively disadvantageous.

So here’s a perhaps reasonable ethical principle:

Call the privileged population of F the set of individuals i such that

Increasing the value of f(i, E) by varying E in a way that does not change f(j, E) for any other j does not decrease F
Increasing the value of f(i, E) by varying E in a way that does not change f(j, E) for any other j may under some circumstances increase F

A not unreasonable principle of equality is “the whole of P is privileged”.

You could define a much stronger principle of equality: Swapping the scores of any two individuals should not affect the value of F. This is the most extreme (and probably the most fair) form of equality I can think of in this case.

It’s worth thinking about whether you actually agree with these principles: For example, what happens if you let the privileged population be “The set of people who are not serial killers”. Even if you wouldn’t support them being unprivileged for things like “life expectancy” if you’re anti death penalty, chances are good you’d not want them to be given the same treatment under freedom of movement.

(Of course, letting serial killers go free violates the “all else being equal” aspect of these considerations, so maybe you would).

Another perhaps reasonable principle can be extracted from the “privileged population” definition I had above. It contained an implicit assumption: That increasing an individual’s score should never decrease the overall score.

Do we agree with that? I don’t know. Consider for example the example of a large population living in abject poverty ruled by a well off elite. Is it really worse to have the elite better off? I don’t think it is, although I don’t necessarily think it’s better either – the problem is the massive poverty rather than how well off the elite is.

Beyond that, I’m not really sure where to go with this, other than to provide some examples of possible solutions:

Minimum value of f(i, E)
Maximum value of f(i, E) (this would be a pretty hard one to justify ethically)
Indeed, any x% mark of f(i, E). i.e. the maxium value such that at least x% of the population have this value. This includes the median value
The mean value
Any convex combination of otherwise acceptable values. For example the sum of the minimum and the median

Unsurprisingly, most of these look like averages, and most averages should work. Note however that the modal value doesn’t satisfy the principle that increasing the value of an individual shouldn’t decrease the value of the population.

Where am I going with this? Beats me. This is about as far as I’ve got with the thought process. Any thoughts?

New Blog: Imbibliotech

This is just a quick note to say I have a new blog called Imbibliotech.

This is not a replacement for the current blog – it’s a subject specific blog on the topic of drinking (primarily cocktails and spirits, but also other things including coffee), as I’m doing a bunch of learning and experimenting on that subject which I felt would be better posted elsewhere.

Gin!

I drink a lot of gin and tonics. Mostly this is a function of the fact that I don’t drink beer, rarely drink wine and, while I like a good cider, am rarely in the mood for it.

That being said, I’ve always really liked the gin and tonic. It’s a nice drink.

When talking with Ryan Alexander over drinks one evening, he reported some experimentation he’d done, trying to find the best gin and tonic combination.

This struck me as a good idea. I must admit, most of the gin and tonics I’ve consumed in my life have been schweppes and bombay sapphire. It’s a perfectly serviceable drink, but surely with better ingredients it could be a better drink?

So I set forth and bought lots of nice gin and some nice tonic water and began to experiment.

As it turned out, what I discovered is that I really like gin without the tonic water. Once you use a decent gin, it has much more possibilities than just drowning out the flavour with quinine and sugar. Don’t get me wrong, I still really like gin and tonics, particularly if you use one of the more spicy gins, but I also really like neat gin, and martinis.

The following are the gins I have tried over the last few weeks:

Whitley Neill
Sipsmith
Tanqueray No. 10
No 3. London Dry Gin
Sacred Gin
Aviation
Dry Fly Gin

I’d also previously had:

Hendricks
Tanqueray export strength
Bombay sapphire

Of the new ones, the only one I really didn’t like was the Dry Fly. It has weird overtones of whiskey and salt (really. It’s based on a wheat liquor and actually does have added salt). I feel like there might be something it’s good in (I keep meaning to try it in a ruddy mary), but I’ve not found it so far.

The ones I would recommend unreservedly are the Whitley Neill and the Sipsmith. The Whitley Neill is quite mild – don’t use it in a G&T, it will drown, but it’s very nice neat and quite good in a martini. The Sipsmith has a similar flavour to it, but much more of a kick (tastewise – they’re about the same in alcohol content with the Whitley Neill actually fractionally stronger). It seems to be very versatile – it produces good martinis, good gin and tonics and is rather nice neat. If I were drinking the gin neat I’d probably choose the Whitley Neill, but for the other uses the Sipsmith seems nicer to me.

(Side note: As you’re probably noting, this isn’t a proper formal alcohol review. This is more just “This is what I tried, these are what I liked”).

For gin and tonics, the combination I’ve been really liking is the Aviation with Fever Tree tonic water. The Aviation is quite spicy (though less so than the Tanqueray) and so the flavour is easily discernable through the otherwise quite strong tasting Fever Tree.

The Sacred gin is nice, but until today I’d not found anything I really liked it in – it has a bit of an odd flavour neat, and I felt that while it was nice in a G&T it wasn’t really living up to its promise. Today I tried it in a classic martini (about 3 parts gin to 1 part vermouth) with Noilly Prat vermouth, which was excellent. This may be my new favourite Martini (although admittedly I’m not yet a connoisseur of the subject).

All told, this has been a really good learning experience. Gin is much more interesting a drink than I had previously realised, and significantly more versatile.

The only downside is that I now have ten bottles of gin in my flat. Oh well. Bottoms up!