The AM-GM inequality

April 24, 2010

One of the most basic inequalities, the AM-GM inequality states that the AM (Arithmetic mean) of a series of real numbers is always greater or equal to the GM (Geometric mean).

Mathematically:

\frac{x_1 + x_2 + \cdots + x_n}{n} \geq \sqrt[n]{x_1 x_2 \cdots x_n}

A simplified case

If there are two elements in the series, the AM-GM states this:

\frac{x+y}{2} \geq \sqrt{xy}

The proof for this simplified case is quite simple:

\begin{array}{l} \frac{x+y}{2} - \sqrt{xy} \\ = \frac{x - 2\sqrt{xy} + y}{2} \\ = \frac{(\sqrt{x} - \sqrt{y})^2}{2} \geq 0 \end{array}

Now, however, it is not so obvious how to extend this proof to a set of three elements, or more. But there is a way, by induction, to prove this inequality for cases where the number of elements is a power of two.

The 2^k subcase

The base case states that the AM-GM inequality is true for n=2, or when the number of elements in the set is 2.

The method of inductive proof is proving a base case, 2^k, and proving that if this base case is true then the case where 2^{k+1} is also true. This would mean that the statement is true for all instances of 2^k.

Here the base case is n = 2^1, which we have just proved to be true. We can now prove that this is true when n = 2^2, or when there are 4 elements in the set: x_1, x_2, x_3, x_4.

The arithmetic mean, or AM of the set is

\frac{x_1 + x_2 + x_3 + x_4}{4} .

We can split this set into two halves. One contains x_1, x_2, and the other contains x_3, x_4.

The point is that the arithmetic mean of the arithmetic means of the two halves is equal to the arithmetic mean of the whole. Or,

\textrm{AM} = \frac{\frac{x_1+x_2}{2}+\frac{x_3+x_4}{2}}{2}

Notice that both of the two halves are of length 2, or in the general case, 2^{k-1}. Having already proved the previous case, we can say,

\textrm{AM} \geq \frac{\sqrt{x_1 x_2} + \sqrt{x_3 x_4}}{2}

This itself is another arithmetic mean. Applying the base case again:

\begin{array}{rcl} \textrm{AM} &\geq& \sqrt{\sqrt{x_1 x_2} \sqrt{x_3 x_4}} \\ &=& \sqrt[4]{x_1 x_2 x_3 x_4} \end{array}

So we have

\frac{x_1 + x_2 + x_3 + x_4}{4} \geq \sqrt[4]{x_1 x_2 x_3 x_4}

which was what we wanted to prove.

The process for proving this for a higher power of 2, such as 8, 16, etc, is very similar to what we have just done.

The n-1 subcase

If the number of elements in the set is not a nice and even power of two, the above proof does not work. Instead, we use induction again, but this time from top-down.

We try to prove that if the inequality is true for a set with n elements, then it is also true for a set with n-1 elements.

Let’s first prove a lemma.

Lemma

If the arithmetic mean of a set, x_1, x_2, \cdots, x_n is a, then

\frac{x_1 + \cdots x_n + a}{n+1} = \frac{x_1 + \cdots + x_n}{n} .

Proof

\begin{array}{l} \frac{x_1 + \cdots + x_n + a}{n+1} \\ =\frac{x_1 + \cdots + x_n + \frac{x_1 + \cdots + x_n}{n}}{n+1} \\ = \frac{\frac{(n+1)x_1 + \cdots + (n+1)x_n}{n}}{n+1} \\ = \frac{x_1 + \cdots + x_n}{n} \end{array}

This lemma simply states that if you have the mean of a set, adding the mean to the set itself and finding the mean again would result in the same mean.

Now let’s prove the inequality when n=3.

Let a be the arithmetic mean of the set. Then

\frac{x_1 + x_2 + x_3 + a}{4} \geq \sqrt[4]{x_1 x_2 x_3 a}

as we proved before. According to the lemma, we can substitute:

\begin{array}{rcl} \frac{x_1 + x_2 + x_3}{3} &\geq& \sqrt[4]{x_1 x_2 x_3 a} \\ a &\geq& \sqrt[4]{x_1 x_2 x_3 a} \\ a^4 &\geq& x_1 x_2 x_3 a \\ a^3 &\geq& x_1 x_2 x_3 \\ a &\geq& \sqrt[3]{x_1 x_2 x_3} \end{array}

This completes our proof.

Of course I’ve proved it only for n=3, but the same method can be used to prove for any number where it is true for n+1.

To prove this for any integer n, first prove by induction that this is true for some number 2^k. Then prove by induction, again, that it is true for 2^k-1, 2^k-2, \cdots, n.

This method of proof is called forward-backward induction. This proof was discovered by Augustin-Louis Cauchy.


Project Euler 280 (Revisited)

March 27, 2010

A while ago I wrote this blog post on this problem. The previous code was able to produce the answer in about 20 minutes, using several gigabytes of RAM.

You may want to read the previous blog post first.

There is a simpler and more efficient solution (used by inamori, zwuupeape, and many others).

The new approach

We do not need to know the exact value of the solution, only an approximate. This approximation has to be accurate only to six digits.

Any any step, there is a certain probability that the ant will reach the final state in that step.

Let’s call this function P(s): the probability that the ant will reach the final state on step s:

Hosted by imgur.com

At very small values of s, the probability is zero because it takes a certain number of steps to get to the final position. 44 is the smallest number of steps to get from the initial to the final position, and the probability increases from there.

But it only increases until a certain point. After that point, the probability decreases. After all, if we run this for thousands of steps, how likely is the ant to still not have reached the final position?

However, the graph continues forever to the right. Even after thousands of steps, there is still a chance, however small, that the final position hasn’t been reached.

Let’s define Q(s) as the weighted average of the probabilities of each value of P(s) from 0 to s:

Hosted by imgur.com

The expected value and the answer for this problem would simply be the weighted average for the entire graph.

Since s must be an integer greater than zero, we don’t have to do any integration with curves. A bit misleading because I’ve drawn P(s) and Q(s) as curves, when they are not.

But because Q(s) cannot be expressed algebraically, we cannot evaluate it as it approaches infinity. Instead, we pick a point that gives us enough precision:

Hosted by imgur.com

Either that, or we keep calculating the weighted average while increasing s until we have enough precision.

Calculating the probabilities

In order to calculate a weighted average Q(s), we need to be able to calculate P(s); while P(s) is the probability function for the final state, we’ll need to know the probabilities for the in-between states as well.

The probabilities of the states on step s depend most upon the probabilities of the previous step, s-1.

Hosted by imgur.com

So if on step s-1 there’s a 0.6 probability that we’re on state X, then on step s we should have a 0.3 probability of being on either Y or Z as there’s an equal chance of moving to either state.

And if multiple states can go to our state, we can get the probability by adding up the probabilities:

Hosted by imgur.com

Coding a solution

At first we start on the initial state, with a probability of 1 (certain chance) of being on it.

On each step we generate a new set of probabilities using rules I described above, and so on.

A lot of code is stolen from my previous work on this problem. The State class is essentially unchanged in this version.

Here’s the code:

import java.util.*;

public class Main{

	public static void main(String[] args){

		final int ITERATIONS = 2501;

		// Initialize probability map.
		// The initial step is 0, containing the initial position with a probability of 1.
		Map<State,Double> prevProbs = new LinkedHashMap<State,Double>();
		prevProbs.put(State.INIT_STATE, 1.0);

		// Distributions for the final state.
		double[] finalValues = new double[ITERATIONS+1];
		Arrays.fill(finalValues, 0);

		// Keep the time.
		long startTime = System.currentTimeMillis();

		// Loop counter is actually the step number of the next step.
		for(int step=1; step<ITERATIONS; step++){

			// Make new probabilities.
			Map<State,Double> nextProbs = new LinkedHashMap<State,Double>();

			// Loop through old probabilities and add
			Set<State> stateSet = prevProbs.keySet();

			for(State state : stateSet){

				// Probability of being on this state right now
				double stateProb = prevProbs.get(state);

				// List of next states
				List<State> nextStates = nextStates(state);

				// Probability factor for each of the next states
				double multiplier = 1.0 / nextStates.size();

				// Added value to each of the next states
				double added = stateProb * multiplier;

				// Now go and update all the state probabilities.
				for(State nextState : nextStates){

					// If we've got the final state, handle it separately.
					if(nextState.equals(State.FINAL_STATE)){
						finalValues[step] += added;
						continue;
					}

					// Could be the first time.
					if(!nextProbs.containsKey(nextState))
						nextProbs.put(nextState, added);

					// Might not be the first time.
					else {
						// Old value, we need to add to it instead of replacing it.
						double previous = nextProbs.get(nextState);
						nextProbs.put(nextState, previous + added);
					}
				}
			}

			// Our new probabilities are the old probabilities for the next loop.
			prevProbs = nextProbs;

			System.out.println(step + " " + weightedAverage(finalValues));
		}

		System.out.println((System.currentTimeMillis() - startTime) + "ms");
	}

	// Calculates a weighted average of a double array with the indices as
	// values and the values in the array as weights.
	static double weightedAverage(double[] array){

		double sumValues = 0;
		for(int i=0; i<array.length; i++)
			sumValues += i * array[i];

		return sumValues;
	}

	// Returns a list of possible continuation states from the current one.
	static List<State> nextStates(State state){

		// Current and changing position of the ant
		int antX = state.ant % 5;
		int antY = state.ant / 5;

		// Whether it can go into each of the four directions (N,S,E,W respectively).
		boolean[] possibleDirs = new boolean[4];
		Arrays.fill(possibleDirs, true);

		// Take out some directions if it's in the corner.
		if(antY == 0) possibleDirs[0] = false; // Can't go north
		if(antY == 4) possibleDirs[1] = false; // Can't go south
		if(antX == 4) possibleDirs[2] = false; // Can't go east
		if(antX == 0) possibleDirs[3] = false; // Can't go west

		// Construct a list of continuations.
		List<State> nextStates = new ArrayList<State>();

		// Loop through the four directions.
		for(int i=0; i<4; i++){

			// Cannot go this direction.
			if( !(possibleDirs[i])) continue;

			int newAntX = antX;
			int newAntY = antY;

			// Modify direction.
			switch(i){
				case 0: newAntY--; break;
				case 1: newAntY++; break;
				case 2: newAntX++; break;
				case 3: newAntX--; break;
			}

			// Start constructing new state object.
			int oldAnt = state.ant; // old ant position
			int newAnt = 5*newAntY + newAntX;
			int[] board = state.board.clone();
			boolean carrying = state.carrying;

			// Carrying a seed. Notice that a square can contain
			// two seeds at once (but not more); seeds are indistinguishable
			// so we just need to keep track of the number of seeds
			// on each square.
			if(carrying){
				board[oldAnt] --;
				board[newAnt] ++;
			}

			// Drop off the seed.
			if(newAntY == 0 && board[newAnt] == 1 && carrying)
				carrying = false;

			// Pick up a new seed.
			if(newAntY == 4 && board[newAnt] == 1 && !carrying)
				carrying = true;

			// Treat the five done positions the same.
			if(donePosition(board))
				nextStates.add(State.FINAL_STATE);

			// Add it normally.
			else nextStates.add(new State(board, newAnt, carrying));
		}

		return nextStates;
	}

	// Is the board in the done position?
	static boolean donePosition(int[] b){
		return b[0]==1 && b[1]==1 && b[2]==1 && b[3]==1 && b[4]==1;
	}
}

class State{

	static final State INIT_STATE = new State(
	new int[]{
		0,0,0,0,0,
		0,0,0,0,0,
		0,0,0,0,0,
		0,0,0,0,0,
		1,1,1,1,1
	}, 12, false);

	// Consider all final states the same; there is
	// no ant position.
	static final State FINAL_STATE = new State(
	new int[]{
		1,1,1,1,1,
		0,0,0,0,0,
		0,0,0,0,0,
		0,0,0,0,0,
		0,0,0,0,0
	}, -1, true);

	// 25 board.
	int[] board;

	int ant;
	boolean carrying;

	State(int[] board, int ant, boolean carrying){
		this.board = board;
		this.ant = ant;
		this.carrying = carrying;
	}

	State(State s){
		this(s.board, s.ant, s.carrying);
	}

	public boolean equals(Object o){
		State s = (State) o;
		return Arrays.equals(s.board, board) && s.ant == ant && s.carrying == carrying;
	}

	public int hashCode(){
		return Arrays.hashCode(board) + ant;
	}

	// For debugging mostly.
	public String toString(){
		StringBuilder ret = new StringBuilder("\n");
		for(int i=0; i<5; i++){
			for(int j=0; j<5; j++){
				int pos = 5*i + j;
				if(ant == pos) ret.append("#");
				else ret.append(board[pos] >= 1? "+" : "-");
			}
			ret.append("\n");
		}
		return ret.toString();
	}
}

As we run this program, the answer becomes more and more accurate. We only need 2300 or 2500 steps to get the six digits of accuracy we need.

Running the program:

Hosted by imgur.com

This takes just over a minute to run — not bad at all.


Follow

Get every new post delivered to your Inbox.

Join 73 other followers