Poisson inflow, constant outflow question

In summary, In response to a problem in work, the author found a simple solution in the form of a sum, and numerically found that it equals the result <v> = i/(2(1-i)). However, since then he's been struggling unsuccessfully to find a justification for the formula.
  • #1
pmsrw3
459
0
The following problem came up in my work.

You have a tube, open at the top. Raindrops fall into the mouth of the tube at a mean rate i per second, 0 <= i < 1, in a Poisson process. There's a hole in the bottom of the tube. When there's water in the tube, it flows out at a constant rate of 1 drop/sec. (Ignore that this is not physically plausible. You can imagine that there's a peristaltic pump hooked up if it makes you feel better.) What is the mean amount of water in the tube at steady-state?

I came up with a complicated solution to this (which I will describe, if anyone wishes) in the form of a sum. But when I evaluated my solution numerically, I found that, within round-off error, computed values equaled the simple result <v> = i/(2(1 - i)). This is also plausible and has correct limiting behavior at 0 and 1. Since then I've been trying hard without success to come up with a proof or even fairly good rationale for that formula.

Thanks in advance for any ideas.
 
Physics news on Phys.org
  • #2
The problem resembles the queueing theory model where there is a single server, poisson arrivals and a constant service time. However, the result for "average number of customers in the queue" ( for example p8 of this PDF: http://www.google.com/url?sa=t&sour...LHloQ4&usg=AFQjCNFWSUKGueI5N_p_E4GxhKRThY14HQ ) doesn't look like your answer.

Are the output drops scheduled at even increments? For example, if the output drop rate is 1 per second, suppose there is no water in the tube at time t = 0 and a drop arrives at time t = 3/4. Does the output drop happen at t = 1 or t = (1 + 3/4)?
 
  • #3
Writing it as [itex]N_{t+1}=\max(0,N_t+K_t-1)[/itex] where [itex]K_t[/itex] is Poisson, we have the steady state equations for [itex]q_n=P[N=n][/itex]
[tex]q_{n+1}=\frac{1}{p_0}-\sum_{k=0}^n p_{n+1-k}q_k - \delta_n p_0q_0[/tex]
where the [itex]p_j[/itex] are the Poisson probabilities. Taking the expectation of N leads to
[tex]q_0=(1-\lambda)e^{\lambda}[/tex]
and taking the expectation of N^2 leads to
[tex]E[N]=\frac{\lambda^2}{2(1-\lambda)}[/tex]
 
Last edited:
  • #4
Stephen Tashi said:
The problem resembles the queueing theory model where there is a single server, poisson arrivals and a constant service time. However, the result for "average number of customers in the queue" ( for example p8 of this PDF: http://www.google.com/url?sa=t&sour...LHloQ4&usg=AFQjCNFWSUKGueI5N_p_E4GxhKRThY14HQ ) doesn't look like your answer.

Are the output drops scheduled at even increments? For example, if the output drop rate is 1 per second, suppose there is no water in the tube at time t = 0 and a drop arrives at time t = 3/4. Does the output drop happen at t = 1 or t = (1 + 3/4)?
No, it's in continuous time -- the drops arrive when they arrive, and the output flow is continuous. However, you can derive a discrete time Markov chain by having a clock that ticks when the first drop falls in (assume we start empty), at 1s intervals thereafter until the tube drains, then waits until the next drop for the next tick. So, for instance if drops arrived at 1.1, 1.3, 1.5, 4.6, 5.9, 6.4, ... ticks would occur at 1.1, 2.1, 3.1, 4.1, 4.6, 5.6, 5.9, 6.9, 7.9, ... At each tick the number of drops will be an integer (1, 2, 1, 0, 1, 0, 1, 1, 0, ...). You can solve for the steady-state occupancies of this chain. The mean will not be the mean of the continuous time system, because the 0's will be underweighted. (In the discrete time case, the 0 state always lasts 1 tick, whereas in the original problem it lasts on average 1/i sec.) But it is straightforward to correct for that. That's how I solved the system. (I also did a little Monte Carlo to check my results.)

I'll have to look into queueing theory -- it's probably what I need, or very close. Unfortunately, that PDF you link to just gives formulas without derivations.

bpet said:
Taking the expectation of N leads to
[tex]q_0=(1-\lambda)e^{\lambda}[/tex]
Could you explain this step, please? I mean, I know [itex]E[N] = \sum{nq_n}[/itex], but how do you get from there to [itex]q_0=(1-\lambda)e^{\lambda}[/itex]?
 
  • #5
pmsrw3 said:
Could you explain this step, please? I mean, I know [itex]E[N] = \sum{nq_n}[/itex], but how do you get from there to [itex]q_0=(1-\lambda)e^{\lambda}[/itex]?

For that you just apply [itex]E[N]=\sum_{n=0}^{\infty}(n+1)q_{n+1}[/itex] to the recurrence relation and after some algebra the E[N] terms cancel.

In continuous time where a new drop is added with probability [itex]\lambda dt[/itex], split the state N=0 into {N=0, no drops falling} with prob q and {N=0, one drop falling} with prob q_0, and the steady state relations give you [itex]q_0=\lambda q, q_1=\lambda q_0, q_{n+2}=(1+\lambda)q_{n+1}-\lambda q_n[/itex]. Applying E[N] to the recurrence relation gives [itex]q=1-\lambda[/itex] and E[N^2] gives
[tex]E[N]=\frac{\lambda^2}{1-\lambda}[/tex].
The notes in Stephen Tashi's link imply the formula [itex]E[M]=(1-q)+E[N] = \lambda+\tfrac{\lambda^2}{1-\lambda}[/itex] which includes the drop that is falling.
 
  • #6
bpet said:
Writing it as [itex]N_{t+1}=\max(0,N_t+K_t-1)[/itex] where [itex]K_t[/itex] is Poisson, we have the steady state equations for [itex]q_n=P[N=n][/itex]
[tex]q_{n+1}=\frac{1}{p_0}-\sum_{k=0}^n p_{n+1-k}q_k - \delta_n p_0q_0[/tex]
where the [itex]p_j[/itex] are the Poisson probabilities.
I am not getting this for the SS conditions. Here is my stochastic matrix:
[tex]P=\left(
\begin{array}{cccc}
p_0+p_1 & p_2 & p_3 & \ldots \\
p_0 & p_1 & p_2 & \ldots \\
0 & p_0 & p_1 & \ldots \\
\vdots & \vdots & \vdots & \ddots
\end{array}
\right)[/tex]
From there (my lambda's are your qs), the SS condition is:
[itex]\lambda _0=\left(p_0+p_1\right)\lambda _0+p_0\lambda _1[/itex]
[itex]\lambda _1=p_2\lambda _0+p_1\lambda _1+p_0\lambda _2[/itex]
...
[itex]\lambda _n=\delta _{0n}p_0\lambda _0+\underset{k=0}{\overset{n+1}{\sum }}p_{n+1-k}\lambda _k[/itex]

Solving:
[tex]\lambda _{n+1}=-\delta _{0n}\lambda _0+\frac{\lambda _n}{p_0}-\frac{1}{p_0}\underset{k=0}{\overset{n}{\sum }}p_{n+1-k}\lambda _k[/tex]

Where am I going wrong?
 
  • #7
No you're right, there was a typo in my formula (though the end result still holds)
 
  • #8
OK, I've got it. I looked up queueing theory in Norris (Markov Chains) and roughly followed his treatment for for an M/G/1 queue. (That's more general than my problem.) Turns out he begins by discretizing the problem in almost exactly the way I did -- only difference is that he doesn't have a tick for a drop falling into an empty tube (which has to be corrected for later when computing mean volume). The update equation for this Markov chain is

[tex]X_{n+1}=X_n+Y_{n+1}-\mathbb{I}_{X_n>0}[/tex]

Y is Poisson with mean i and [itex]\mathbb{I}_{X_n>0}[/itex] is an indicator that is 1 if there's anything in the tube, 0 otherwise. Define the probability generating function for [itex]X_n[/itex]

[tex]G(z)=\mathbb{E}\left[z^{X_n}\right]=\underset{i=0}{\overset{\infty }{\sum }}\pi_iz^i[/tex]

Then

[tex]zG(z)=\mathbb{E}\left[z^{X_{n+1}+1}\right]=\mathbb{E}\left[z^{X_n+Y_{n+1}+\mathbb

{I}_{X_n=0}}\right][/tex]
[tex]zG(z)=e^{i(z-1)}\left(\pi_0z+G(z)-\pi_0\right)[/tex]

([itex]\pi_i[/itex] here is steady-state probability than [itex]X_n=i[/itex].) From here you eventually get to

[tex]G(z)=\frac{(i-1) (z-1) e^{i(z-1)}}{e^{i(z-1)}-z}[/tex]

and of course you can differentiate that to get mean X. Since the ticks are not equally spaced in time (the interval after [itex]X_n = 0[/itex] is always longer), and since there's always an extra drop that falls in during that interval, it takes some more fiddling to get to mean volume. But it does, in fact, eventually reduce to [itex]\frac{1}{2}\frac{i}{1-i}[/itex].

I still suspect, when I see such a simple answer emerge after a painfully long calculation, that I missing a more elegant way to get there. But, elegant or no, I have managed to prove what the numerical calculations said.

Thanks for putting me on the right track!
 
  • #9
pmsrw3 said:
OK, I've got it. I looked up queueing theory in Norris (Markov Chains) and roughly followed his treatment for for an M/G/1 queue. (That's more general than my problem.) Turns out he begins by discretizing the problem in almost exactly the way I did -- only difference is that he doesn't have a tick for a drop falling into an empty tube (which has to be corrected for later when computing mean volume). The update equation for this Markov chain is

[tex]X_{n+1}=X_n+Y_{n+1}-\mathbb{I}_{X_n>0}[/tex]

Y is Poisson with mean i and [itex]\mathbb{I}_{X_n>0}[/itex] is an indicator that is 1 if there's anything in the tube, 0 otherwise. Define the probability generating function for [itex]X_n[/itex]

[tex]G(z)=\mathbb{E}\left[z^{X_n}\right]=\underset{i=0}{\overset{\infty }{\sum }}\pi_iz^i[/tex]

Then

[tex]zG(z)=\mathbb{E}\left[z^{X_{n+1}+1}\right]=\mathbb{E}\left[z^{X_n+Y_{n+1}+\mathbb

{I}_{X_n=0}}\right][/tex]
[tex]zG(z)=e^{i(z-1)}\left(\pi_0z+G(z)-\pi_0\right)[/tex]

([itex]\pi_i[/itex] here is steady-state probability than [itex]X_n=i[/itex].) From here you eventually get to

[tex]G(z)=\frac{(i-1) (z-1) e^{i(z-1)}}{e^{i(z-1)}-z}[/tex]

and of course you can differentiate that to get mean X. Since the ticks are not equally spaced in time (the interval after [itex]X_n = 0[/itex] is always longer), and since there's always an extra drop that falls in during that interval, it takes some more fiddling to get to mean volume. But it does, in fact, eventually reduce to [itex]\frac{1}{2}\frac{i}{1-i}[/itex].

I still suspect, when I see such a simple answer emerge after a painfully long calculation, that I missing a more elegant way to get there. But, elegant or no, I have managed to prove what the numerical calculations said.

Thanks for putting me on the right track!

That's interesting. I'm guessing you solved for [itex]\pi_0[/itex] by finding the derivative of

[tex]zG(z)=e^{i(z-1)}\left(\pi_0z+G(z)-\pi_0\right)[/tex]

at z=1. If so, the mean could be found without explicitly solving for G by taking the second derivative at z=1.
 
  • #10
bpet said:
That's interesting. I'm guessing you solved for [itex]\pi_0[/itex] by finding the derivative of

[tex]zG(z)=e^{i(z-1)}\left(\pi_0z+G(z)-\pi_0\right)[/tex]

at z=1. If so, the mean could be found without explicitly solving for G by taking the second derivative at z=1.
There's a simpler way to get [itex]\pi_0[/itex]. At every tick, X changes by [itex]Y-\mathbb{I}_{X>0}[/itex]. At steady-state, this has to average to 0. [itex]Y[/itex] has mean [itex]i[/itex], and [itex]\mathbb{I}_{X>0}[/itex] has mean [itex]\mathbb{P}\left[X>0 \right]=1-\pi_0[/itex], so there you have it.

Norris doesn't do it this way, actually. He requires [itex]G(z)=1[/itex] (evident from the definition) and solves for [itex]\pi_0[/itex]. But this gives [itex]G(z)=0/0[/itex] and he has to use L'Hopital's Rule, so it is in essence the same as what you suggest.
 

Related to Poisson inflow, constant outflow question

1. What is Poisson inflow and constant outflow?

Poisson inflow and constant outflow is a mathematical concept used to model the flow of a substance or particle into and out of a system. It is based on the Poisson distribution, which is used to describe the probability of a certain number of events occurring within a specific time or space.

2. How is Poisson inflow and constant outflow used in scientific research?

Poisson inflow and constant outflow is commonly used in various fields of science, such as biology, chemistry, physics, and engineering. It is often used to model the movement of particles in a system, such as the diffusion of molecules in a cell or the flow of a fluid through a pipe.

3. What are the assumptions made in Poisson inflow and constant outflow models?

The main assumptions made in Poisson inflow and constant outflow models are that the inflow and outflow rates are constant over time and that the events are independent of each other. This means that the probability of an event occurring at any given time is not affected by previous events.

4. How does Poisson inflow and constant outflow differ from other flow models?

Poisson inflow and constant outflow differs from other flow models, such as the Bernoulli or Binomial models, in that it takes into account the arrival rate of events rather than just the number of events. It also assumes a constant outflow rate, whereas other models may allow for varying rates of outflow.

5. What are some real-world applications of Poisson inflow and constant outflow?

Poisson inflow and constant outflow models have many practical applications, such as predicting the number of customers arriving at a store during a certain time period, estimating the number of defects in a manufacturing process, and analyzing the spread of diseases in a population. They are also used in financial modeling, such as predicting stock market movements or insurance claim rates.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Biology and Medical
Replies
1
Views
1K
  • Electrical Engineering
Replies
2
Views
995
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
Replies
17
Views
3K
Replies
3
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
Replies
7
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
Replies
16
Views
3K
Back
Top