\section{Non-ergodicity of 2048}


The purpose of this section is to prove the non-ergodicity of the 2048 game.

\begin{theorem}
2048 game is non-ergodic between non-absorbing states.
\end{theorem}
\begin{IEEEproof}
 To apply Theorem \ref{judgmentTheorem}, what we need 
 to do is to assign a countable value to the 2048 game board 
 and demonstrate the properties of the 
 state transition probabilities in the 2048 game.


In the 2048 game, each tile has 16 potential values,
 including empty and $2^k$, $k\in\{1,2,3,\ldots,15\}$.
Using 4 bits to represent a tile, the game board is a 4$\times$4 matrix 
$B$. The corresponding tile is then computed as follows:
\begin{equation}
1\leq m\text{, }n \leq 4\text{, }tile_{m,n} =
\begin{cases}
0, & \text{if } B_{mn}=0; \\
 2^{B_{mn}}, & \text{otherwise.}  
\end{cases}
\label{equationTile}
\end{equation}
The sum of all tiles in the game board is
\begin{equation}
sum(B) = \sum_{m=1}^4\sum_{n=1}^4 tile_{mn}.
\end{equation}
A 64-bit long integer can uniquely represent any game board state.
\begin{equation}
long(B)= \sum_{m=1}^4\sum_{n=1}^416^{(m-1)*4+(n-1)}\cdot B_{mn}.
\end{equation}
We have 
\begin{equation}
long(B)<2^{64}.
\label{size}
\end{equation}
The size of the board space $\mathcal{B}$ is
$|\mathcal{B}|=2^{64}$.
Define a utility function on board,
\begin{equation}
u(B) = 2^{64}\cdot sum(B)+long(B).
\label{utility}
\end{equation}
It is easy to verify that 
$\forall B_1, B_2\in \mathcal{B}$,
if $B_1\neq B_2$, then $u(B_1)\neq u(B_2)$.
For all possible board,
 $\forall B\in \mathcal{B}$, calculate the utility value
 $u(B) $, and sort $B$ by $u(B) $ in ascending order.
 Let $I(B)$ be the index of the board $B$ after sorting,
 we have
 \begin{equation}
 \forall B_1, B_2\in \mathcal{B}, u(B_1)<u(B_2) \iff
 I(B_1)<I(B_2).
 \label{basis}
 \end{equation}
For any transition $\langle B_1, a, B_1', B_2\rangle$ in the 2048 game,
we have 
$sum(B_1)=sum(B_1')$  regardless of whether at least two tiles merge.

Due to a new generated 2-tile or 4-tile in board $B_2$,
$sum(B_2)>sum(B_1')$, that is $sum(B_2)>sum(B_1)$.

Based on (\ref{size}) and (\ref{utility}),
we have  $u(B_2)>u(B_1)$.
That means $I(B_2)>I(B_1)$.
The transition probability between non-absorbing state satisifies (\ref{condition}),
the claim follows by applying Theorem \ref{judgmentTheorem}.
\end{IEEEproof}

%\input{material/2048prove}