Return to 2-story apartment 8 units
amcwill417
news:mHT1b.239520$uu5.49153@sccrnsc04...
> Hi All,
>
> The bottomless stein is back!! It is given to the tenant in apartment one
> of an 8 unit apartment laid out as follows:
>
> TOP FLOOR BOTTOM FLOOR
>
> _________ __________
> | | | | | |
> | #2 | #3 | | #6 | #7 |
> |-----------| |-------------|
> | apt | | | | |
> | #1 | #4 | | #5 | #8 |
> ------------ --------------
>
> Yes, you've guessed correctly, I'm not an architect. And yes, the
> mailperson won't like the way the apartments are numbered.
>
> Now each apartment has 2 walls plus a floor/ceiling with a hole,
sufficient
> in size to pass the bottomless stein. Thus, for example, the person in
> apartment #1 can pass the stein to apt #2, apt #4, or apt #5.
>
> Now assume the stein first appears in apt #1. On this SOLE occasion the
> tenant does NOT drink from the stein before randomly passing it.
Question:
> For each apartment, what is the probability that it's tenant is the last
to
> take a first drink?
>
> Best wishes, Jim
Since the original thread seems to be gone from this NG I have repeated the
original problem (shown above). The picture, again:
> TOP FLOOR BOTTOM FLOOR
>
> _________ __________
> | | | | | |
> | #2 | #3 | | #6 | #7 |
> |-----------| |-------------|
> | apt | | | | |
> | #1 | #4 | | #5 | #8 |
> ------------ --------------
>
One can change this from a 3D representation to a 2D one as shown below:
2 3 7 6 2 3 7 6 2 3 7 6
1 4 8 5 1 4 8 5 1 4 8 5
with the above apartment layout continuing indefinitely both to the right
and to the left. Thus, in a plane, there are two infinitely long rows of
numbered apartments. Another pattern which does the same thing is:
4 3 7 8 4 3 7 8 4 3 7 8
1 2 6 5 1 2 6 5 1 2 6 5
The stein leaving an apartment numbered "1" would randomly travel thereafter
with the motion being confined to single horizontal and single vertical
steps (but no diagonal steps). Thus 1 is followed by either 2, 4 or 5 , for
example.
The above gives a somewhat different way of looking at this problem and
comes close to a random walk in 1D.
Alex
Macavity
Did anyone do this problem - I mean find an expression analytically?
Looks like I missed most of the thread.
Anyway, here is my incomplete attempt...
=============================================================
We can use the symmetry of the cube to cut down problems a bit.
First, note the alternate vector notations in brackets for each room
in the diagram below, which I found more convenient (in fixed pitch).
2 3
+-------------------+
/|(i) /|(i+j)
/ | / |
/ | / |
/ | / |
Start ---> 1 +-------------------+ 4 |
(0)| | |(j) |
| | | |
| | | |
| |6 | |7
| +--------------|----+(i+j+k)
| /(i+k) | /
| / | /
| / | /
(k)|/ (j+k)|/
5 +-------------------+ 8
Now, let p(X) denote the probability that X is the last drinker.
Also, let |X| denote the shortest distance along the lattice.
Then by symmetry, p(X) must be a function of |X| only. Hence let
p(X) =
-------
= a if |X| = 0
= b if |X| = 1
= c if |X| = 2
= d if |X| = 3
As Sum {over all X: p(X)} = 1, we have
a + 3b + 3c + d = 1 ....(E1)
we need four equations...
========================
Let p(X|Y) denote the probability that X is the last drinker, given
that Y is the first drinker. In our problem, |Y| = 1, but this need
not be a restriction for the definition.
Then, by symmetry, p(X|Y) must be a function of |X-Y|. So we have a
table of unknowns:
p(X|Y) =
---------
= a_1 if |X-Y| = 1
= b_1 if |X-Y| = 2
= c_1 if |X-Y| = 3
Further, we have the following equation:
Sum {over |Y| = 1; p(X|Y)/3} = p(X)
It is enough to evaluate the equations for distinct cases of |X|. X =
1, 2, 3, 7 must cover all cases.
Sum {over |Y| = 1; p(1|Y)/3} = p(1)
=> p(1|2) + p(1|4) + p(1|5) = 3* p(1)
=> 3 a_1 = 3*a or a_1 = a
Taking X = 2 in the same equation,
=> p(2|2) + p(2|4) + p(2|5) = 3 p(2)
=> 0 + b_1 + b_1 = 3 b
=> b_1 = 3b/2
Taking X = 3 in the equation,
=> p(3|2) + p(3|4) + p(3|5) = 3 p(3)
=> a_1 + a_1 + c_1 = 3 c
=> c_1 = 3c - 2a
Similarly, taking X = 7 in the same equation,
=> p(7|2) + p(7|4) + p(7|5) = 3 p(7)
=> 3 b_1 = 3d or b_1 = d
But b_1 = 3b/2
=> 3b = 2d ....(E2)
Summarising,
p(X|Y) =
---------
= a if |X-Y| = 1
= d if |X-Y| = 2
= 3c-2a if |X-Y| = 3
and we also got the additional relationship
3b = 2d ....(E2)
===========================
Now let p(X|YZ) denote the probability that X is the last drinker,
given that Y is the first drinker and Z the second. Here, by
definition, |Y-Z| = 1.
Again, by symmetry, p(X|YZ) must be a function of |X-Y| and |X-Z|. So
we need to consult only the unknowns in the following table for
p(X|YZ):
|X-Z|
p(X|YZ) | |
| 1 | 2 | 3 |
---------+---------------------+
| | | |
1 | - | a_2 | - |
| | | |
|X-Y| 2 | b_2 | - | c_2 |
| | | |
3 | - | d_2 | - |
| | | |
---------+---------------------+
Again, with the following equation:
Sum{over all allowable Z; p(X|YZ)/3} = p(X|Y)
Keeping Y = 2, let us try distinct |X-Y| possibilities. X = 1, 4, 8
cover these.
Taking X = 1,
Sum{over allowable Z; p(1|YZ)/3} = p(1|Y)
=> p(1|21) + p(1|23) + p(1|26) = 3 p(1|2)
=> 0 + a_2 + a_2 = 3 a
=> a_2 = 3a/2
Taking X = 4,
=> p(4|21) + p(4|23)+p(4|26) = 3 p(4|2)
=> b_2 + b_2 + c_2 = 3d
=> 2 b_2 + c_2 = 3d
Taking X = 8
=> p(8|21) + p(8|23) + p(8|26) = 3 p(8|2)
=> d_2 + d_2 + d_2 = 3 (3c-2a)
=> d_2 = 3c - 2a
There are no more distinct equations, so we are left with
a_2 = 3a/2
b_2 = ?
c_2 = 3d-2b_2
d_2 = 3c-2a
which does not add much to our understanding of the original problem.
Am I missing any relationships? Or does one have to keep plodding on?
====================================
Alternate approaches:
* A 3D random walk mod 2? Gets crazy.
* A Markov process - state defined by drunken people and where the
stein is. Too many possible states! If you assume 0 denotes not
drunk, 1 denotes drunk and -1 where the stein is, possibly a state
transition matrix of dimension
8 * 2^7 = 1024 or so?
At this point I gave up... will try again during the weekend. If
someone had answered, please repost.
HTH. If not in maths, looks like I score in architecture;)
amcwill417
cut---
> Now, let p(X) denote the probability that X is the last drinker.
> Also, let |X| denote the shortest distance along the lattice.
>
> Then by symmetry, p(X) must be a function of |X| only. Hence let
> p(X) =
> -------
> = a if |X| = 0
> = b if |X| = 1
> = c if |X| = 2
> = d if |X| = 3
>
> As Sum {over all X: p(X)} = 1, we have
> a + 3b + 3c + d = 1 ....(E1)
>
cut---
The shortest distance to apartment #1 seems to be 2 (the stein has to move
2 steps to get to #1) so should not the above equation read:
3b + 4c + d = 1 ?
Alex
Macavity
The distance is measured along the lattice with 0 as the origin. No
reference to the stein.
2 3
+-------------------+
/|(i) /|(i+j)
/ | / |
/ | / |
/ | / |
Start ---> 1 +-------------------+ 4 |
(0)| | |(j) |
| | | |
| | | |
| |6 | |7
| +--------------|----+(i+j+k)
| /(i+k) | /
| / | /
| / | /
(k)|/ (j+k)|/
5 +-------------------+ 8
|0| = 0; corresponds to apartment #1
|i| = |j| = |k| = 1; correspond to apartments #2, #4 and #5
|i+j| = |j+k| = |k+i| = 2; correspond to apartments #3, #8 and #6
|i+j+k| = 3; corresponds to apartment #7
Hence a + 3b + 3c + d.
Anyway, the only relations I got using that were
a + 3b + 3c + d = 1 and
3b = 2d
More relations are needed if one is to solve using that method.
HTH.
Jim Dars
"amcwill417" <amcwi...@email.msn.com> wrote in message
news:qKK8b.331$wS2....@eagle.america.net...
As I recall the problem was Monte Carloed into oblivion, all using different
languages and programs, and arriving at the same answer. As I recall I
added to this solution with comments such as "Since you've Monte Carloed it
10^8 times, why not 10^80 times for greater accuracy" --- which all were
happy to do. I don't believe anyone was able to establish a closed form
solution. Nor did the Monte Carlo results suggest a closed form solution.
Although, Mac, the apparent symmetries were shown to obtain.
Best wishes, Jim
amcwill417
The picture:
> >> TOP FLOOR BOTTOM FLOOR
> >>
> >> _________ __________
> >> | | | | | |
> >> | #2 | #3 | | #6 | #7 |
> >> |-----------| |-------------|
> >> | apt | | | | |
> >> | #1 | #4 | | #5 | #8 |
> >> ------------ --------------
> >>
As an aside it may be of some interest to note that the arrangement can be
presented differently. Here is a 2nd layout of the apartments on a single
flat strip:
________________
#2 #3 #7 #6
#1 #4 #8 #5
________________
If this is wound around a cylinder (or your finger, or the Seattle space
needle) the same relations pertain as in the 3D model - although the
symmetries may not be as obvious.
One can also stay in one plane by repeating the above array both to the
right and the left indefinitely - as a 3rd arrangement of the apartments
(now infinite in number).
Alex.
Mike Terry
news:9660ac79d91802fb...@news.teranews.com...
I posted a methodology that could be followed mechanically to calculate the
exact probabilities. I had a go at applying this to various smaller
networks, e.g. a 2x2 square (trivial) and a "square pyramid" with 5 nodes
(not so trivial, but doable). I also had a go at an octahedron version (6
nodes), but made several mistakes, so I lost confidence in the result I
obtained.
All this convinced me that to apply my method to the original problem (2x2x2
cube) would require a computer program to keep track of all the branches and
solve the required simultaneous linear equations reliably...
And as I have some time at the moment, I've started to write the program!
I'll post again when it's working (probably a couple of days) and then we
can check how accurate all the Monte Carlo simulations were - or maybe just
how accurate my programming is!! :-)
My original post with the algorithm I'll be using for my program will be
captured on Google, if you're interested.
Regards,
Mike.
Chip Eastham
"Macavity" <mxy...@hotmail.ignore.com> wrote in message
news:9660ac79d91802fb...@news.teranews.com...
> <amcwi...@email.msn.com> wrote:
>
> >"Jim Dars" <jim-...@comcast.net> wrote in message
> >news:mHT1b.239520$uu5.49153@sccrnsc04...
> >> Hi All,
> >>
> >> The bottomless stein is back!! It is given to the tenant in apartment
one
> >> of an 8 unit apartment laid out as follows:
> >>
> >>
> >> Now assume the stein first appears in apt #1. On this SOLE occasion
the
> >> tenant does NOT drink from the stein before randomly passing it.
> >Question:
> >> For each apartment, what is the probability that it's tenant is the
last
> >to
> >> take a first drink?
> >>
> >> Best wishes, Jim
> >
>
>
> Did anyone do this problem - I mean find an expression analytically?
> Looks like I missed most of the thread.
>
> Anyway, here is my incomplete attempt...
>
[snip]
Mike Terry outlined an approach to solving it analytically in the
original thread, and I elaborated on such an approach, involving
a chain of Markov processes that take advantage of symmetry
in accounting for the locations of each additional drinker. Mike
has already posted another note in this thread, so I won't try to
make a full recapitulation.
As an illustration of the ideas, let me point out that a somewhat
more natural variation of Jim's problem, where the occupant who's
initially in possession of the stein DOES take a drink (see above),
is simpler (in the sense of having only two unknown parameters)
and can be used to solve Jim's version.
If the first occupant takes a drink before passing, then obviously
the chance that occupant will be last to drink is zero. The chances
for each apartment are then distributed like this:
[0,p,p,p',p,p',p',p"]
where I've enumerated the apartments in an order corresponding
to vertices of a cube {0,1}x{0,1}x{0,1} like this:
(0,0,0) --> #0 (1,0,0) --> #4
(0,0,1) --> #1 (1,0,1) --> #5
(0,1,0) --> #2 (1,1,0) --> #6
(0,1,1) --> #3 (1,1,1) --> #7
Certain apartments/occupants have equal chance of being last in
view of their equivalent positions under rotations of the cube that
preserve the stein's initial location.
p" = 1 - 3(p + p'), so there are really only unknowns p,p' to find.
Jim's original version, in which the stein is passed the first time
without a drink, then "blends" three copies of this modified set
of probabilities by the equally likely passing of the stein from #0
to #1, #2, or #4. Thus in terms of p and p' the answer to Jim's
version would be:
(1/3)*[p,0,p',p,p',p,p",p'] +
(1/3)*[p,p',0,p,p',p",p,p'] +
(1/3)*[p,p',p',p",0,p,p,p']
which gives (for the original problem):
Pr(#0 last to drink) = p
Pr(#1 last to drink) = (2/3)p'
Pr(#2 last to drink) = (2/3)p'
Pr(#4 last to drink) = (2/3)p'
Pr(#3 last to drink) = (1/3)(1 - p) - p'
Pr(#5 last to drink) = (1/3)(1 - p) - p'
Pr(#6 last to drink) = (1/3)(1 - p) - p'
Pr(#7 last to drink) = p'
These sorts of analytical methods can be combined with the
Monte Carlo calculations to advantage. For example, if the
Monte Carlo trials are begun with three occupants already
having drunk from the stein (arranged in an "ell" shape),
then presumably the distribution of the "last drinkers" will
be determined more precisely by the random movements
of the stein (conditioned upon those initial conditions) than
if each trial starts "from scratch". Of course it is necessary
to relate the results conditioned on an "ell" configuration
back to Jim's original problem by a more elaborate but
similar calculation to that outlined above.
To carry out the full analytical solution requires the
analysis of about 15 configurations, and though tedious
it can be done manually. The Markov chain formulation
makes evident that p, p' and all related chances are just
rational numbers.
regards, chip
Mike Terry
news:bld2ei$anlfj$1...@ID-201979.news.uni-berlin.de...
the
> exact probabilities. I had a go at applying this to various smaller
> networks, e.g. a 2x2 square (trivial) and a "square pyramid" with 5 nodes
> (not so trivial, but doable). I also had a go at an octahedron version (6
> nodes), but made several mistakes, so I lost confidence in the result I
> obtained.
>
> All this convinced me that to apply my method to the original problem
(2x2x2
> cube) would require a computer program to keep track of all the branches
and
> solve the required simultaneous linear equations reliably...
>
> And as I have some time at the moment, I've started to write the program!
> I'll post again when it's working (probably a couple of days) and then we
> can check how accurate all the Monte Carlo simulations were - or maybe
just
> how accurate my programming is!! :-)
...and here are the final results:
First, the exact probabilities corresponding to the original problem, where
the stein is introduced to Apt.0, but no drinking occurs there:
Prob(Apt.1 last to drink) = 8483/65835
Prob(Apt.2 last to drink) = 6598/65835
Prob(Apt.3 last to drink) = 27661/197505
Prob(Apt.4 last to drink) = 6598/65835
Prob(Apt.5 last to drink) = 6598/65835
Prob(Apt.6 last to drink) = 27661/197505
Prob(Apt.7 last to drink) = 3299/21945
Prob(Apt.8 last to drink) = 27661/197505
If the occupant in Apt.0 drinks before passing it on for the first time, the
probabilities evaluate as follows:
Prob(Apt.1 last to drink) = 0
Prob(Apt.2 last to drink) = 8483/65835
Prob(Apt.3 last to drink) = 3299/21945
Prob(Apt.4 last to drink) = 8483/65835
Prob(Apt.5 last to drink) = 8483/65835
Prob(Apt.6 last to drink) = 3299/21945
Prob(Apt.7 last to drink) = 713/4389
Prob(Apt.8 last to drink) = 3299/21945
(my program calculates these results first and uses them to calculate the
earlier set, as chip described)
Checking the results of Bill's simulation against the exact results shows he
was pretty much on track (to well within a fraction of a percent)...
Regards,
Mike.
Jim Dars
"Chip Eastham" <eas...@bellsouth.net> wrote in message
news:mkqdnSewNtr...@comcast.com...
I originally suggested that one might work backwards, namely if the stein is
at location r and only s and t have not had a drink, then calculate
P[s(s,t)|r]. Then obviously, P[t(s,t)|r] = 1 - P[s(s,t)|r]. This seems
like a large number of calculations, but I suspect symmetry greatly reduces
the number. Once these values are determined couldn't one determine, say,
P[u(s,t,u)|r] from the 6 existing values of the (s,t,u)|r pairs problem?
etc. {The original symmetries should work their way back into the problem.
Also, obvious things like #2, #4, and # 5 can't all be in the parenthesis.}
Frankly, I did not find the P[s(s,t)|r] problem easy, but I suspect I was
missing something elementary. --- Since all ignored the post perhaps
P[s(s,t)|r] is not easy?.
Best wishes, Jim
Chip Eastham
Hi, Jim:
I suspect that this "working backward" suggestion is very much in the
spirit of how Mike Terry approached the problem. Note that his reply in
the original thread also speaks of working backward, particularly with the
observation that when only one location has not had a drink, the outcome
is determined (regardless of the current location of the stein).
I believe that my work takes optimal advantage of symmetries. Therefore
I phrased my suggestions along the lines of first "working forward," which
uncovers a minimal net of configurations for which the "conditional"
probabilities can be pieced together.
You've suggested that the cases in which all but two have drunk might
be so difficult as to discourage analysis, but the Markov chain approach
outlined in my replies to the original thread will handle them. I found six
configurations of "six drinkers" to be sufficient, and I gave them these
names:
shoulder, leg, hip, belt, girdle
The shoulder and hip configurations are the same subsets of drinkers,
namely all but two adjacent apartment locations, and differ only as to
the stein's current location (of which terms shoulder and hip are meant
to be suggestive). Similarly leg and belt are configurations that have
the same subsets of drinkers but differing current locations of the stein.
The girdle configuration omits two locations from having drunk that
are "antipodal", i.e. as far apart as possible (one on the bottom floor
and the other on the top floor at the far corner). Let's use this example
to illustrate how the probability distribution of outcomes can be found
using the Markov chain model.
Recall my labeling of the apartments as 0-7 connected as vertices of
the cube so that 0 is adjacent to 1,2,4; etc. Because of high symmetry,
if 3,4 are the "missing" locations, any one of the other locations can
serve equally as the stein's current location. Let's say the stein starts
in location 7.
The states of the Markov process are a combination of:
- the set of locations where a drink has already been taken
- the stein's current location (one of the above, except initially)
My idea is to consider a "narrow" problem of the transistion from
six drinkers to seven drinkers. We have the following states in
which the stein passes among locations where a drink has already
been taken:
(7,{0,1,2,5,6,7}) START
(0,{0,1,2,5,6,7})
(1,{0,1,2,5,6,7})
(2,{0,1,2,5,6,7})
(5,{0,1,2,5,6,7})
(6,{0,1,2,5,6,7})
together with the following two states in which an additional
drinker accrues:
(3,{0,1,2,3,5,6,7})
(4,{0,1,2,3,5,6,7})
Since we are only interested in which drinker is next added, we
treat these last two states as "absorbing", i.e. the probability
of staying in that state, once reached, is 1. The transition
probabilities for the other states (as the stein is located with
one of the six prior drinkers) are 1/3 for each pair of adjacent
locations.
The probability transition matrix has a block structure, using
the ordering of states given above, M =
A B
0 I
where I represents the 2x2 identity matrix for "transitions"
between the two absorbing states. As I worked out in my
earlier posts, the state converges over time to one or the
other of the absorbing states with distribution:
[1,0,0,0,0,0] (I - A)^-1 B
Since locations 3 and 7 are immediately adjacent, one would
certainly expect a big tilt in favor of the next drink occuring
at location 3 rather than 4. The actual calculation however:
[3/5,2/5]
gives perhaps less of a difference than might be expected.
In any case, that's the result.
I have worked out all the Markov chain results, chewing
up the better part of a yellow pad in the process, but I've
got room left to piece these together and (hopefully) get
the same answers that Mike got.
regards, chip