Probability question, Very hard

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

Homework Help Overview

The discussion revolves around a probability problem involving a game where 12 persons pass a ball around a circular table. The focus is on determining the probability that a specific player, the 6th person, is the last to hold the ball after a series of random passes.

Discussion Character

  • Exploratory, Assumption checking, Conceptual clarification

Approaches and Questions Raised

  • Participants explore the definition of the "last person" holding the ball and question the implications of time limits on the game's outcome. There are discussions about the probabilities associated with different players based on their positions relative to the first player.

Discussion Status

Multiple interpretations of the problem are being explored, particularly regarding the conditions under which the 6th player could be the last to hold the ball. Some participants suggest that the probability approaches 1 under certain conditions, while others argue that the probabilities must be recalculated after each pass. There is no explicit consensus on the final probability values.

Contextual Notes

Participants note that the game is a Markov process, where the probabilities change with each pass, and they discuss the implications of the game's structure on the likelihood of each player being the last to hold the ball. There is also mention of assumptions regarding the infinite nature of the game and the equal chances of players based on their positions.

  • #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
4K
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