4by12

Hypercubes and Hamilton Circuits

The Ising model is a simple model used to describe a magnet: It consists of a grid of spins. Each spin can be thought of as a tiny magnet, and can have the value +1 or -1 (called ‘up’ and ‘down’). Two neighboring spins interact, having positive energy if they are in opposite directions (e.g. up and down), and negative energy if they are in the same direction. So, neighboring spins ‘want’ to be in the same direction, to minimize energy.

This model is used to calculate various properties of magnets. For example, suppose we want to measure the average magnetization of the grid in a given temperature. The magnetization of a specific state is just the sum of all the spin values in that state. So if all the spins are up and the grid size is 5×5, the magnetization is 25. To calculate the average magnetization, we’d have to know the probability of each state. We’d then multiply each state’s magnetization by the probability of reaching that state, and sum over all the states. The probability distribution is given by the Maxwell-Boltzmann distribution, an important result of statistical physics.

If the grid size is sufficiently small (up to about 5×5), we can actually go over all the possible states and calculate an accurate average value for the magnetization. What is the most efficient way of going over all the states? It is very convenient to implement this algorithm by flipping just one spin at a time. In this case, the most efficient algorithm would iterate over the possible states by flipping just one spin in each step.

Let’s think of a state as a series of bits, 0 meaning a spin value of ‘down’ and 1 meaning a spin value of ‘up’. We can think of this series as a binary number, and iterate the states by incrementing this number. For example, if the grid size is 2×2, then we can iterate as follows: 0000, 0001, 0010, 0011, 0100, … This method works, but it takes more than one spin to switch states (on average). For example, going from 0111 to 1000 requires 4 flips. It is easy to see that the average number of flips per step for a series of length n is approximately:

With the limit taken as .

Let’s try to improve on this. In a previous post, I noted that we can think of a hypercube’s vertex as a series of bits. So iterating over all the spin states is like walking on a hypercube, visiting all of its vertices. We want to flip just one spin at each step — that would be the most efficient algorithm. In the hypercube analogy, this is the same as saying we are allowed to walk only on the graph’s edges, because edges only connect vertices that differ by exactly one bit. So now we’re trying to find an algorithm that walks the edges of a hypercube, vists all the vertices, and vists each vertex exactly once. This is almost the definition of a Hamilton circuit, except we don’t have to go back to the first vertex at the end.

Trying it out for a 3D cube, it’s obviously very easy to do this: We can start at the top face and walk through the 4 vertices there. Then we can ‘climb down’ to the bottom face, and finish walking through the bottom 4 vertices. We can generalize this concept inductively: Given such an algorithm for an (n-1)-hypercube, we can use it to build an algorithm for an n-hypercube: Start with the vertex 0000…0, and use the (n-1) algorithm to go over all the 0xxx..x vertices. Let’s say the algorithm finishes at vertex 0111…1. Next, ‘climb up’ to vertex 1111…1, and run the (n-1) algo. backwards to go through all the ‘upper’ states, reaching 1000…0. We can even complete a full Hamilton cycle by climbing back down to 0000…0.

Of course, we have an algorithm for n=0, so inductively we get an algorithm for every n. This algorithm goes over all the states, using just one flip (or edge) for each step.

When I told my girlfriend about my discovery, she told me this was a well-known method called Gray code. Party pooper.

Posted in Mathematics | No Comments »

Benford’s Law

Benford discovered that in many sets of data, the leading digit is much more likely to be ‘1′ than any other digit. Take, for example, the population counts of nations. The most significat digit probabilities there are as follows:

The MathWorld article offers an explanation in terms of distributions that are invariant under changes of the measurement unit. I have to say, I wasn’t entirely convinced by that explanation. I’d like to offer a different theory that might account for this phenomenon.

Read the rest of this entry »

Posted in Mathematics | No Comments »

Polarizing Sunglasses

How much light to polarizing sunglasses block? To answer this, a couple of things need to be clarified. First, what is meant by ‘how much light’, and second, how polarization works.

To answer the first question, it seems best to measure the power that the sunglasses absorb, i.e. the energy-per-time. Light travels in waves of electromagnetic fields. The electric field has an amplitude, , and the energy delivered by the wave per unit time is proportional to .

Next, let’s tackle polarization. Mathematically, the electric field is represented by a vector. When the wave travels through a polarizer, the polarizer leaves intact only one component of the vector — the component that’s in the same direction as the polarizer. So if the electric field of amplitude E has an angle relative to the polarizer, the wave’s amplitude once it travels past the polarizer is reduced to . The vector also appears to rotate, but that doesn’t matter for our purposes.

What is the power carried by the wave once it gets past the polarizer? That’s simply the square of its new amplitude: . The polarizing sunglasses are of course a polarizer, so they have this effect on an incoming wave.

There’s just one obstacle left to overcome before making the calculation: All the discussion above waves assumes that the waves are already polarized in some direction before reaching the polarizer. But light hitting your glasses is generally unpolarized, so we have to account for that. Unpolarized light can be thought of as a sum of polarized waves in different angles, each with the same amplitude. To get the power absorbed by the glasses, we need to average over the possible angles:

Question: Why is the integration carried out between 0 and pi rather than 0 and 2*pi?

We conclude that using polarization, sunglasses reduce light power by one half.. Note that there are probably other mechanisms by which such glasses absorb light — this calculation only addresses polarization.

Posted in Physics | No Comments »

Composing Hebrew Messages in GMail

Hebrew support in GMail is a bit problamatic. You can align the text to the right and start typing in hebrew, but when you enter numbers or punctuation marks the text gets flipped. For example, you can’t end a sentence with a period, because the period jumps to the beginning of the line…

I found a simple workaround for this problem. First, align the text to the right as before. Then type in a hebrew word (e.g. you can enter your name if you use it as a signature). Press ‘Home’, and hit ‘Enter’ several times. Move up to the empty lines above the text and start typing. Problem solved!

Posted in Software | 2 Comments »

A Google plugin for deskbar-applet

I discovered Gnome’s deskbar-applet today. What a great tool! I wrote a Google plugin that allows you to search Google, use I’m Feeling Lucky, and get a word definition using ‘define:word’. You can download it here.

To install, simply extract this file in your ~/.gnome2/deskbar-applet/handlers directory.

To use the plugin, type the following in your deskbar:

• some search query searches google for ’some search query’
• luck(y) some site jumps to ’some site’ using I’m Feeling Lucky
• def(ine) ubuntu takes you to the definition of ‘ubuntu’

Posted in Software | 2 Comments »

Billiards Tip

Here’s a tip to improve your game.

Read the rest of this entry »

Posted in Physics | No Comments »

Superhero Survey

Turns out I’m Iron Man, according to this superhero survey:

(via Quantumm Pontiff)
Read the rest of this entry »

Posted in Random Thoughts | No Comments »

Chicken McNuggets

McDonald’s sells its Chicken McNuggets in groups of 6, 9, and 20. What is the largest number of McNuggets you can’t buy?

Read the rest of this entry »

Posted in Riddles | 1 Comment »

Last Exam of the Semester

Took my last test of the semester today, in Topology. It came after four days of intensive studying. Sometime during the second day I realized that I had underestimated the breadth of the material, and that I needed more time. So I went into a blitz that involved little sleep and much caffeine.

I can say now that all that studying paid off, as I was able to swing back at almost all the topological curvballs prof. Lapid threw at us. There was one question that stumped me though. Here it is. If you can solve it, more power to ya (and please let me know the answer!)

Let be a continuous, injective function from the sphere (that’s the unit sphere in ) to some metrizable space Y. Is the image necessarily homeomorphic to ?

Anyway, while studying I stumbled on a fun little something involving polarizing sunglasses. More on that in a future post.

Posted in Mathematics, Personal | 1 Comment »

An eBay Dispute

A month ago, I bought a pair of headphones on eBay from this seller. I payed 50 GBP for shipping. This is a very high shipping cost for such a small item. It should guarantee delivery within a week. A month has passed, and the item has yet to arrive.

I tried contacting the seller but he hasn’t responded. So I used PayPal to open a dispute. As I learned, disputes are handled in the following steps:

• You first open a dispute, describing your complaint.
• The seller and you have 20 days to work out your differences.
• If you can’t resolve the problem yourselves, you can escalate the dispute. PayPal then assigns their own fraud investigator who decides whether to refund the payment.

Filing the dispute finally got the seller to contact me. After a brief exchange, he refunded my payment in full.

In the past, PayPal’s handling of disputes received a lot of bad press. I don’t know if this is the result of a fundamental change for the better, but this incident has boosted my confidence in eBay shopping.

Posted in Personal | No Comments »