28 views

Skip to first unread message

Jun 7, 2002, 1:48:44 AM6/7/02

to

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]

Jun 7, 2002, 5:31:56 AM6/7/02

to

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?

> 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! =-----

Jun 7, 2002, 7:10:30 AM6/7/02

to

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?

> 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. |

+====================================================================+

Jun 7, 2002, 7:16:09 AM6/7/02

to

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:

> > 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.

>

For n = 2 or n = 1, the first player always wins.> 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.

Jun 7, 2002, 10:48:53 AM6/7/02

to

I don't know of a formula, but i modeled the game and it was interesting.

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.

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...

Jun 7, 2002, 11:17:10 AM6/7/02

to

After a little more thought....

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

Jun 7, 2002, 1:03:47 PM6/7/02

to

William Elliot <ma...@xx.com> wrote in message news:<20020607023124...@agora.rdrop.com>...

> 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

>

> 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

Jun 7, 2002, 4:18:31 PM6/7/02

to

I've a recursive formula for W(k,n), where n is the total number of

players and k is the player position.

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??

Jun 7, 2002, 6:30:58 PM6/7/02

to

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.

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.

Jun 8, 2002, 12:15:20 AM6/8/02

to

pr...@yahoo.com (pradeep) wrote in message news:<8198af42.02060...@posting.google.com>...

> 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??

>

> 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

Jun 8, 2002, 12:30:24 AM6/8/02

to

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?> 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 =-----

Jun 8, 2002, 2:22:50 AM6/8/02

to

On Fri, 7 Jun 2002 22:30:58 +0000 (UTC), se...@btinternet.com (Henry) tried to

confuse everyone with this message:

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.

Jun 8, 2002, 8:54:03 AM6/8/02

to

William Elliot <ma...@xx.com> wrote in message news:<20020607212740...@agora.rdrop.com>...

> 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?

>

> 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)

Jun 13, 2002, 10:10:04 AM6/13/02

to

"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

(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

Jun 13, 2002, 10:46:06 PM6/13/02

to

"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

Jun 14, 2020, 9:42:17 PM6/14/20

to

在 2002年6月14日星期五 UTC+8上午10:46:06，Chip Eastham写道：

Did you succeed in "scaling" the result? Another point I find interesting is which player has the peak winning probability as N goes to infinity. It seems for large N's, players at the tail (N,N-1,N-2, etc.) can never have the highest winning probability. Check it here https://mathoverflow.net/questions/363032/what-is-the-asymptotic-dynamics-of-the-winning-position-in-this-game

Any ideas?

Any ideas?

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu