This question asks about a variant of an alternating renewal process.

I am sitting at a cafe watching men and women walk by. The interarrival time $X$ between successive men is iid with distribution $F$, while the interarrival time $Y$ between successive women is iid with distribution $G$. Both $F$ and $G$ are nonlattice. Unlike the usual alternate renewal process, here we have two independent renewal processes, one for each sex.

Is there a nice way to compute the asymptotic probability that the most recent person seen is a man? (The usual theorem doesn't quite apply, since the interarrival times are within-gender only, not from person to person independent of gender.)

I'm interested both in general, and for the specific case that F and G are gamma distributions...

  • $\begingroup$ the probability that the last person seen is a man is not clear for me. It's the probability that the most recent person is a man given... what? The past arrival times? Labeled? $\endgroup$ – leonbloy Jul 3 '11 at 20:27
  • $\begingroup$ You say "we have two independent renewal processes". That is quite a restriction, and is not implied by your earlier words. $\endgroup$ – Henry Jul 3 '11 at 20:48
  • $\begingroup$ Sorry if the statement wasn't clear. Let S_i be the arrival time of the i-th man, where S_i = S_{i-1} + X_i, and X_i is an independent variable with distribution F. (Take S_0 = 0.) Here F is a given distribution, such as a Gamma distribution with parameters k=2 and Theta=3. The arrival times for the women satisfy a similar distribution, with interarrival times Y_i satisfying another distribution G, such as a Gamma distribution with parameters k=4 and Theta=5. The men and women are arriving independently of each other; there is no interaction. $\endgroup$ – Ron Rivest Jul 3 '11 at 21:11
  • $\begingroup$ Additional clarification: Let $P(t)$ be the event that at time $t$ the last person to walk by was a man. The quantity of interest is then $\lim_{t\rightarrow\infty} P(t)$, assuming this is defined. $\endgroup$ – Ron Rivest Jul 3 '11 at 21:44

First consider only one renewal process, describing i.i.d. interarrival times with integrable distribution $F$. Asymptotically, the distribution of the largest interval around the present time without any arrival is the size-biased transform of $F$ (more on this later) and the present time is uniformly distributed in this interval.

In other words, assume that $X$ is a random variable with distribution $F$. Then the size-biased transform of $F$ is the distribution of any random variable $\hat X$ such that $$ E(h(\hat X))=\frac{E(Xh(X))}{E(X)}, $$ for every bounded measurable function $h$. And the time elapsed since the last arrival is asymptotically distributed like $U\hat X$, where $U$ is uniform on $(0,1)$ and independent on $\hat X$.

Now, consider two independent renewal processes, with respective integrable distributions $F$ and $G$. The asymptotic probability that the last event corresponds to the $F$ renewal process is $$ p_F=P(U\hat X\le V\hat Y), $$ where $U$, $\hat X$, $V$ and $\hat Y$ are independent, $U$ and $V$ are uniform on $(0,1)$, the distribution of $\hat X$ is the size-biased transform of $F$ and the distribution of $\hat Y$ is the size-biased transform of $G$. Thus, $$ p_F=\frac{E(XY;UX<VY)}{E(X)E(Y)}, $$ where $X$, $Y$, $U$ and $V$ are independent, $U$ and $V$ are uniform on $(0,1)$, the distribution of $X$ is $F$ and the distribution of $Y$ is $G$.

Our next task is to get rid of $U$ and $V$. To condition on $(X,Y)$, one needs to compute $$ P(Ux<Vy)=[y<x]y/(2x)+[x<y](1-x/(2y)). $$ Unless I made a mistake, this yields


Note that this is only one among several algebraically equivalent formulas for $p_F$.

All the expectations in the formula for $p_F$ are integrals involving $F$, $G$ and the respective densities $f$ and $g$. For example, $$ E(Y^2;Y<X)=E(Y^2(1-F(Y))=\int_0^{+\infty}y^2g(y)(1-F(y))\mathrm{d}y. $$ Post hoc checks: Here are some properties of the result above, which hold and ought to, for the formula to make sense.
(1) One has $p_F+p_G=1$ (where $p_G$ is the result one gets interchanging $X$ and $Y$) and $p_F$ is obviously positive, hence $p_G$ is positive as well. This proves that $p_F$ is in $(0,1)$.
(2) If $F=G$, everything cancels out in the numerator except the $E(2XY;X<Y)$ term, hence $p_F=\frac12$.
(3) If $X$ is exponential with parameter $a$ and $Y$ is exponential with parameter $b$, $p_F=a/(a+b)$.

Edit Regarding check (3) above, for exponential $a$ and $b$ distributions, one can compute everything in the formula giving $p_F$ as a function of $a$ and $b$, starting with $E(X)=1/a$, $E(Y)=1/b$, $f(x)=a\mathrm{e}^{-ax}$, $F(x)=1-\mathrm{e}^{-ax}$, $g(y)=b\mathrm{e}^{-by}$, $G(y)=1-\mathrm{e}^{-by}$.

Furthermore, $E(Y^2;Y<X)=E(Y^2(1-F(Y))$ hence $$ E(Y^2;Y<X)=\int_0^{+\infty}y^2b\mathrm{e}^{-by}\mathrm{e}^{-ay}\mathrm{d}y=\frac{2b}{(a+b)^3}, $$ by symmetry, $E(X^2;X<Y)=2a/(a+b)^3$, and finally, $$ E(XY;X<Y)=\int_0^{+\infty}ax\mathrm{e}^{-ax}\int_x^{+\infty}by\mathrm{e}^{-by}\mathrm{d}y\mathrm{d}x=\int_0^{+\infty}ax\mathrm{e}^{-ax}(x+1/b)\mathrm{e}^{-bx}\mathrm{d}x, $$ hence $E(XY;X<Y)=2a/(a+b)^3+a/(b(a+b)^2)$. Simplifying everything yields the value of $p_F=a/(a+b)$ given above.

Or, one can remember that for exponential interarrival times the arrival times form Poisson processes, that the superposition of two independent Poisson processes with intensities $a$ and $b$ is itself a Poisson process with intensity $a+b$, and finally that each point in the resulting point process is either an $a$-point or a $b$-point, independently of everything else and with respective probabilities $a/(a+b)$ and $b/(a+b)$. Putting all this together, one sees directly why the last event is an $a$-event with probability $p_F=a/(a+b)$.

  • $\begingroup$ Excellent answer! This is very much what I am looking for! Thanks! Could you perhaps show a few details for the computation for (3) (two exponentials) if there is an easy way to see it is $a/(a+b)$?? $\endgroup$ – Ron Rivest Jul 4 '11 at 17:44
  • $\begingroup$ Thanks for the appreciation. See edit. $\endgroup$ – Did Jul 4 '11 at 19:48
  • $\begingroup$ Thanks again for the very clear explanation! Your final note about the superposition of two Poisson processes I was well aware of, but it is good to point out here; the details of the application of your earlier analysis was what I was asking for, and which you give. Thanks again! $\endgroup$ – Ron Rivest Jul 5 '11 at 12:35

If I understand right: arrivals of men are independent from arrivals of women. And each one is a renewal process, with distributions $f(t)$ and $g(t)$ (i.e. $f(t)$ is the probability density for the times between successive men arrivals $X$).

We take a random time $t$ (large, so that initial conditions do not matter and we can assume homogeneity) and call $A$ the "age" of the men arrival process, i.e., the time interval from the last men arrival to time $t$ ; analogously, we call $B$ the "age" of the women arrival. We want to compute the probability that the most recent is a man, that is $P(A < B)$

For this, we must compute the joint probability density of $A,B$. The marginal (density of the "age") is given by

$$p(A) = \frac{1}{E(X)} \int_A^\infty f(t) dt$$

(this can be easily found by a limit argument; check eg here, page 119).

And the same for $B$. And $A,B$ are indepent, hence the probality seeked is computed integrating in the region $A>B$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.