Prev: Gravity and black holes
Next: Is This really a Proof that Standard Math is Inconsistent?
From: Ilmari Karonen on 22 Jan 2010 06:03
On 2010-01-22, Phil Carmody <thefatphil_demunged(a)yahoo.co.uk> wrote:
> Ilmari Karonen <usenet2(a)vyznev.invalid> writes:
>> On 2010-01-19, mike <m.fee(a)irl.cri.replacethiswithnz> wrote:
>>> 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?
>>
>> Good question. I don't have a full answer, but even just the mean
>> number of arrivals needed to go from n-1 occupied urinals to n seems
>> to scale as O(n^4). It's that last gap that takes the longest to
>> fill, though. I have a vague hunch that the total number of arrivals
>> needed to go from 0 to n might be something like O(n^4 log n), but I
>> could be completely wrong there.
>
> There is no 'last gap', surely? There are two last gaps, and they
> slowly perform a random walk towards and away from each other until
> they finally meet, at which point there's a 2/3 chance that the new
> arrival will leave space for another new arrival and finish the
> circle.

Depends on what one means by "gap". I used that word in an earlier
post in the same sense as you did here, to refer to two adjacent
unoccupied urinals. In a state where no more urinals can be
immediately occupied, there will (on a circle) always be m-2n of
those, where m is the total number of urinals and n the number of
occupied ones.

In the paragraph you quoted above, though, I was trying to use "gap"
as just a shorthand for "potential vacancy that could accommodate one
more person if the ones already present were moved appropriately", of
which there are floor(m/2)-n. I apologize for that bit of needlessly
confusing misuse of terminology.

Anyway, you're exactly right about what happens. In fact, save for
that final 2/3 merging probability (and the fact that all the
transition rates must be scaled by 1/(n-1) to account for the fact
that most departures and arrivals cause no change in the occupancy),
the process is exactly equivalent to the well known Drunkard's Walk
problem. That's how I derived my O(n^4) estimate.

--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
From: Stormin Mormon on 22 Jan 2010 20:27
The most efficient pack would be three urinals occupied by
two patrons. Which would be 101.

Figuring for more than 3 urinals, the most efficient usage
would be 10101010 which leads to 50% usage. Beyond that, too
complicated for me.

--
Christopher A. Young
Learn more about Jesus
www.lds.org
..


"Jim Ferry" <corklebath(a)hotmail.com> wrote in message
news:e205cc11-df35-4460-b6a1-8e67c9373a91(a)a32g2000yqm.googlegroups.com...
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.


From: gerson on 26 Jan 2010 06:41

"Ilmari Karonen" <usenet2(a)vyznev.invalid> wrote in message news:slrnhl8vp4.tvn.usenet2(a)melkki.cs.helsinki.fi...
> 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.

> Ilmari Karonen
> To reply by e-mail, please replace ".invalid" with ".net" in address.

Does anybody remember a science fiction story about nobody noticing
anybody leaving - it was a bar and people were sitting on barstools,
waiting, perhaps like "Seconds", or hmm "the great divorce" - or was it
the "great Gatsby", as in not noticing - does not noticing make a difference ?


From: Eric Sosman on 26 Jan 2010 09:03
On 1/26/2010 6:41 AM, gerson wrote:
> "Ilmari Karonen"<usenet2(a)vyznev.invalid> wrote in message news:slrnhl8vp4.tvn.usenet2(a)melkki.cs.helsinki.fi...
>> 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.
>
>> Ilmari Karonen
>> To reply by e-mail, please replace ".invalid" with ".net" in address.
>
> Does anybody remember a science fiction story about nobody noticing
> anybody leaving - it was a bar and people were sitting on barstools,
> waiting, perhaps like "Seconds", or hmm "the great divorce" - or was it
> the "great Gatsby", as in not noticing - does not noticing make a difference ?

If they spend all that time at the bar, won't they
eventually need to visit the urinals?

--
Eric Sosman
esosman(a)ieee-dot-org.invalid
First  |  Prev  | 
Pages: 1 2 3 4
Prev: Gravity and black holes
Next: Is This really a Proof that Standard Math is Inconsistent?