Probability question, Very hard

  • Thread starter Thread starter shezleng
  • Start date Start date
  • Tags Tags
    Hard Probability
Click For Summary
SUMMARY

The probability of the sixth person being the last to hold the ball in a game with twelve players is 1 if there is no time limit on the game. As the game progresses indefinitely, the probability that the sixth player holds the ball approaches 1. The discussion also highlights that the game operates as a Markov process, where each pass recalculates the probabilities based on the current state of the game. The players closest to the originator are more likely to be eliminated early, affecting the overall probabilities of who can be the last to hold the ball.

PREREQUISITES
  • Understanding of Markov processes and their memoryless property
  • Basic knowledge of probability theory, specifically binomial distribution
  • Familiarity with stochastic processes and their applications
  • Concept of asymptotic probability in infinite sequences
NEXT STEPS
  • Study Markov chains and their applications in probability theory
  • Learn about binomial distributions and their properties
  • Explore stochastic processes in depth, focusing on memoryless properties
  • Investigate asymptotic analysis in probability and statistics
USEFUL FOR

Mathematicians, statisticians, game theorists, and anyone interested in probability theory and stochastic processes.

  • #31
Lukybear said:
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.
 
Last edited:
Physics news on Phys.org
  • #32
SW VandeCarr said:
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.
 
  • #33
Jamma said:
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.
 
  • #34
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.
 
  • #35
zgozvrm said:
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.
 
  • #36
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.
 
  • #37
zgozvrm said:
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.
 
  • #38
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)
 

Attachments

Last edited:
  • #39
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!
 
  • #40
Jamma said:
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.
 
Last edited:
  • #41
zgozvrm said:
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
 
  • #42
SW VandeCarr said:
Thanks zgozvrm. I don't doubt the proof...
I didn't give a proof; I merely presented some data.

SW VandeCarr said:
...I'm curious about the actual data variations
What are you curious about?
 
  • #43
zgozvrm said:
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.
 
  • #44
Not sure what you mean by "aggregate percentage of wins..." exactly.
 
  • #45
zgozvrm said:
Not sure what you mean by "aggregate percentage of wins..." exactly.

Nevermind. Thanks for posting the PDF and some of your results.
 
  • #46
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...
 

Similar threads

Inclusion-Exclusion Principle and Circular Arrangement
  • · Replies 3 ·
Replies
3
Views
2K
Solving a combinatorial problem
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Please Explain (actually explain) The Monty Hall Problem
  • · Replies 53 ·
2
Replies
53
Views
3K
High School Death Rally: an intricate probability problem?
  • · Replies 8 ·
Replies
8
Views
3K
Probability Statistics Question
  • · Replies 19 ·
Replies
19
Views
6K
Graduate A game of seemingly mutually independent events
  • · Replies 7 ·
Replies
7
Views
2K
What Are the Probabilities of Different Seating Arrangements at a Party?
  • · Replies 2 ·
Replies
2
Views
2K
Expected value and probability
  • · Replies 7 ·
Replies
7
Views
3K
Conditional probability & r balls randomly distributed in n cells
  • · Replies 2 ·
Replies
2
Views
6K
Probability Problem: Success Event in 2 Tasks
  • · Replies 8 ·
Replies
8
Views
3K