0
$\begingroup$

I have a set of marbles and a number line from 0 to infinity. Every step I either put a new marble on the number 0 or I move one existing marble (chosen uniformly) to the next number. The ratio between new marbles and propagating existing marbles is $r$. That is, for every new marble I put down, $r$ marbles have been propagated since the last new marble.

At any given time I want to know the distribution of my marbles. How would I model this? I don't really know where to start.

Also, eventually I would want to change how I select the marble to propagate. Maybe I want to favor the marbles closer to 0, or maybe I want to guarantee that each number on the line has at most $k$ marbles. This second suggestion sounds quite a bit more complex though.

Any thoughts?

$\endgroup$

1 Answer 1

0
$\begingroup$

After $n$ marbles are on the line, the sum of the positions is $(n-1)r$. The average position of the first marble to be placed is $r(1+\frac 12 + \frac 13 + \dots \frac 1{n-1})=rH_{n-1} \approx r (\log (n-1)+ \gamma)$ because it is certain to be moved the first $r$ moves, has $\frac 12$ chance for the next $r$ and so on. $H_k$ is the $k$th harmonic number. The average position of the second marble is $r(H_{n-1}-1)$ and so on. There will be substantial dispersion.

The other way to model it is to write a program that throws random numbers, using whatever distribution you want, and collect the statistics. Do a bunch of tries and see what comes out. If the choice of which marble to move is not uniform, you will need this.

$\endgroup$
6
  • $\begingroup$ By `and so on' do you mean that the third marble would have average position $r (H_{n-1} - (1 + \frac{1}{2}))$ and the fourth would have average position $r (H_{n-1} - (1 + \frac{1}{2} + \frac{1}{3}))$? $\endgroup$
    – pdexter
    Commented Jul 3, 2014 at 20:13
  • $\begingroup$ That is correct. The fourth marble can't get moved in the first three batches of moves because it is not on the board yet, so you skip the first three terms in the sum. $\endgroup$ Commented Jul 3, 2014 at 20:17
  • $\begingroup$ Can I say anything about the final distribution? For example, can I say that any certain percentage is below the number 20? $\endgroup$
    – pdexter
    Commented Jul 5, 2014 at 4:05
  • $\begingroup$ I don't see anything easy. Of course if $r$ is small, you know the last few marbles are below $20$, and the next to last few are very likely below $20$ $\endgroup$ Commented Jul 5, 2014 at 4:26
  • $\begingroup$ It seems to follow an exponential distribution perfectly. I'm using $\lambda = 1/r$. plot image Is there any way to prove this? $\endgroup$
    – pdexter
    Commented Jul 5, 2014 at 15:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .