Sunday, November 23, 2014

Minibus stochastic process (part 1)

Recently I had a talk in Pereslavl, so I needed to get up early and travel to bus station, because the only way to get to Pereslavl on public transport is by intercity bus.

Well, that was a long way (about 6 hours one direction). But first step was to get to nearest underground station, which is not so trivial in mornings. People hurry, traffic jams make public transport circulate slowly, and as a result, there is crowding in nearly every bus/minibus moving towards city center or nearest underground station.

After I found a place for me in one of minibuses I was quite sure that there is at most free place for one or two passengers.

Of course, I was wrong. The minibus was moving its way and driver skipped the stops if nobody wanted to get off, since minibus was already filled. But when he stopped and one of passengers got off, two new were coming into, which made it even more crowdy inside.

Each time I was sure, that after looking inside people won't enter the minibus, and each time they did. Exactly two new passengers, others for some reason didn't dare.

So I invented such a simple stochastic process:
At $t=0$ there is only one passenger. During small time interval $\Delta t$ each passenger with probability $\alpha \Delta t$  wants to get off. When he gets off, two new passengers are entering the bus.

Studying the probability-generating function

Let's introduce an analytical over $s$ function that will describe the process:
$F(t, s) = \sum_{n=0}^{+\infty} p_n (t) s^n$, where $p_n(t)$ is probability that at the moment $t$ there are exactly $n$ passengers.

Note:

  1. $F(t,1) = 1$ for any $t$, since the probabilities sum up to 1.
  2. $F(0,s) = s$, since initially there was exactly one passenger
Now let's think about how this system evolves. During small time interval $\Delta t$ with probability $\alpha n \Delta t$ the number of passengers is incremented (by one).

This is mathematically written as:
$$p_n(t + \Delta t) \cong p_n(t) + \alpha (n-1) \Delta t  p_{n-1}(t) - \alpha n \Delta t  p_{n}(t), \quad p_0 \equiv 0$$
Which in the limit $\Delta t \to 0$ turns into system of ODEs:

$$\frac{d}{dt} p_n(t) =  - \alpha n  p_{n}(t) + \alpha (n-1) p_{n-1}(t), \quad p_0 \equiv 0$$

Or equivalently this can be written as single PDE:

$$F_t(t,s) = \alpha F_s(t,s) (s^2 - s) $$

The last one is solved in typical way:
$$F=F(z), \quad z=e^{-\alpha t}\frac{s}{1-s}$$
So we can compute value for any $t,s$ by
$$F(t,s) = F(0,s_0), \text{where } \; e^0 \frac{s_0}{1-s_0} = z =  e^{-\alpha t}\frac{s}{1-s}, $$
and it is now easy to compute that

$$s_0 = \frac{1}{1 + e^{\alpha t} \frac{1 - s}{s} }, $$
so for our setting with one passenger at $t=0$:
$$F(t,s) = s_0 = \frac{1}{1 + e^{\alpha t} \frac{1 - s}{s} }  =   \frac{s e^{-\alpha t}}{1  - s(1 - e^{-\alpha t}) } $$

and we can see that at moment $t$ this is geometric distribution with mean=$e^{\alpha t}$.

As an example to play with, you can try to repeat the same for the process where a man is leaving the minibus and nobody comes in (so that is like fermion version of the same problem :) )
You'd get
$$F_t(t,s) = \alpha F_s(t,s) (1 - s) $$
$$F_t(t,s) = s e^{-\alpha t} + (1 - e^{-\alpha t}) $$

For the version with $k$ new passengers one would have the following PDE:
$$F_t(t,s) = \alpha F_s(t,s) (s^k - s), $$
which is studied the same way

NB: Easy to see that $F_t(t,1) = \text{const} $, which is good sign (probabilities always sum up to 1), and a simple self-check.

First I solved this problem, then thought about possible applications and googled them. 
The interesting thing that such systems form quite popular topic in statistics: they are called 'branching processes'. 
What is it in general case, and what are applications of such mad model - in the next part.

No comments :