Adding beans to a pot

I’ve been reading through Crispin Gardiner’s `Handbook on stochastic processes’. It’s a really dense but helpful book, designed sort of as a reference as opposed to a teaching tool. There are plenty of calculations worth going through, but the very first one I wanted to redo is using generating functions to derive the Poisson process, that’s the probability distribution generated from a process that has a mean rate of happening in a given time interval. The events must be independent. I’ll frame the process in terms of adding a single bean n=1 to a pot with mean chance \lambda in a given time interval \Delta t.

Thus, the probability we consider is a function of time and number of beans p(n,t). The probability that the number of beans is increased by 1 in the time interval t+\Delta t is

p(n\to n+1,t+\Delta t) = \lambda\Delta t

That means the probability that n stays constant in the time interval is made up of the addition of two probabilities: the complement of the probability of having n and increasing the number, and the probability that we orginally had n-1 beans and one was added. Together then

p(n,t+\Delta t) = p(n,t)[1 - \lambda\Delta t] + p(n-1,t)\lambda\Delta t

we can expand and factor and then as \Delta t\to 0 we have a partial differential equation (PDE) for the probability:

\frac{1}{\lambda}\frac{\partial p}{\partial t} = p(n-1,t)-p(n,t)

We can solve this partial differential equation, for example, by using the method of generating functions. We define a probability generating function (pgf) as a power law sum:

G(s,t) = \sum_{n=0}^{\infty} s^n p(n,t)

The reason for calling it a generating function is intuitive. Taking the first derivative with respect to s and evaluating at s=0 gives us

\left.\partial_s G(s,t)\right|_{s=0} = \sum_{n=1}^{\infty} n s^{n-1} p(n,t) = 1*0^0*p(1,t) + 2*0^1*p(2,t) + 3*0^2*p(3,t) + \ldots

where we had to readjust the sum to avoid division by zero. It is clear then that

\left.\partial_s G(s,t)\right|_{s=0} = p(1,t)

so taking derivatives of the pgf and evaluating at 0 gives us the probability of having 1 bean over time. Likewise the second derivative evaluated at zero gives us the probability of having 2 beans

\left.\partial_s^2 G(s,t)\right|_{s=0} =  \sum_{n=2}^{\infty} n(n-1) s^{n-2} p(n,t) = 2*1*p(2,t)

so that the general formula for the probability of having k beans is

p(k,t) = \frac{1}{k!} \left. \partial_s^k G(s,t)\right|_{s=0}

and this function `generates’ the probabilities.

Now, we can return to solving the PDE. Writing the time derivative of the pgf

\partial_t G(s,t) = \sum_{n=0}^{\infty} s^n \partial_t p(n,t)

we now substitute in the time rate-change of the probability from the PDE we are interested in solving

\partial_t G(s,t) = \lambda \sum_{n=0}^{\infty} s^n [p(n-1,t)-p(n,t)]

the right hand side sum can be written out using the notation $p(s,t)=p_s$

\partial_t G(s,t)  = \lambda[s^1p_0-s^1p_1+S^2p_1-s^2p_2+\ldots]

and grouping terms

\partial_t G(s,t)  = \lambda[sp_0 + p_1s(s-1) +p_2s^2(s-1) +\ldots]


\partial_t G(s,t)  = \lambda(s-1)[\frac{s}{s-1}p_0 + p_1s +p_2s^2 +\ldots]

so that for s\gg1 this is approximately

\partial_t G(s,t)  \approx \lambda(s-1)[p_0 + p_1s +p_2s^2 +\ldots] = \lambda(s-1)G(s,t)

thus the solution is

G(s,t) = e^{\lambda(s-1)t} G(0,t)

If we assume that n=0 at t=0, we have p(0,0)=1 and p(n\geq 1,0)=0. That means that G(s,0)=1. We can write

G(s,t) = e^{\lambda(s-1)t} = e^{-\lambda t}\left(e^{\lambda t}\right)^s

and expand in powers of s to obtain

G(s,t) = e^{-\lambda t}[1+s\ln e^{\lambda t} + \frac{1}{2!}s^2(\ln e^{\lambda t})^2 + \frac{1}{3!}s^3(\ln e^{\lambda t})^3 + \ldots]

G(s,t) = \sum s^k \,\frac{e^{-\lambda t} (\lambda t)^k}{k!}

so that we may identify p(k,t) obtaining the solution to the Poisson process for the number of beans in a jar if they are added randomly with a mean number in a time interval to be

p(n,t) = \frac{e^{-\lambda t} (\lambda t)^n }{n!}

The form of this probability distribution might be familiar.

1 Comment

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s