Prev: Gravity and black holes
Next: Is This really a Proof that Standard Math is Inconsistent?
From: ksoileau on 18 Jan 2010 19:49
On Jan 18, 12:41 am, Jim Ferry <corkleb...(a)hotmail.com> wrote:
> Suppose a bathroom has n urinals in a row which are initially
> unoccupied.  Men approach one by one, balking at any urinal adjacent
> to one in use.  Assuming they select urinals uniformly at random from
> the set of those neither in use nor adjacent to one in use (and, for
> simplicity, that they never leave -- think Austin Powers), what is the
> expected fraction of urinals in use when the row fills up, in the
> limit n -> infinity?  The answer clearly lies between 1/3 and 1/2 (the
> densities of the least and most efficient packings), so you might
> think "Cinch!  1/e", but no, the density is greater than 40%.
>
> BTW, some of you may have seen the very row of urinals which inspired
> this problem:  it was in the bathroom near the Employment Center at
> last week's Joint Math Meetings in San Francisco.

I realize this is not what was asked, but I had fun calculating the
number of different end configurations as a function of n:

Let U(n)=the number of different end configurations with n urinals,
U(n,0)=the number of different end configurations with n urinals, with
the first urinal unoccupied,
and U(n,1)=the number of different end configurations with n urinals,
with the first urinal occupied,
Clearly U(n)=U(n,0)+U(n,1).
Also note that for each configuration such that the first urinal is
unoccupied, the second urinals must be occupied because the
configuration is maximal.
Thus U(n,0)=U(n-1,1).
Next, for each configuration such that the first urinal is occupied,
the second urinal must be unoccupied because the configuration is
maximal, and either the third or the fourth urinals (but not both)
must be occupied, again because of maximality.
Hence U(n,1)=U(n-2,1)+U(n-3,1).
Since U(1,1)=1, U(2,1)=1, U(3,1)=1,
the solution to this recurrence is
U(n,1)=(-0.272558-0.0739727 I)*(-0.662359-0.56228*I)^n-
(0.272558-0.0739727 I)*(-0.662359+0.56228 I)^n+0.545116*1.32472^n.
Since U(n,0)=U(n-1,1), we get
U(n,0)=(-0.272558-0.0739727*I)*(-0.662359-0.56228*I)^(n-1)-
(0.272558-0.0739727*I)*(-0.662359+0.56228*I)^(n-1)+0.545116*1.32472^
(n-1).
Since U(n)=U(n,0)+U(n,1), this yields
U(n)=(-0.272558-0.0739727*I)*(-0.662359-0.56228*I)^(n-1)-
(0.272558-0.0739727*I)*(-0.662359+0.56228*I)^(n-1)+0.545116*1.32472^
(n-1)+(-0.272558-0.0739727 I)*(-0.662359-0.56228*I)^n-
(0.272558-0.0739727 I)*(-0.662359+0.56228 I)^n+0.545116*1.32472^n.



From: Jim Ferry on 18 Jan 2010 23:00
On Jan 18, 6:36 pm, Ilan Mayer <ilan_no_s...(a)hotmail.com> wrote:
> On Jan 18, 4:43 am, Henry <s...(a)btinternet.com> wrote:
> > On 18 Jan, 06:41, Jim Ferry <corkleb...(a)hotmail.com> wrote:
>
> > > Suppose a bathroom has n urinals in a row which are initially
> > > unoccupied.  Men approach one by one, balking at any urinal adjacent
> > > to one in use.  Assuming they select urinals uniformly at random from
> > > the set of those neither in use nor adjacent to one in use (and, for
> > > simplicity, that they never leave -- think Austin Powers), what is the
> > > expected fraction of urinals in use when the row fills up, in the
> > > limit n -> infinity?  The answer clearly lies between 1/3 and 1/2 (the
> > > densities of the least and most efficient packings), so you might
> > > think "Cinch!  1/e", but no, the density is greater than 40%.
>
> > The expected density tends towards 1/2 - exp(-2)/2 = 0.432... from
> > above as n increases

Yep. Nice job, Henry. This may also be written sinh(1)/e ("Cinch! 1/
e" -- sorry).

>
> There is an analysis of an equivalent problem athttp://algo.inria.fr/libraries/autocomb/fatmen-html/fatmen1.html

Ah! Thank you for the reference. My analysis was similar, except
that (a) I converted to a circular configuration, (b) I took the
generating function approach further, but (c) I didn't pursue the
overall analysis nearly as far.

Letting b_n(x) be a polynomial in which the coefficient of x^k is the
probability of k men at n urinals arranged in a row, and c_n(x) be the
corresponding polynomial for a circular configuration, we note that c_n
(x) = x b_(n-3)(x), so it is simple enough to convert between the
two. The governing relationship for c_n(x) is

c_n(x) = 1/(n-3) SUM(k = 2 to n-2) c_k(x) c_(n-k)(x), c_2(x) = c_3(x)
= x.

The convolution suggests letting f(x,y) = SUM(n = 2 to infinity) c_n
(x) y^n, which has the governing equation f(x,y)^2 = y df(x,y)/dy - 3 f
(x,y) + x y^2. This is an ODE in y with x as a parameter. After
constraining the general solution to agree with c_3(x) = x, we obtain

f(x,y) = x y^2 (sqrt(x) + tanh(sqrt(x) y)) / (sqrt(x)(1-y) + (1 - x y)
tanh(sqrt(x) y)).

Evaluating df/dx at x = 1 gives the generating function for expected
value: df(1,y)/dx = y^2 (2 - y - y e^(-2 y))/(2 (1 - y)^2). From
this we obtain an exact expression for the expected number:

mu(n) = n (1/2 - SUM(j = 0 to n) (2 - j)/8 (-2)^j/j!),

which converges very quickly to n sinh(1)/e.
From: mike on 19 Jan 2010 17:11
In article <slrnhl8vp4.tvn.usenet2(a)melkki.cs.helsinki.fi>, usenet2
@vyznev.invalid says...
> On 2010-01-18, Jim Ferry <corklebath(a)hotmail.com> wrote:
> > Suppose a bathroom has n urinals in a row which are initially
> > unoccupied. Men approach one by one, balking at any urinal adjacent
> > to one in use. Assuming they select urinals uniformly at random from
> > the set of those neither in use nor adjacent to one in use (and, for
> > simplicity, that they never leave -- think Austin Powers), what is the
> > expected fraction of urinals in use when the row fills up, in the
> > limit n -> infinity?
>
> The assumption that nobody ever leaves makes a big difference. If,
> instead, we assume that men do occasionally leave, but that there's a
> queue from which any vacancies are immediately filled, then the number
> of occupied urinals will almost surely converge to n/2 for even n or
> (n+1)/2 for odd n.
>
So for 2n urinals (mounted in a circle so each has two neighbours), what
is the expected number of arrivals before occupancy = n, as a function
of n?

--Mike
From: Andrew Erickson on 19 Jan 2010 21:58
In article
<510c95b4-50ef-41af-b3ce-638d20706a49(a)c34g2000yqn.googlegroups.com>,
ksoileau <kmsoileau(a)gmail.com> wrote:

> On Jan 18, 5:36�pm, Ilan Mayer <ilan_no_s...(a)hotmail.com> wrote:
> > On Jan 18, 4:43�am, Henry <s...(a)btinternet.com> wrote:
> >
> >
> >
> >
> >
> > > On 18 Jan, 06:41, Jim Ferry <corkleb...(a)hotmail.com> wrote:
> >
> > > > Suppose a bathroom has n urinals in a row which are initially
> > > > unoccupied. �Men approach one by one, balking at any urinal adjacent
> > > > to one in use. �Assuming they select urinals uniformly at random from
> > > > the set of those neither in use nor adjacent to one in use (and, for
> > > > simplicity, that they never leave -- think Austin Powers), what is the
> > > > expected fraction of urinals in use when the row fills up, in the
> > > > limit n -> infinity? �The answer clearly lies between 1/3 and 1/2 (the
> > > > densities of the least and most efficient packings), so you might
> > > > think "Cinch! �1/e", but no, the density is greater than 40%.
> >
> > > > BTW, some of you may have seen the very row of urinals which inspired
> > > > this problem: �it was in the bathroom near the Employment Center at
> > > > last week's Joint Math Meetings in San Francisco.
> >
> > > The expected density tends towards 1/2 - exp(-2)/2 = 0.432... from
> > > above as n increases
> >
> > There is an analysis of an equivalent problem
> > athttp://algo.inria.fr/libraries/autocomb/fatmen-html/fatmen1.html
> >
> > Please reply to ilan dot mayer at hotmail dot com
> >
> > � �__/\__
> > � �\ � �/
> > __/\\ �//\__ �Ilan Mayer
> > \ � � � � �/
> > /__ � � �__\ �Toronto, Canada
> > � /__ �__\
> > � � �||
>
> I think this problem for n urinals in a row is equivalent to the
> problem of n+1 urinals arranged in a circle which starts with one
> occupied urinal.

It seems to me that the equivalent would be n+3, not n+1, as the end
stalls for the linear case are not inherently disallowed, while those
adjacent to the seed person in the circular case are. This is perhaps
clearest by analyzing the base case where n=1.

--
Andrew Erickson

"He is no fool who gives what he cannot keep to gain that which he cannot
lose." -- Jim Elliot
From: Anthony Buckland on 20 Jan 2010 21:27

"mike" <m.fee(a)irl.cri.replacethiswithnz> wrote in message
news:MPG.25c0f5389eaf649d989773(a)news.comnet.net.nz...
> ...
> So for 2n urinals (mounted in a circle so each has two neighbours), what
> is the expected number of arrivals before occupancy = n, as a function
> of n?
> ...

Unless the arrivals are by elevator inside the circle, the occupancy
stays at zero, or the number of unfortunate men present when
the circle was closed.


First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4
Prev: Gravity and black holes
Next: Is This really a Proof that Standard Math is Inconsistent?