// Arup Guha
// 1/16/2014
// Uses theory to determine probability distribution of where the drunkard will be after a certain number of steps.

import java.util.*;

public class Drunkard {
	
	final public static int N = 5;
	final public static int STEPS = 1000000;
	
	public static void main(String[] args) {
		
		// Set up matrices using the drunkard's walk example shown in class.
		double[][] start = new double[1][N];
		double[][] trans = new double[N][N];
		start[0][N/2] = 1;
		trans[0][1] = 1;
		trans[N-1][N-2] = 1;
		for (int i=1; i<N-1; i++) {
			trans[i][i-1] = .5;
			trans[i][i+1] = .5;
		}
		
		// Set up our two matrices, exponentiate, multiply and print resultant probabilities.
		Matrix s = new Matrix(start);
		Matrix m = new Matrix(trans);
		Matrix m1000000 = m.pow(STEPS);
		Matrix probs = s.multiply(m1000000);
		System.out.println(probs);
	}
}