🚀 go-pugleaf

This one has bothered me for a long time.


"HALF-OR-PLUS" is a simple discrete-time stochastic process. 
 ~~~~~~~~~~~~
Start with value 1; and at each time step, either halve or add one to the current
value, with probability 1/2 each, independently of what's happened before.


Formally....    Y   = 1
                 0

                        /   Y  + 1  .....   if  X = 0
                       /     n                   n
              Y     = <
               (n+1)   \    Y  / 2  .....   if  X = 1
                        \    n                   n

where { X  } is a Bernoulli sequence with parameter 1/2 .
         n
-----

This is a Markov process, and, as always, one is interested in the long-term
behaviour of it.  

Intuitively, as the value is bounded below by zero, but downward moves are 
more "damaging" than upward ones (at least to large values), one would expect
that it would "settle down" to a reasonable statistcal behaviour. That is,
one might hope that the probability distribution of Y(n) would tend to
some fixed distribution on R+ , seemingly with most of its weight near the
left end.

Indeed, if the transition rule were more diffuse, that's what we would get,
fairly straightforwardly.  But the trouble here is, the state space for this
process, i.e. the set of values any of the Y(n) might take, is a discrete
set, though an unusual one. Specifically, the state space is the set of
positive dyadic fractions
                           S = { m/2^n : for integer m>0, n>=0 } .

So the probability distribution for each Y(n) is discrete, supported by 
a finite subset of S .

And it seems to be exceedingly difficult to calculate what the limiting
(continuous) probability distribution is. It's not even 100% clear that 
there WILL be a limiting distribution, though I feel sure there must be !

It seems reasonably easy to calculate (numerically), coarse approximations to 
the limiting distribution; i.e. the limiting discrete distribution on the set 
of disjoint intervals of unit width; or of half-unit width; and so on. 
But it's frustrating trying to extend the results to a continuous distribution.


Anyone who can provide help on this problem will earn my gratitude.

---
Bill Taylor.                  wft@math.canterbury.ac.nz