Calculate the probability for the lamp at the origin to be lit after n steps of a random walk on the lamplighter group; see https://math.stackexchange.com/questions/2837955.

Question2837955.java

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

public class Question2837955 {
	static class State {
		boolean lamp;
		int x;
		
		public State () {}
		
		public State (State s) {
			this.lamp = s.lamp;
			this.x = s.x;
		}
		
		public int hashCode() {
			return 2 * x + (lamp ? 0 : 1);
		}

		public boolean equals (Object o) {
			State s = (State) o;
			return s.lamp == lamp && s.x == x;
		}
	}
	
	public static void main (String [] args) {
		Map<State,BigInteger> counts = new HashMap<>();
		counts.put (new State (),BigInteger.ONE);

		BigInteger total = BigInteger.ONE;
		for (int n = 0;;n++) {
			BigInteger sum = BigInteger.ZERO;

			for (State s : counts.keySet ())
				if (s.lamp)
					sum = sum.add (counts.get (s));
			
			System.out.println (n + " " + (0.5 - (sum.doubleValue () / total.doubleValue ())));
			
			Map<State,BigInteger> newCounts = new HashMap<>();
			for (State state : counts.keySet ()) {
				BigInteger count = counts.get (state);
				for (int d = -1;d <= 1;d++) {
					State newState = new State (state);
					newState.x += d;
					if (d == 0 && state.x == 0)
						newState.lamp = !newState.lamp;
					BigInteger newCount = newCounts.get (newState);
					if (newCount == null)
						newCount = BigInteger.ZERO;
					newCounts.put (newState,newCount.add (count));
				}
			}
			
			counts = newCounts;
			total = total.multiply (BigInteger.valueOf (3));
		}
	}
}