1
$\begingroup$

A bank has $N$ counters in a row, and customers arrive irregularly at an average of 1 per minute (say, according to a normal distribution with variance $\sigma^2$ – but I don't think that is significant). Each customer needs $k$ minutes for his operation ($k$ need not be integer), say like $k=N/2$ or $k=N/3$. As the customers prefer to do their business with maximal discretion, each one will choose a free counter at biggest possible distance from any occupied counter at the moment he arrives. (There is a somewhat small probability that all counters are already occupied, then he'd of course just wait for the first to be freed. Ignoring this uninteresting case won't change a lot I think.) To avoid trivialities, let's say $N\ge 6$ and imagine the process going on for a long time. Question:

  • What is the average proportion of time during which there are no two adjacent counters with customers, in terms of $N$ and $k$ (unless $\sigma$ also plays a role)?

Now, as we mathematicians do not necessarily worry about constraints of real life and such things, let's feel free to also consider a continuous version of the problem (which may even be more easy to treat): instead of $N$ counters in a row, we can imagine a circle or more generally a unit sphere $S_n$, each point of which is a potential counter. The (rather small) customers still arrive at an average of 1 per minute. Though the counters aren't discrete anymore, the customers still are as discreet as possible, so each one chooses a point on $S_n$ furthest away from all occupied points and does his business, which takes $k$ minutes. (E.g. on $S_2$ for $k$ big enough, there are very good chances that the six first customers are at the corners of an octahedron. Note that if the two first ones occupy the poles and thus the third one a point on the equator, then the fourth one would not only be somewhere on a half of the equator, but he must choose the antipodal point of the third one, to be as far away as possible from him, too. So I mean 'furthest away from all of them' in a stricter sense, hopefully well-defined, which might make the question more interesting by the possibly more frequent presence of certain patterns, see below.)
For a threshold $\epsilon$, we'll define $f_n(k,\epsilon)$ as the average proportion of time when any two customers on the sphere are more than $\epsilon$ away from each other in Euclidean distance.

  • Are there good lower and upper bounds for $f_n(k,\epsilon)$?

  • Is it true (or even straightforward) that $f_n(k,\epsilon)$ is continuous as a function of $\epsilon$? It may be conceivable that for certain triples $(n,k,\epsilon)$ there are patterns of certain polytopes that occur frequently, causing $f$ to jump in a neighborhood.

  • Does the picture change if we start with a boundary condition of the following kind? At time $t=0$, let there be already a number of customers at certain (random) points, each one having already done a (random) part of his business? Note that by 'average ratio', I mean more precisely the ratio over a total time $T\to\infty$, and I'd think that the presence or not of such a boundary condition does not change anything – but this doesn't seem straightforward.

I wouldn't be surprised if this kind of problem has already been examined somewhere. Pointers welcome.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.