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(k)(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(mod2j); the second is a family of branching random walks that imitate the behavior of T.1(mod3j). For these models we prove analogues of the conjecture that limsupn..(..(n)/log(n))=. for a finite constant .. Both models produce the same constant .0.41.677647. Predictions of the stochastic models agree with empirical data for the 3x+1 problem up to 1011. The paper also studies how many n have ..(n)=k as k.. and estimates how fast t(n)=max(T(k)(n):k.0) grows as n...