Average norm growth in a 2048-like merging game

Inspired from a 2048-like merging mobile game. There are surprisingly many of these -- just check the ads if you want one.

Consider the space of (positive) integer sequences $u = (u_0,u_1,...) = \sum u_ie_i$ with one "norm" and one operation. The measurement is $\| u \| = \sum 2^i u_i$. The operation $T$ is as follows: first add $e_0$ to $u$. If all entries are at most 1 then we are done. Otherwise find the lowest $u_i \geq 2$ and perform $u \mapsto u - 2e_i + e_{i+1}$. For those who know, this is related to 2-adic numbers, but we are not going to cover advanced math today. A simple question is how does the operation $T$ affects the norm? Clearly it adds the norm by 1 because the carry operation is norm invariant.

Game devs know as much as we do that simply advancing in 2-adic numbers one by one is insanely boring so they decided to adopt a variant instead. Consider an alternate operation as follows: there is a chance $r$ so that the carry jumps to the next digit. i.e., $u \mapsto u - 2e_i + e_{i+2}$. In that case, the norm jumps by $2^{i+1}$. 

Now under the new operation, what is the expected growth rate of the norm? Well, this is yet another Markov Chain like problem like many others we have encountered here. Let $p_{n,k}$ be the chance of $u_n = k$ in long term using the fact that the lower digits are independent of the higher ones. That gives an ergodic chain, meaning that it converges.

We work out the case $n=0$ effortlessly: $p_{0,0} = p_{0,1} = 0.5$. What about $p_{1,k}$?

When $u_0 = 0$, $u_1$ would be merged if $u_1\geq 2$. When $u_0 = 1$, there is a chance of $1-r$ that the carry lands on $u_1$ (no jumps). 

Therefore we have the system

$p_{1,0} = 0.5p_{1,0} + 0.5p_{1,2}$

$p_{1,1} = 0.5p_{1,1} + 0.5p_{1,3} + 0.5(1-r)p_{1,0}$

$p_{1,2} = 0.5p_{1,2} + 0.5p_{1,4} + 0.5(1-r)p_{1,1}$

...

That quickly becomes a mess. We will need another probability $q_n = (1-p_{0,0})\cdot \prod _{n = 1} (1-p_{n,0}-p_{n,1})$ the chance of no carrying up to $u_n$. We know $q_0 = 0.5$ hence the 0.5 above but the rest is so bad. Worse news is that $q_n$ is not a constant, and we don't even know if it converges to 0 as long as $p_{n,0}+p_{n,1}$ shrinks quick enough(for example, $\prod (1-2^{-n}) \approx 0.289$ converges to a positive constant). On one hand, we know carrying always happen as long as the lower digits requires no carrying. On the other hand, we worry the possibility of carrying happening mostly at lower digits, causing higher $u_n$ to stack up.

Oh, you say the original question was asking the growth rate of the norm? That's simple. Once you computed $p_{n,k}$'s, we know exactly how often a jump would happen on a given digit which gives the extra growth except the $p_{n,k}$'s are too complicated to compute.

But wait! We can still do some simulation. We can't accurately sample $u$ as an infintiely long string but we can simulate the operation starting from $u = 0e_0$. From here we have two key observations.

First, $p_{n,k}$ is largely independent of $n$ with $\lim _{n\to \infty}p_{n,k} = p_k$. Why? The state only changes when carrying concerning a certain digit occurs, but it's behavior (whether carrying to next digit or jump occurs) is uniform across $n$. If carrying is 50% less likely on a certain digit, it only means a state of change is 50% less likely, but that does not change the proportion among numbers at that digit in long term.

This is very important because now we can simply work on $p_k$ which would be a good estimate. Another implication is that $q_k$ is surely geometrically converging to zero, so we have one less technical problem.

Second which is also our original question. If we also call the new operation by $T$ out of laziness, we find that $\| T^k(u)/k\|$ increases with $k$. This is clear if we fit into a simpler but similar parameter. Assume that a carry happens at $u_n$ at the chance of $2^{-n}$. The expected gain in norm due to jump would be $\sum 2^{-n} \cdot 2^n = \sum 1$ which diverges...in a long term scenario. Practically when $u$ is finite, the number of 1's is capped by the highest non-zero $u_n$. That says, we expect $\| T^k(u)\|$ to behave like $O(k \log k)$ under the simplified parameter. Using the approximated parameter of $p_k$ the best guess remains $O(k \log k)$ instead of $O(k^{1+\varepsilon})$.

All I can say is, this problem sounds more interesting than Simon Marais A4 that I have covered month ago, and it's something nice to spend time on while listening to the carols.