Probability question, Very hard

[shezleng]

12 persons sit around a round table for a game.
1st person gives the ball in his hands to the person in either his left or right randomly.
in the same token the person who holds the ball gives it the person in either his left or right randomly.
game continues so until the last person holds the ball.

Waht is the probability of being the 6th person as the last person in this game?

 

[mathman]

Who is the "last person"?

 

[shezleng]

last person is the person who holds the ball last

 

[SW VandeCarr]

last person is the person who holds the ball last

The probability is 1 if there is no time/pass limit.

 

[shezleng]

I mean that 6th person will be the last person who holds the ball first time

 

[SW VandeCarr]

I mean that 6th person will be the last person who holds the ball first time

Without a limit on the number of passes, the probability that the sixth player holds the ball asymptotically approaches 1. If the game ends when the sixth person actually holds the ball, then p=1 of course.

 

[SW VandeCarr]

I'm assuming the sixth player is the one directly across from the first player to hold the ball, There are five players on each side of the table between the two. Is this correct?

Or else you mean the twelfth (or last) person to hold the ball for the first time. If that's what you mean, then the probability of being the twelfth person to hold the ball approaches 1 as the game proceeds although the most likely player to be last at the start of the game would still be one in the sixth position furthermost from the first player to hold the ball.

I believe this prior probability would be 1-(1-0.5)^5=0.9688. That is, a high prior probability of being the last player to hold the ball for the first time. However, this must be continuously recalculated after each exchange.

 

[shezleng]

To be more understandable, have a loo at the below question similar to that I asked;

We start with a roulette wheel that is numbered from 0 to 32 in order, clockwise around the wheel. The ball starts in the 0 slot. The ball has paint on it that won't dry, so it leaves a mark whenever it visits a slot on the wheel. We flip a fair coin to determine the ball's movements. If it comes up heads, the ball moves one spot clockwise. If we flip tails, it moves one spot counter-clockwise. We will continue flipping, until every slot gets marked with some paint.

Determine which numbers, if any, are more likely than the others to be the last slot to get marked with paint (the 0 is out of the running as the wet ball starts there)

 

[SW VandeCarr]

My answer would be essentially the same, In time, every slot gets inked. On average, the slots furthest away from 0 would be the last to be inked, but for any given run any slot can be last except 0.

 

[shezleng]

Actually you mean or I understand from your reply is that every slot/or person has an equal chance to be last. So for the first problem probability for each will be 1/11 and for the second 1/32.
Am I correct?

 

[SW VandeCarr]

Actually you mean or I understand from your reply is that every slot/or person has an equal chance to be last. So for the first problem probability for each will be 1/11 and for the second 1/32.
Am I correct?

No. Did you read my post 7 and 9? I said earlier that each player will hold the ball or each slot will get inked with probability 1 if no prior limit is placed on how long the game runs. I said clearly that the seat or slot furthest from the originator would have the highest probability of being last in post 7 and 9.

Using the wheel as an example and 16 as the furthest slot from 0 we can imagine that the ball (probabilistically) oscillates around zero and visits slots further and further away over time according to a binomial distribution. The standard deviation is \sqrt{np(1-p)}= \sqrt{(16)(0.5)}= 2.828. Since the furthest slot is 16 slots from 0 and is 16/2.828=5.658 SD from the mean, the largest SD of any slot, it is the most likely to be the last slot visited on average.

However I'm not sure this is the correct model for anything but a prior probability. The game seems to be Markovian in that each new position changes the probabilities and the situation must constantly be re-evaluated.

 

[SW VandeCarr]

@shezleng

Since you are apparently only reading your email and not reading my actual posts on line I'm making a separate post. What you were referring to in your previous post was edited out and taken out of context. Please read my posts online and quote them or part of them when responding.

 

[Jamma]

I understood your question immediately- what is the probability that the last person to hold the ball is opposite the person who started?

The only way he would have been the last one is if the ball had got to his left, and then returned to him the other way round, or vice versa.

It will eventually get to his left or right, so you can assume wlog that we start to the left to work this out.

You will get an infinite expression to find the probability of going all the way round from the player to his left back to him from the right. Each one is equally likely, so this is the answer.

I think this is right, it's a cool question, I'll try and work it out when I have more time!

 

[Jamma]

One thing to note here that is cool is that it doesn't seem to matter which player you pick, I think that the probability is the same. So it seems that the chances are 1/11, although I'm sure that I've probably made a mistake!

 

[SW VandeCarr]

One thing to note here that is cool is that it doesn't seem to matter which player you pick, I think that the probability is the same. So it seems that the chances are 1/11, although I'm sure that I've probably made a mistake!

If the question is the probability of being is the last player to hold the ball for the first time, how could the probability be the same for all players? One of the players on either side of the first player (or originator) will get the ball with first the pass. So one these two players will eliminated on the first pass with p=0.5. For the player on the other side, the probability is now 1/4, and much lower for players farther away from the new ball position. It's clear that players close to the originator must be eliminated before the the most distant players can be eliminated from the possibility of being the last person to hold the ball for the first time. (Eliminated in the sense of not being able to be the last player to hold the ball, but remaining in the game to pass the ball,)

This is a Markov process where there is no "memory" of the prior positions of the ball. The game essentially begins again with each pass, and the probabilities are recalculated from each new origin adjusted for eliminated players. At least that's how see it, but I'd like to hear other views.

 

[Jamma]

Hmm the way I was thinking of it was this:

Let a player be examined for his probability of being the last to hold the ball. He will hold the ball eventually, otherwise the game wouldn't have ended. The ball must approach him from one side of the other. Suppose we choose the first time that this happens. Then the player to his other side hasn't received the ball yet. Therefore, for him to receive the ball last, the ball must go all the way back around the circle without passing him.

I don't know (and can't be bothered) to work out what this infinite sum, or multiple is; it's value or it's expression. However, I know that it is the same for whatever way round the ball has to go. It is also the same value for each player. The first player cannot be the last with the ball, since he starts with it. Every other player, however, can be the last, and we can use the above logic to see that they all have equal probability of being the last with the ball. Therefore the probability is 1/11.

I must admit that this still seems weird to me, and I'm not convinced that I haven't made some (very!) stupid mistake. It might be nice to find what this long expression is, and it might be a nice probability proof of a limit which might at first appear to be an analysis problem. Anyway, need to be sure of that thhe above argument works first, will think about it when I get more time.

 

[Jamma]

Oh, and if this is right, then the seemingly strange fact that the players close to the originator seem very easy to eliminate may be offset by the fact that the ball doesn't have to make it's way to them a long way first and then decide to turn back to make them the last ones.

 

[SW VandeCarr]

Hmm the way I was thinking of it was this:

Let a player be examined for his probability of being the last to hold the ball. He will hold the ball eventually, otherwise the game wouldn't have ended.

Do you agree that when the game begins one of the players to the immediate right or left of the originator will receive the ball and therefore be eliminated from being the last player to hold the ball with probability one? (probability 0.5 for each player). If so, then the probability for all players to be last cannot be uniform. Only one player can be last if the entire game is considered as a unity.

There's no simple general solution for this problem. I'm saying it's a Markov process which must be updated after each passing of the ball. It has the memoryless property that I referred to in a previous post. I'd be satisfied if someone would post and just confirm or refute this view with an explanation.

Earlier I said that the game effectively begins again with each pass. If you want to be tricky you could say that every player will be in the position of being to the immediate right or left of the person holding the ball before the game ends, but that's facetious. Only one player will be eliminated last which implies to me that the game must be considered as whole. The players next to the originator when the game begins will almost never the last to hold the ball.

This thread was moved to the pre-calculus forum for reasons I don't understand, It's clearly stochastic process question and it's not your typical homework question.

 

[zgozvrm]

It seems that most people are confused as to what the actual question is. Let's suppose there are only 5 people (a, b, c, d, & e) sitting around a table.

The ball starts in the hands of a.
a has the ball and can pass it to either b or e.
Let's suppose he passes it to e.
e can either pass it to d or back to a.
Let's suppose e passes to d
(now 3 of the 5 players have held the ball, so the game is not over)

We now know that the game will end with the ball in the hands of b or c
Let's suppose, that the sequence of passes continues as such:
d to e
e to d
d to e
e to a
a to b

This is player b's first possession of the ball; only player c has yet to hold it, so he will be the final player when that event occurs.



The OP's problem has 12 players: a, b, c, d, e, f, g, h, i, j, k, & l

Player a can never be the last to hold the ball, since he is starting the game. The remaining 11 players have yet to hold the ball. Once a passes to either b or l, there will be 10 players remaining who have yet to hold the ball, so that player cannot be the last to hold it.

The probability that player a is the last to hold the ball is 0.

The probability that player b is the last to hold the ball is 0, given that a passes the ball to him first. The probability that player b is the last to hold the ball, given that player a passes to player l first, instead, is greater than 0 but less than 1.

So, the question is: What is the probability that player f will be the last to hold the ball?

 

[Jamma]

Do you agree that when the game begins one of the players to the immediate right or left of the originator will receive the ball and therefore be eliminated from being the last player to hold the ball with probability one? (probability 0.5 for each player). If so, then the probability for all players to be last cannot be uniform. Only one player can be last if the entire game is considered as a unity.

There's no simple general solution for this problem. I'm saying it's a Markov process which must be updated after each passing of the ball. It has the memoryless property that I referred to in a previous post. I'd be satisfied if someone would post and just confirm or refute this view with an explanation.

Earlier I said that the game effectively begins again with each pass. If you want to be tricky you could say that every player will be in the position of being to the immediate right or left of the person holding the ball before the game ends, but that's facetious. Only one player will be eliminated last which implies to me that the game must be considered as whole. The players next to the originator when the game begins will almost never the last to hold the ball.

This thread was moved to the pre-calculus forum for reasons I don't understand, It's clearly stochastic process question and it's not your typical homework question.

I agree with you that a player to the left or right must be eliminated from the game in the first turn with probability 1, but I don't see how you conclude that the probabilities cannot be uniform.

As I've said a few times, I'm probably being an idiot, so instead of convincing me of why the probabilities can't all be the same, could you just point out where I went wrong in my explanation instead? That way may be a little more painless =D

 

[Jamma]

Let me rewrite my proposed solution in zgozvrm's notation for clarity (which I think is the issue here).

Start with the ball at person-a. Let P(b) be the probability that person-b
is the last person to touch the ball. Note that due to symmetry we have
that P(l) = P(b). So for person-b to be the last person to touch the ball, we require that the ball goes around the whole circle without ever crossing person-a in the direction of person-b.

Now let's compute the probability that person-x is the last person to hold
the ball, where x is any of the given letters, except a (P(a)=0, obviously).

With probability 1, the ball will get to one of person-(x-1) or
person-(x+1) before it reaches person-x (obviously by this abuse of notation, I mean the players to the left and right). From this point the probability that x is last requires exactly what was required in the x=b or x=l case, to go all the way around the circle, so P(x) = P(a) for all x except x=a.

The probability therefore of a player being the last to touch the ball, given that the game ends, is 1/11 for any player other than a and it is 0 for player a. Given that game ends with probability 1, the probabilities are the same.

 

[zgozvrm]

Let me rewrite my proposed solution in zgozvrm's notation for clarity (which I think is the issue here).

Start with the ball at person-a. Let P(b) be the probability that person-b
is the last person to touch the ball. Note that due to symmetry we have
that P(l) = P(b). So for person-b to be the last person to touch the ball, we require that the ball goes around the whole circle without ever crossing person-a in the direction of person-b.

Now let's compute the probability that person-x is the last person to hold
the ball, where x is any of the given letters, except a (P(a)=0, obviously).

With probability 1, the ball will get to one of person-(x-1) or
person-(x+1) before it reaches person-x (obviously by this abuse of notation, I mean the players to the left and right). From this point the probability that x is last requires exactly what was required in the x=b or x=l case, to go all the way around the circle, so P(x) = P(a) for all x except x=a.

The probability therefore of a player being the last to touch the ball, given that the game ends, is 1/11 for any player other than a and it is 0 for player a.

I disagree. Although I'm not sure how to calculate it, it seems obvious that the probability that the game ends with either player "b" or player "l" is lower than the probability that it ends with player "f".

A random situation like this will likely end in an even distribution "to the left" and "to the right," meaning that it would be most likely (high probability) that player "f," being half-way around the table is the last player to receive the ball.

 

[SW VandeCarr]

I agree with you that a player to the left or right must be eliminated from the game in the first turn with probability 1, but I don't see how you conclude that the probabilities cannot be uniform.

As I've said a few times, I'm probably being an idiot, so instead of convincing me of why the probabilities can't all be the same, could you just point out where I went wrong in my explanation instead? That way may be a little more painless =D

When game begins, the ball is most likely to be in the vicinity of originator for a while. It moves both ways to the right and left of the originator eliminating players. It's unlikely to move in one direction very far, and very unlikely to go "all the way around" in a sustained movement.

However systems like this will tend to find new centers of motion over time, but they are unpredictable. Do you know what a Markov process is? In any case, it's clear that the players close to the originator must be eliminated first before more distant players can be eliminated. Your scenario that the ball goes all the way around, say to the left of the originator, and reaches the player to the immediate right of originator last is possible, but not likely. It is true that these systems do tend to favor one side from coin tossing experiments but when the game begins, you don't know which side.

Short answer: Since players close the originator must be eliminated before more distant players can be eliminated, the probability of being last to hold the ball is higher with more distant players.

http://research.cs.tamu.edu/prism/lectures/pr/pr_l23.pdf

Note: In an earlier post I said "eliminated" means eliminated from the possibility of being last, but remaining in the game to pass the ball. However, either way, it doesn't change the conclusion regarding proximity to the originator.

 

[Jamma]

When game begins, the ball is most likely to be in the vicinity of originator for a while. It moves both ways to the right and left of the originator eliminating players. It's unlikely to move in one direction very far, and very unlikely to go "all the way around" in a sustained movement.

However systems like this will tend to find new centers of motion over time, but they are unpredictable. Do you know what a Markov process is? In any case, it's clear that the players close to the originator must be eliminated first before more distant players can be eliminated. Your scenario that the ball goes all the way around, say to the left of the originator, and reaches the player to the immediate right of originator last is possible, but not likely. It is true that these systems do tend to favor one side from coin tossing experiments.

Short answer: Since players close the originator must be eliminated before more distant players can be eliminated, the probability of being last to hold the ball is higher with more distant players.

http://research.cs.tamu.edu/prism/lectures/pr/pr_l23.pdf

You don't need Markov processes as far as I can tell; I've not read about them before though.

Look, my proof seems watertight. The outcome is a little bit surprising, but not too much when you think about it a bit harder. The nature of the ball movement isn't to swing around the vacinity of the originator at all; it's not that unlikely that it doesn't actually pass back over the originator, it's not like he has some sort of extra gravitational pull which is making the ball to decide to swing around the center a lot before managing to find it's way to the further players. It does seem like the probability should be higher for the further players at first, but then think that for it to be the player to the left or right of the originator, we just need the ball to go once around the circle without crossing the starting player, whereas a player further away needs to come all the way to him first before it deciding to return, so it all pans out.

I might try and find the expression for this probability, but I've not done anything computational for ages!

 

[Aradesh]

Jamma is obviously correct. With a circle of n people the probability of each individual of being last (apart from the starter) is 1/(n-1). In a uniform distribution each non-starting position has probability of 10/11 of being eliminated at some point - so how on Earth does the fact that people in positions 1 and -1 have probability of 1/2 of being eliminated in the first go suggest that the distribution isn't uniform?

What's fun is that this clever solution allows us to solve the superficially more difficult problem:

Let n people stand in a row, numbered 1,2,...,n, and start with person-k holding the ball. They pass the ball each turn left or right with probability 0.5. The game ends when the ball goes off one of the ends (i.e. when person-1 has to send it away from person-2, or when person-n has to send it away from person-(n-1)). What is the probability it goes off the n-end of the line?

Spoiler

Consider the cicrle of n+2 people with the ball starting at the k-th position on the circle. The problem above is equivalent to the ball reaching person-(-1) before it reaches person-0. Which people can be last to touch the ball (as in the previous game) to allow this to occur?

 

[Aradesh]

For any doubters, here is the case with 4 people.

Name them 0,1,2,3 and start with the ball at 0.

For player 3 to be last to see the ball, the ball needs to do any of the following:
0 -> 1 -> 2 (then eventually hitting 3 with probability 1) (probability 1/4)
0 -> 1 -> 0 -> 1 -> 2 (probability 1/4^2)
0 -> 1 -> 0 -> 1 -> 0 -> 1 -> 2 (probability 1/4^3)
...

We can only get extra possibilities for this scenario adding another 0->1 to the start. So the probability that 3 is the last to see the ball is

1/4 + 1/4^2 + 1/4^3 + ... = 1/3.

Similarily by symmetry for person-1 to be the last to see the ball its also 1/3. And since we only have 1/3 left over, it must also be 1/3 probability for person-2 to be last to touch the ball.

 

[SW VandeCarr]

@Jamma

Yes, I see it now. I had the solution early on (the OP saw it) and edited it out because I didn't appreciate how critical the first pass (from the originator to the left or right) was. I conceded that the process would initially move to favor one side of the circle (from the originator's perspective) but didn't follow through on that thought. Thanks for clarifying this for me.

 

[Lukybear]

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

 

[Aradesh]

Luckybear: I'm not sure what you mean. If you mean in the case where there are four people, once the ball has been to 0,1,2 at least once (without going to 3 before it) then whatever happens after, at some point eventually, with probability 1, it will reach 3. So we only need to look at the examples which end up with all 0,1,2 at some point seeing the ball.

If you mean for n>4, then you can compute it manually like this but it gets more and more complicated.

 

[Lukybear]

But say can't ball swing from 0>1 then to -1 in other direction? How is that accommodated?

 

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