4
$\begingroup$

People arrive at some shop as Poisson process of rate $N$. There are $N$ corridors in the shop and each customer chooses one at random, independently of the other customers. Now let $X_t^N$ be the proportion of corridors which remain empty at time $t$ and $T^N$ the time until half of the corridors have at least one customer, then it holds that $X_t^N\rightarrow e^{-t}, T^N\rightarrow \log 2$ for $N\rightarrow \infty$ in probability.

Well I started step by step. Let $X$ be the RV that describes the number customers that arrived, then we know $P(X=k)=\frac{N^k e^{-N}}{N!}$. I denote each customer with a number so $P$(customer i chooses some corridor)$=\frac{1}{N}$. How can I continue?

$\endgroup$
2
  • 1
    $\begingroup$ Using $X_t^N$ to be something and $X$ to mean something very different (that should depend on $t$) may cause confusion. $\endgroup$
    – Henry
    Feb 1, 2014 at 7:26
  • 2
    $\begingroup$ In fact $P(X=k)=\dfrac{(Nt)^k e^{-Nt}}{k!}$ $\endgroup$
    – Henry
    Feb 1, 2014 at 7:28

1 Answer 1

4
+50
$\begingroup$

What follows can be tightened up, but essentially the position is that with $N$ corridors and a rate of $N$, each corridor is filled independently with a rate of $1$, which does not change with $N$.

So at time $t$, the probability an individual corridor is still empty is $e^{-t}$ and so the probability that that the proportion $\frac{k}{N}$ of the corridors are empty is ${N \choose k}e^{-kt}(1-e^{-t})^{N-k}$. The expected number of corridors empty is $Ne^{-t}$ and the expected proportion of corridors empty is $e^{-t}$. The law of large numbers tells you that as $N$ increases without limit, the proportion of corridors empty converges on its expectation, i.e. to $e^{-t}$.

Solving $e^{-t} = \frac12$ gives $t= \log_e 2$, so both the median time at which a particular corridor is filled and the limit of the time of when half the corridors are filled as the number of corridors increases are $\log_e 2$. You could have achieved this result without the previous result, since the sample median converges on the population median as the sample size increases.

$\endgroup$
5
  • $\begingroup$ Thanks for your answer. I award the bounty and have therefore some questions. First why should it be true: "with N corridors and a rate of N, each corridor is filled independently with a rate of 1"?. I think the whole thing is a little bit more complicated, since for example for $T^N$ we need at least $\lceil \frac{N}{2}\rceil$ customers. Basically $P(U=k|X\ge\lceil \frac{N}{2}\rceil)$, where $X$ is the number of customers arrived and $U$ is binomial distributed. Note I'm not sure if $U$ is really binomial distributed. $\endgroup$
    – math
    Feb 2, 2014 at 15:28
  • $\begingroup$ On your first part of your comment, it might be easier to see it in the other direction. If the rate for arriving at each corridor is $1$ then the rate for arriving at the $N$ corridors is $N \times 1 = N$. And if the arrivals in each corridor are independent Poisson process (i.e. with memoryless exponentially distributed inter-arrival times) then the combined arrivals are also a Poisson process, just at a faster rate. $\endgroup$
    – Henry
    Feb 2, 2014 at 17:40
  • $\begingroup$ On the second part of your comment, I did not use $X$ (the number of customers that had arrived overall). If you did then you would get into a form of the coupon collector's problem: You would want to combine the probability that $X=k$ had arrived with the probability that $k$ individuals were in at least $N/2$ distinct corridors. The latter expression would be very messy, though you are correct that it would be zero if $k \lt N/2$. $\endgroup$
    – Henry
    Feb 2, 2014 at 17:56
  • $\begingroup$ Thanks for your comment. I will check the whole thing tomorrow. Yes, I think it will be messy but maybe for easier to understand. $\endgroup$
    – math
    Feb 2, 2014 at 18:01
  • $\begingroup$ @user8: It's a pretty fundamental (and important) property of Poisson processes that splitting a Poisson process gives Poisson processes again. See e.g. Splitting a Poisson Process at the excellent Virtual Laboratories in Probability and Statistics website of the University of Alabama in Huntsville. $\endgroup$ Feb 6, 2014 at 9:24

You must log in to answer this question.

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