The $3x + 1$ Problem: Two Stochastic Models

The $3x + 1$ problem concerns the behavior under iteration of the function T: Z⁺ → Z⁺ defined by $T(n) = n/2$ if n is even and $T(n) = (3n + 1)/2$ if n is odd. The $3x + 1$ conjecture asserts that for each n ≥ 1 some k exists with T⁽ᵏ⁾(n) = 1; let σ_∞(n) equal the minimal such k if one exists and +∞ otherwise. The behavior of σ_∞(n) is irregular and seems to defy simple description. This paper describes two kinds of stochastic models that mimic some of its features. The first is a random walk that imitates the behavior of T (mod2ʲ); the second is a family of branching random walks that imitate the behavior of T⁻¹ (mod3ʲ). For these models we prove analogues of the conjecture that lim n → ∞(σ_∞(n)/log(n)) = γ for a finite constant γ. Both models produce the same constant γ₀ 41.677647. Predictions of the stochastic models agree with empirical data for the $3x + 1$ problem up to 10¹¹. The paper also studies how many n have σ_∞(n) = k as k → ∞ and estimates how fast t(n) = max(T⁽ᵏ⁾(n): k ≥ 0) grows as n → ∞.