Collatz-Style Division Process on Even Integers

Stochastic Processes · Medium · Free problem

You are given a large even integer $N$ and must repeatedly apply the following operation:

  • If $N \equiv 0 \pmod{4}$, replace $N$ with $N/2$.
  • If $N \equiv 2 \pmod{4}$, replace $N$ with $3N/2$.

The process stops when $N$ becomes odd.

  1. Model this process as a Markov chain on the 2-adic valuation $v_2(N)$ (the largest power of 2 dividing $N$). Prove that the process terminates almost surely for any even starting value $N$.
  1. For a given starting value $N_0$, derive tight bounds (in terms of $\log N_0$) on the maximum possible number of steps before termination.
  1. For a "typical" large even $N_0$ (say, chosen uniformly at random from even integers up to some bound), discuss whether the expected number of steps is closer to the lower or upper bound.

Hints

  1. Track the 2-adic valuation $v_2(N)$ -- how many times does 2 divide $N$? What happens to $v_2$ at each step?
  2. When $v_2(N) \geq 2$, dividing by 2 reduces $v_2$ by exactly 1. When $v_2(N) = 1$, check whether $3N/2$ is even or odd.
  3. Since $v_2$ decreases by 1 at every step until the $3N/2$ operation terminates the process, the total number of steps is exactly $v_2(N_0)$. For the typicality question, compute $P(v_2 = k)$ for a random even integer.

Worked Solution

How to Think About It: The key is to track the 2-adic valuation $v_2(N)$, which counts how many times 2 divides $N$. Write $N = 2^k \cdot m$ where $m$ is odd and $k \geq 1$ (since $N$ is even). Now look at what each operation does to $k$:

  • If $k \geq 2$ (i.e., $N \equiv 0 \pmod{4}$): we replace $N$ with $N/2 = 2^{k-1} \cdot m$. The valuation drops by 1, and the odd part $m$ stays the same.
  • If $k = 1$ (i.e., $N \equiv 2 \pmod{4}$): we replace $N$ with $3N/2 = 3m$. Since $m$ is odd, $3m$ is odd -- so the process terminates immediately.

This means the process is actually deterministic once $N_0$ is fixed, and the number of steps equals exactly $v_2(N_0)$.

Quick Estimate: Take $N_0 = 2^{10} \cdot 7 = 7168$. Here $v_2(N_0) = 10$, so the process runs for exactly 10 steps:

$7168 \to 3584 \to 1792 \to 896 \to 448 \to 224 \to 112 \to 56 \to 28 \to 14 \to 21$

The first 9 steps are divisions by 2 (each time $v_2 \geq 2$), and the final step applies the $3N/2$ rule when $v_2 = 1$ (here

4 \to 21$). The process always terminates because $v_2$ strictly decreases at each division step and the $3N/2$ step terminates immediately.

Part 1 -- Markov Chain Formulation and Almost Sure Termination:

Define the state of the chain as $k = v_2(N)$. The state space is $\{0, 1, 2, 3, \ldots\}$, where state 0 means $N$ is odd (absorbing). The transitions are:

  • From state $k \geq 2$: move to state $k - 1$ with probability 1.
  • From state $k = 1$: move to state 0 with probability 1 (since $3N/2$ is odd).

This is a purely deterministic walk toward the absorbing state. Starting from state $k_0 = v_2(N_0)$, the chain reaches state 0 in exactly $k_0$ steps. Since $k_0 < \infty$ for any finite $N_0$, the process terminates with probability 1. $\square$

More formally, define the supermartingale $M_t = v_2(N_t)$. At each step $M_{t+1} \leq M_t - 1$ (strict decrease, not merely non-increase). Since $M_t$ is a non-negative integer-valued process that decreases by exactly 1 each step, it hits 0 in exactly $M_0$ steps. By the optional stopping theorem (or simply by induction), termination is certain.

Part 2 -- Bounds on the Number of Steps:

The number of steps equals $v_2(N_0)$, the 2-adic valuation of $N_0$. We need to bound this in terms of $\log N_0$.

  • Upper bound: Since $N_0 \geq 2^{v_2(N_0)}$, we have $v_2(N_0) \leq \log_2 N_0$. More precisely, $v_2(N_0) \leq \lfloor \log_2 N_0 \rfloor$. This bound is tight: take $N_0 = 2^k$ (a pure power of 2), which gives exactly $k = \log_2 N_0$ steps.
  • Lower bound: $v_2(N_0) \geq 1$ for any even $N_0$. This is tight: take $N_0 = 2m$ for any odd $m$, which gives exactly 1 step.

So the number of steps $T$ satisfies:

$1 \leq T = v_2(N_0) \leq \lfloor \log_2 N_0 \rfloor$

Both bounds are achievable. In big-O notation, $T = O(\log N_0)$ and $T = \Omega(1)$.

Part 3 -- Typical Number of Steps:

For a "typical" large even integer, the number of steps is much closer to the lower bound. Here is why.

Among all even integers, the probability that a uniformly random even integer has $v_2 \geq k$ is

/2^{k-1}$ (since this requires divisibility by
^k$). So:

$P(v_2 = k) = \frac{1}{2^{k-1}} - \frac{1}{2^k} = \frac{1}{2^k} \quad \text{for } k \geq 1$

The expected number of steps is:

$E[T] = \sum_{k=1}^{\infty} k \cdot \frac{1}{2^k} = 2$

So for a random large even integer, the expected number of steps is just 2 -- a constant independent of $N_0$. Half of all even integers have $v_2 = 1$ (one step), a quarter have $v_2 = 2$ (two steps), and so on. The typical behavior is overwhelmingly near the lower bound.

The upper bound of $\log_2 N_0$ steps is achieved only by powers of 2, which are exponentially rare among integers of that size. Among even integers up to M$, there are only $\log_2(2M)$ powers of 2, compared to $M$ total even integers.

Answer: The process terminates in exactly $v_2(N_0)$ steps. This is bounded by

\leq v_2(N_0) \leq \lfloor \log_2 N_0 \rfloor$, with both bounds tight. For a typical large even integer, the expected number of steps is 2, so the typical case is dramatically closer to the lower bound. Only the exponentially rare powers of 2 approach the upper bound.

Intuition

This problem looks like it might involve complicated Collatz-like dynamics, but the 2-adic valuation reveals that the process is actually trivial: each step reduces $v_2$ by exactly 1, and the $3N/2$ operation always produces an odd number when $v_2 = 1$. The "Markov chain" is just a deterministic countdown. The real insight is recognizing that tracking the right quantity -- here the 2-adic valuation rather than $N$ itself -- collapses what looks like a complex dynamical system into a simple one. This is a recurring theme in quant interviews: many problems that seem hard become easy once you identify the right state variable.

The typicality discussion illustrates a related principle that shows up constantly in practice: worst-case and average-case behavior can differ by orders of magnitude. The worst case here is $\Theta(\log N_0)$ steps, but the average case is $O(1)$ -- just 2 steps regardless of how large $N_0$ is. This kind of gap between worst-case and typical-case complexity matters in algorithm design, trading system latency analysis, and risk management.

Open the full interactive solver →