Probability question, Very hard

[SW VandeCarr]

Aradesh, sorry for my slow understanding, but how do you accommodate for all movement from person 1 to then person -1, and finally person n

For example:
0>1>2>1>2>3

In this example I agree with you. If player one receives the ball directly from from player 0, how can player one be last to receive the ball? In the circular example, one of two players will be eliminated with the first pass, but it could be either one with equal probability while the other could still be last.

 

[Jamma]

In this example I agree with you. If player one receives the ball directly from from player 0, how can player one be last to receive the ball? In the circular example, one of two players will be eliminated with the first pass, but it could be either one with equal probability while the other could still be last.

No, what Aradesh is saying is that we have effectively shown that player 3 (or -1) is the last with the ball as soon as player 2 receives it.

So 0>1>2>1>2>3 would come under the umbrella of 0>1>2 that he'd already listed. You see, as he was explaining, the game is effectively over when 0,1 and 2 have seen the ball, since with probability 1 the game will end eventually (it is not certain, 1 and 2 could pass to each other forever for example). So you just need to list the different ways that will lead to 1, 2 and 3 getting the ball before 4, all of which ways he has listed.

 

[SW VandeCarr]

No, what Aradesh is saying is that we have effectively shown that player 3 (or -1) is the last with the ball as soon as player 2 receives it.

OK. So it's still a circular arrangement. They way it was written, it looked like a linear arrangement.

 

[zgozvrm]

Here's some data for you:


I wrote a program in Visual Basic to simulate this game. It plays the game 1,000,000 times, keeping track of the number of times each player wins. It then tabulates the following data:
1) The percentage of wins for the the player who won most often after playing 500,000 games and after 1,000,000 games
2) The percentage of wins for the 2nd most winning player after 500,000 games and after 1,000,000 games
3) The percentage of wins for player #6 after 500,000 games and after 1,000,000 games
4) The percentage of wins for the player who won the least number of games (not player 1) after 500,000 games and after 1,000,000 games

On my computer, the program takes approximately 27 seconds to complete.


Here are my results (in each of the 4 categories, the data for the first 500,000 games is listed first, followed by the data for the entire 1,000,000 games played):

1st program run:
Most wins: Player 2 after 500,000 games (9.6034%), Player 2 after 1,000,000 games (9.6666%)
2nd most wins: Player 5 (9.3842%), Player 11 (9.5847%)
Player 6: 9.3038%, 8.7337%
Least wins: Player 10 (8.5560%), Player 10 (8.5995%)


2nd run:
Most wins: Player 12 (9.8740%), Player 12 (9.4708%)
2nd most wins: Player 11 (9.4456%), Player 5 (9.3190%)
Player 6: 9.3676%, 9.2796%
Least wins: Player 4 (8.5390%), Player 9 (8.6502%)


3rd run:
Most wins: Player 5 (9.5348%), Player 11 (9.5035%)
2nd most wins: Player 3 (9.3450%), Player 12 (9.3111%)
Player 6: 9.2758%, 9.0039%
Least wins: Player 8 (8.3498%), Player 8 (8.7958%)


4th run:
Most wins: Player 12 (9.9604%), Player 7 (9.5820%)
2nd most wins: Player 9 (9.4144%), Player 3 (9.5198%)
Player 6: 9.3296%, 8.9394%
Least wins: Player 10 (8.4282%), Player 5 (8.5131%)


In one run, after 100,000 games, player 5 was the least winning player, but after 1,000,000 games, he was the most winning player.

 

[SW VandeCarr]

Here's some data for you:I wrote a program in Visual Basic to simulate this game. It plays the game 1,000,000 times, keeping track of the number of times each player wins. It then tabulates the following data:

Thanks zgozvrm. I'd be interested in seeing the percentage of wins for each of all 12 players over all four runs.

 

[zgozvrm]

I'll run 4 more when I get some time (I'm at work!). Do you have Excel? If so, I can post it in spreadsheet form.

 

[SW VandeCarr]

I'll run 4 more when I get some time (I'm at work!). Do you have Excel? If so, I can post it in spreadsheet form.

OK. Thanks. BTW I meant 11 players after excluding the originator.

 

[zgozvrm]

Here's the complete data ...

(Note that the numbered columns represent how many wins each player has per successive 100,000 games played. That is, each column 1, 2, 3 ... 10 represents 100,000 games each, the "Total" column is the sum of the previous 10 columns; all 1,000,000 games)

 

[Jamma]

It's almost as if you guys still don't trust my proof =D haha

Aradesh's other problem is really cool. The reason I liked it, is that if you were asked to solve it before seeing this problem, it would have took a pretty amazing leap of insight to think of solving this one first. I don't think that I'd have managed to solve it, at least not in a day. But when you've solved the circular problem, you can show that the probability of it falling off the n end is i/(n+1) if the game starts at the i'th player. It's a pretty cool result!

 

[SW VandeCarr]

It's almost as if you guys still don't trust my proof =D haha

Yes. I couldn't let go of this problem. Actually once I considered that it had the Markov property:

P(q_i|q_{i-1},..,q_1)=P(q_i|q_{i-1}) for i>1

it should have been clear to me that the whole problem could have been broken down to just two players plus the originator. You were correct all along; but, of course, you are a mathematician.

 

[SW VandeCarr]

Here's the complete data ...

(Note that the numbered columns represent how many wins each player has per successive 100,000 games played. That is, each column 1, 2, 3 ... 10 represents 100,000 games each, the "Total" column is the sum of the previous 10 columns; all 1,000,000 games)

Thanks zgozvrm. I don't doubt the proof, but I'm curious about the actual data variations

 

[zgozvrm]

Thanks zgozvrm. I don't doubt the proof...

I didn't give a proof; I merely presented some data.

...I'm curious about the actual data variations

What are you curious about?

 

[SW VandeCarr]

I didn't give a proof; I merely presented some data.

I was referring to Jamma's previous post about a proof which I took to be in reference to your simulation. Sorry if that wasn't clear.

What are you curious about?

I was interested in the aggregate percentage of wins for the 11 positions across all four runs or as large a sample as you may have in order to to look at convergence. All I have with me is my laptop. Since you posted your simulation results, I didn't think you'd mind sharing this.

 

[zgozvrm]

Not sure what you mean by "aggregate percentage of wins..." exactly.

 

[SW VandeCarr]

Not sure what you mean by "aggregate percentage of wins..." exactly.

Nevermind. Thanks for posting the PDF and some of your results.

 

[Jamma]

Hmm, this seems wrapped up. I wonder if there are more difficult versions, with players placed in a lattice around a sphere for example, or on a square table and the one who drops it off loses =D

Actually, let's not go there...