Elimination...
Timofei Shatrov
n players sit around the table. Players are numbered 1, 2, 3, ..., n clockwise.
First player selects any other player at random and that player goes away. Then,
the next player clockwise does the same and so on. What is probability that k-th
player wins the game?
For example if n=4, then
k=1 - 1/2
k=2 - 0 - never wins
k=3 - 1/6
k=4 - 1/3
--
#__|___|_/########|___|__###############################################
#|___|#######O#O####|___|# Timofei Shatrov aka Grue (grue -> mail.ru) #
#__|__|###########|___|__# http://grue3.tripod.com #
#|___|_|#########|__|__Gr#########################################[4*72]
William Elliot
> n players sit around the table. Players are numbered 1, 2, 3, ..., n clockwise.
> First player selects any other player at random and that player goes away. Then,
> the next player clockwise does the same and so on. What is probability that k-th
> player wins the game?
1/n
-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 80,000 Newsgroups - 16 Different Servers! =-----
Bob Harris
> n players sit around the table. Players are numbered 1, 2, 3, ..., n
> clockwise. First player selects any other player at random and that player
> goes away. Then, the next player clockwise does the same and so on. What is
> probability that k-th player wins the game?
and William Elliot replied:
> 1/n
I don't think that's right. If there are only three players, whoever goes
first will never win. For whichever player she chooses to eliminate, the
reminaing one will then eliminate her.
Bob H
--
-- Bob Harris =======================================================+
| This e-mail sponsored by... Feeling tired? Run down? You may |
| be overdue for a phlebotomy. Call the offices of Dr. Acula, |
| 826-7473. Specialists in venesection since 1431. |
+====================================================================+
William Elliot
> Timofei Shatrov wrote:
> > n players sit around the table. Players are numbered 1, 2, 3, ..., n
> > clockwise. First player selects any other player at random and that player
> > goes away. Then, the next player clockwise does the same and so on. What is
> > probability that k-th player wins the game?
>
> and William Elliot replied:
> > 1/n
>
> I don't think that's right. If there are only three players, whoever goes
> first will never win. For whichever player she chooses to eliminate, the
> reminaing one will then eliminate her.
>
So 1/n is only correct in the limit.
Frank At GTMA
Even with ten players certain players had large advantages. the first seat
won 4.5 times as many times as the 4th seat. I thought as n went up we
would see an "evening out of winning probability, much sooner. Anyways a
probability tree works for simple cases, but if n is large this method is
awkward.
One way to simplify the tree is after eliminating one player, the game is
now analagous to the n-1 game.
For example: for n = 5, after player one goes one player is elimated and the
rest of the game is the same as the fouur player game with player one of the
five player game being analgous to player four of the four player game. So
(since he is choosing firdt) he has 100% chance to make it to the second
round, where he now has a 33%(fourth player of a four player game). So
overall winning percentage is 100% * 33% = 33%.
Or for player 2 of n=5 game. He has a 75% chance to make it to the second
turn, after which he is analogous to player 1 of n=4 game., where he has a
50% chance. So his overall chance is 75% * 50% = 37.5% to win the n=5 game.
For player 3 of n=5. He has a 75% chance making it to the second round. In
the second round (if playing) he has a 33% chance to be k=1 for n=4 game,
and 67% to be k=2 for a n=4 game. Or 75% * 33% * 50% = 12.5% chance.
For player 4 of n=5. 3/4* 1/3 (chance they are player 3 in n=4 game) * 1/6
= 1/24
For player 5 of n=5. 3/4* 1/6 = 1/8.
And then use gme n=5 to solve n= 6.
In any event, it seems complicated and I cannot see a formula, maybe someone
wiser than I can.
"Timofei Shatrov" <gr...@mail.ru> wrote in message
news:3d0045e...@News.CIS.DFN.DE...
Frank At GTMA
with
j
P
n
meaning the winning probability of the jth player in a n person game
the following recursive formula should work.
for j = 1
1 n-1
P = P
n n-1
for j > 1
j j-2 j-2 6-j j-1
P = ---- P + ---- P
n n-1 n-1 n-1 n-1
And
1
P = 100%
2
2
P = 0%
2
Chip Eastham
> On Fri, 7 Jun 2002, Timofei Shatrov wrote:
> > n players sit around the table. Players are numbered 1, 2, 3, ..., n clockwise.
> > First player selects any other player at random and that player goes away. Then,
> > the next player clockwise does the same and so on. What is probability that k-th
> > player wins the game?
>
> 1/n
>
William,
It is pretty easy to show the chances of winning are not equal. If
they were,
then after the first player goes, all the remaining players (including
the first player) would then have a 1/(n-1) chance of winning. But
the first player is guaranteed to make it into the second round
("First player selects any other player at random and that player goes
away.") so this says the first player would have at least a 1/(n-1) >
1/n chance of winning.
regards, chip
pradeep
players and k is the player position.
W(k,n) = ( (k-2)* W(k-2,n-1) + (n-k)* W(k-1,n-1) )/(n-1)
This will not work for k=1.So
W(1,n) = W(n-1,n-1)
You can prove that this is correct. The position of player k in
an n-player game will either move to k-1 or k-2 once the first
player is eliminated(in the (n-1)-player game). The respective
chances are (k-2)/(n-1) and (n-k)/(n-1).
Make sense??
Henry
>On Fri, 7 Jun 2002, Bob Harris wrote:
>> Timofei Shatrov wrote:
>> > n players sit around the table. Players are numbered 1, 2, 3, ..., n
>> > clockwise. First player selects any other player at random and that player
>> > goes away. Then, the next player clockwise does the same and so on. What is
>> > probability that k-th player wins the game?
>>
>> and William Elliot replied:
>For n = 2 or n = 1, the first player always wins.
>So 1/n is only correct in the limit.
If that is true, it happens very slowly according to my unchecked
calculations:
For example for n=200, the best position (181) has a chance of winning
of 0.00724... and the worst position (79) has a chance of 0.00264...
The ratio of best chance over worst chance tends to decline very
slowly: at n=50 it is 2.935..., at n=100 2.815..., at n=150 2.764...,
at n=200 2.744... It is not ovious to me that this reaches a limit of
1.
It looks as if it is best to go first if n is
1,2,4,10,11,28,29,30,78,79,80,81,215,216,217,218,219,220,221,...
All very odd.
Chip Eastham
> I've a recursive formula for W(k,n), where n is the total number of
> players and k is the player position.
>
> W(k,n) = ( (k-2)* W(k-2,n-1) + (n-k)* W(k-1,n-1) )/(n-1)
>
> This will not work for k=1.So
>
> W(1,n) = W(n-1,n-1)
>
> You can prove that this is correct. The position of player k in
> an n-player game will either move to k-1 or k-2 once the first
> player is eliminated(in the (n-1)-player game). The respective
> chances are (k-2)/(n-1) and (n-k)/(n-1).
>
> Make sense??
>
Yes, pradeep, I agree. The first position player in the n player
game always becomes the last position player in the subsequent n-1
player game, since the first player cannot be eliminated in the
first step. Hence W(1,n) = W(n-1,n-1).
Any other player, say in position k, has three possible fates:
- a 1/(n-1) chance of being eliminated in the first step
- a (k-2)/(n-1) chance of becoming the k-2 position player in the
n-1 player game (if someone ahead is eliminated in the first step)
- a (n-k)/(n-1) chance of becoming the k-1 position player in the
n-1 player game (if someone following is eliminated at step one)
W(k,n) = ( 0 + (k-2)W(k-2,n-1) + (n-k)W(k-1,n-1))/(n-1) for k > 1
which simply restates/proves your recursion formula.
If I were going to try and spot a pattern, I think I'd scan over
the results for W(k,n)*n! and look for terms that can be expressed
in combinations form.
regards, chip
William Elliot
> I've a recursive formula for W(k,n), where n is the total number of
> players and k is the player position.
>
> W(k,n) = ( (k-2)* W(k-2,n-1) + (n-k)* W(k-1,n-1) )/(n-1)
>
> This will not work for k=1.So
>
> W(1,n) = W(n-1,n-1)
>
> You can prove that this is correct. The position of player k in
> an n-player game will either move to k-1 or k-2 once the first
> player is eliminated(in the (n-1)-player game). The respective
> chances are (k-2)/(n-1) and (n-k)/(n-1).
>
> Make sense??
>
> > "Timofei Shatrov" <gr...@mail.ru> wrote in message
> > n players sit around the table. Players are numbered 1, 2, 3, ..., n
> > clockwise.
> > First player selects any other player at random and that player goes away.
> > Then,
> > the next player clockwise does the same and so on. What is probability
> > that k-th player wins the game?
-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
Timofei Shatrov
confuse everyone with this message:
>On Fri, 7 Jun 2002 04:16:09 -0700, William Elliot <ma...@xx.com> wrote:
>
>>On Fri, 7 Jun 2002, Bob Harris wrote:
>>> Timofei Shatrov wrote:
>>> > n players sit around the table. Players are numbered 1, 2, 3, ..., n
>>> > clockwise. First player selects any other player at random and that player
>>> > goes away. Then, the next player clockwise does the same and so on. What is
>>> > probability that k-th player wins the game?
>>>
>>> and William Elliot replied:
>>For n = 2 or n = 1, the first player always wins.
>>So 1/n is only correct in the limit.
>
>If that is true, it happens very slowly according to my unchecked
>calculations:
>For example for n=200, the best position (181) has a chance of winning
>of 0.00724... and the worst position (79) has a chance of 0.00264...
>
>The ratio of best chance over worst chance tends to decline very
>slowly: at n=50 it is 2.935..., at n=100 2.815..., at n=150 2.764...,
>at n=200 2.744... It is not ovious to me that this reaches a limit of
>1.
I guess it would be e.
Chip Eastham
> On 7 Jun 2002, pradeep wrote:
> > I've a recursive formula for W(k,n), where n is the total number of
> > players and k is the player position.
> >
> > W(k,n) = ( (k-2)* W(k-2,n-1) + (n-k)* W(k-1,n-1) )/(n-1)
> >
> > This will not work for k=1.So
> >
> > W(1,n) = W(n-1,n-1)
> >
> > You can prove that this is correct. The position of player k in
> > an n-player game will either move to k-1 or k-2 once the first
> > player is eliminated(in the (n-1)-player game). The respective
> > chances are (k-2)/(n-1) and (n-k)/(n-1).
> >
> > Make sense??
> >
> No, what's W?
>
W(k,n) is the probability of the k'th player winning an n-player game.
In addition to the formulas above we need the initial condition:
W(1,1) = 1
For example, from W(1,n) = W(n-1,n-1) with n = 2 we get W(1,2) = 1.
From the more complicated formula with k = 2, n = 2:
W(2,2) = 0*W(0,1) + 0*W(1,1) = 0
It might be objected that W(0,1) is undefined, but it only appears (as
here) multiplied by its first argument (zero), so its definition is
moot. However it could also be handled by making a separate formula
for k = 2:
W(1,n) = W(n-1,n-1)
W(2,n) = (n-2)W(1,n-1)/(n-1)
W(k,n) = [(k-2)W(k-2,n-1) + (n-k)W(k-1,n-1)]/(n-1) for k > 2
-- chip
(replace bellsouth by icx to reply)
Mark Lewis
> W(k,n) = [(k-2)W(k-2,n-1) + (n-k)W(k-1,n-1)]/(n-1) for k > 2
If you plot this it looks sinusoidal, something like:
W(k,n) = [1 + .46 sin(2 pi (k/n - log(n) + 0.65))]/ n
If the ratio of the max to the min is e then the amplitude constant is
(e-1)/(e+1)= 0.4621…
The phase constant goes as log(n) which I guess follows from it
changing 1/n for each n.
Maybe you can convert the recursive formula into a differential
equation and solve it?
--
Mark W. Lewis, North Somerset, UK
Chip Eastham
"Mark Lewis" <peri...@dial.pipex.com> wrote in message
news:0J1O8.1633$nu5.13...@news-text.cableinet.net...
> "Chip Eastham" <eas...@bellsouth.net> wrote:
>
> > W(k,n) = [(k-2)W(k-2,n-1) + (n-k)W(k-1,n-1)]/(n-1) for k > 2
>
> If you plot this it looks sinusoidal, something like:
>
> W(k,n) = [1 + .46 sin(2 pi (k/n - log(n) + 0.65))]/ n
>
> If the ratio of the max to the min is e then the amplitude constant is
>
> The phase constant goes as log(n) which I guess follows from it
> changing 1/n for each n.
>
> Maybe you can convert the recursive formula into a differential
> equation and solve it?
>
Hi, Mark:
Maybe. I was trying to think of a way to not only "scale" the
results to a constant interval, but also somehow "unrotate" the
solution so that the peak winning probability is localized. As it
is, with W(1,n) = W(n-1,n-1), the solutions appear to "wrap
back around" and rotate forward as n increases.
regards, chip
3532...@qq.com
Any ideas?