[math-fun] a perplexing asymmetry
Here's a sequence I'd like to know more about: (*) 1,1,2,3,3,4,4,4,5,6,6,7,8,8,9,9,9,... It arises from a simple numerical dynamical sytem that describes how a sharply concentrated distribution of particles spreads out as it drifts off to the right. The nth term (which I'll call f(n)) is about n/2, but there's an asymmetry in the behavior of f(n) - n/2 that tells us something about the ways in which which round-off errors can build up instead of cancelling out. To find the nth term, put n particles at location 1 and then start moving particles on {1,2,3,...}, according to the rule that at each discrete time step, nearly 2/3 of the particles at any given location move one step to the right and nearly 1/3 move one step to the left --- where "nearly" means "rounded to the nearest integer". More specifically, if a site has 3k+i particles, with i = -1, 0, or 1, then 2k+i of those particles move one step to the right and k of them move one step to the left. Important special case: Particles that move to the left from *1* fall out of the system, or if you prefer, get absorbed at 0. It can be shown that eventually none of the sites 1,2,3,... has more than 1 particle, and all these particles move in lock-step forever after, each moving one step to the right at each time-step. Define f(n) as the number of particles forming this train. Then (*) is just the sequence f(1),f(2),f(3),... For instance, here's how we compute that f(8) = 4: 8 0 0 0 0 0 0 0 0 ... 0 5 0 0 0 0 0 0 0 ... 2 0 3 0 0 0 0 0 0 ... 0 2 0 2 0 0 0 0 0 ... 1 0 2 0 1 0 0 0 0 ... 0 2 0 1 0 1 0 0 0 ... 1 0 1 0 1 0 1 0 0 ... 0 1 0 1 0 1 0 1 0 ... 0 0 1 0 1 0 1 0 1 ... ................................................. If fractional particles were allowed, and if every particle were to split into 2/3 of a particle moving to the right and 1/3 of a particle moving to the left (in this case, it makes sense to switch to a mass-flow metaphor), then it is not hard to show that over time, exactly half of the mass disappears from the system (by disappearing to the left) while half of the mass travels off to the right. So, we expect f(n) to be close to n/2; and by and large, it is. But to me, the big surprise about f(n) is that it never falls short of n/2 (at least not for values of n up through 500)! Indeed, the only values of n up to n=500 for which f(n) equals n/2 are 2, 8, 48, 50, and 200; for all other n up to 500, f(n) is strictly greater than n/2. Naively, one would expect the difference between f(n) and n/2 to be positive as often as it is negative. So, what's going on here? Jim Propp
participants (1)
-
James Propp