Showing posts with label balls. Show all posts
Showing posts with label balls. Show all posts
One At A Time
Alright, time to finish off the solution to the balls in jars problem from before.
The essential proof is that it is possible to find an algorithm that will move from a position (a,b,c), with a>b>c, to a position (x,y,z) such that z is less than c. Thus by repeating this algorithm no more than c times, you must reach zero (given that we can only have integer values).
OK, suppose we start in some position. Call the bucket with the most marbles A, the one with the fewest marbles C, and the other one B. The names of those jars will not change throughout the algorithm, specifically even though C has the fewest at the start it might not at some later point. Let a, b, and c be the number of marbles in jars A, B, and C respectively. Note that even though A, B, and C will not change throughout the algorithm, the values of a, b, and c will.
The algorithm is: Check the value of floor(b/c). If it is even, move marbles from A to C. If it is odd, move marbles from B to C. If C has more marbles than B then stop, otherwise go back to the start.
Simple enough, now, to prove it works. We must prove that at the end B will have fewer marbles in it than C started with.
At the start, we know that b is greater than c, let us write b=qc+t with t less than c, so q being the floor of b/c. For this proof, we will not change the values of a, b, and c, I will assume those values are locked at the start.
Let us suppose b is not at least twice as big as c, so then q=1 and when we move marbles from B to C (as per the algorithm), B will have t marbles in it, and t is less than c.
Now, if q is bigger than 1, I will show that the algorithm will reduce the number of marbles in jar B without changing the value of t, so eventually q will be 1.
So, if we suppose q is even, so we move marbles from A to C. Now C contains 2c, and B contains b. Since b=qc+t=(q/2)(2c)+t, so b mod c and b mod 2c both give t (note that q being even was needed).
If q is odd, we will move marbles from B to C. Now C contains 2c and B contains b-c. Since b=qc+t we can also then show b-c=((q-1)/2)(2c)+t, so b mod c and b-c mod 2c both give t (in this case q being odd is needed).
Each time, B contains fewer marbles, so eventually q will be 1 and then next move B will have t marbles, which was less than the starting value of C. So, this finishes the proof. One simply needs to repeat the algorithm many times (renaming the jars A, B, and C after each iteration) to win the game.
Two In One
Alright, time for the partial solution to the balls in jars problem from last time.
I guess since the two-jar problem is a decent amount easier, I'll solve that out first.
First of all, it is absolutley trivial to see that if the total number of balls in the jars is not an even number, there will be no way to win, since to win you must first arrive at a position of the form (p,p). Next, it is easy to see that any common divisor has no effect on the ability to win from a position, that is to say: the position (p,q) is winnable iff the position (np,nq) is winnable.
At this point, we might be inclined to work out a few winning positions. OK, so what are the winning positions of the form (1,q)? Well, clearly (1,1) is a winning position, and (1,q) can only be a winning position if q is odd. From the position (1,q) we move to the position (2,q-1), but since q is odd for any position of interest this is the same as (1,[q-1]/2) so if we suppose this is another position, say (1,k), we see that q=2k+1 so if (1,k) is a winning position then so is (1,2k+1). From here we can list off the positions as (1,3), (1,7), (1,15)... clearly (1,q) seems to be a winning position if q is 1 less than a power of two. You can prove that by induction if you like, and with a bit more work we can also be sure that there aren't other winning positions of the form (1,q), but I won't bother with that yet.
Next, what about positions of the form (3,q)? Well, first of all q=1 would be a winning position. Next, from (3,q) we can move to (6,q-3) (this assumes that q>3, but other positions are finite enough anyway). Now since we might as well assume q is odd, we can half this position to (3,[q-3]/2) so calling this (3,k) again, we see that if (3,k) is a winning position then so is (3,2k+3). Listing off positions we can see that the winning positions seem to be (3,1), (3,5), (3,11), (3,29)... again summing to a power of two. This makes it seem that a position (p,q) is a winning position iff the sum p+q is a power of two. Well, thats easy enough to disprove, (3,9) is a winning position, but it is merely a multiple of 3 away from (1,3).
The main thing that will finish this off is the realiziation that once you have divided off any multiples in your problem, no new ones will show up, besides 2, and that one will show up every move. Lets prove that. Suppose we are in some position (p,q) with p and q both odd (so that their sum is even, but we do not need to divide off an overall 2), and we assume that p and q are not both multiples of some prime number n (n>2). Now we move to (p-q, 2q) (setting p as the larger one), I claim that p-q and 2q are also not both multiples of n. If they were then q would be a multiple of n (since 2q is) and then p would be (since p-q is and q is). Naturally this argument won't work for n=2, an overall multiple of 2 shows up every single move.
Now I will prove the main result: from position (p,q) with p and q having no common factors, we are in a winning position iff p+q is a power of 2.
You can prove one direction by induction. Prove it for p+q=2^n. It is trivial for n=1, then if it is true for n=k and you are in position (p,q) with p+q=2^(k+1) you can make one move and then half p and q so that p+q will now equal 2^k.
For the other direction we must show that if p+q is a multiple of a prime other than 2 and p and q have no common factors, then it is a losing position. Suppose p+q is z*k where z is a prime other than 2. k must be even, for if p+q is odd then we are trivially in a losing position. In order to win, we must first reach (z*k/2, z*k/2) but we have already proven that once you have divided off multiples, no new ones can show up. A new multiple of z (for z>2) cannot happen, so the position (z*k/2, z*k/2) cannot be reached, so the game cannot be won.
This finishes the proof. While working on the problem I also noticed that the legal move from (p,q) is to (2p,2q) mod p+q, which I thought was sort of cool. Perhaps people who are better at number theory than I can make use of that. Anyway, feel free to try to use this to solve the three jar problem, I was never able to.
Balls In Jars
New puzzle time I suppose. I am going to put up a puzzle that I have been working on for about 2 years which I got from the Math Club room on KGS. Its possible that I spent alot of time overthinking the puzzle, but there was a very interesting diversion that I thought was a neat side puzzle that I will also post here. First, the main puzzle:
You have three jars that contain marbles. You are going to play a one-player game with these jars. On a turn, the legal move is to select two jars and move from the first jar to the second jar as many marbles as were in the second jar (naturally the "first jar" must be the one with more marbles). The goal is to set things up so that you can get one jar to be empty. Show that it is always possible, no matter how many marbles were in each of the three jars initially, to achieve the goal of getting an empty jar.So, for example, you could start with (1,8,3) then move 1 marble from the second to the first, getting (2,7,3). Then move 2 marbles from the second to the first, getting (4,5,3). Next move 3 marbles from the second to the third, getting (4,2,6). Now move 4 marbles from the last to the first, getting (8,2,2). Finally move 2 marbles from the second to the last, getting (8,0,4) winning the game. I could have won that game more efficiently, but I wanted to just play around a bit to demonstrate the moves. When I tried to solve the puzzle, I first tried to explore out the two-jar case, figuring that would help (it did not, by the way). In the end I saw a neat little result that I will also pose as a problem:
In the two jar version of the same problem, what is the complete list of initial situations (a,b) from which you can reach a winning position (q,0).It is clear not all initial positions of the two-jar game can be solved, for example if you start with (8,2) you can only move to (6,4) and then to (2,8) and then to (4,6) and back to (8,2). However, (3,1) can be won, moving to (2,2) then to (4,0). You can see that there are no choices when playing this game, but from what initial setups can you win?
Pigeonhole'd
Solution o'clock! Hopefully you have all solved out the balls in boxes problem from last time. Given that you probably have, writing a solution is a totally pointless act, done simply to amuse myself. Here we go.
First of all, lets find some N for which we cannot always win. Specifically, consider that N=1 and there are 1000 balls. Box 999 might have 500 of them and box 1000 has the other 500 of them. In this case we have no legal moves and cannot win. What is the largest N can be so that we still might have no legal moves? To put it another way, when is N big enough to guarantee that we always have a legal move?
The most balls we can have with no legal move is 1 ball in box 2, 2 balls in box 3, 3 balls in box 4,..... k-1 balls in box k. If we have any more balls than that it will be guaranteed that we always have at least one legal move. That number of balls is 1+2+3+4+..+999 = 999*1000/2. So if N is larger than 999/2, so 500 or more, then we always have a legal move. If N is less than 500 we might have no legal moves, thus we may have started in a position with no legal moves.
Now, if N is 500 or larger, we know we always have a legal move, is this enough to guarantee that we can eventually wander our way to a solution? First note that if all the balls were in box 1, we would basically be done, we can move balls from box 1 to any target box simply by moving them 1 at a time. In fact, if we want to move balls from box i to box j, it costs us nothing to move from box i to box 1 then from box 1 to box j, so we might as well only consider moves to and from box 1.
So, assume N is 500 or larger, we have some boxes that have enough balls in them such that we can perform a move. Make all the moves you can from those boxes to box 1, such that when we are done the only legal moves we have left are from box 1. When we are done this box 1 must be nonempty, for if box 1 was empty we would have no moves, and that is impossible for N at least 500. Now, either all the balls are in box 1 or they are not, if all the balls are in box 1 we are done, we can solve the problem as mentioned earlier. If not all the balls are in box 1, there exists some k and x where box k has x balls in it, with k>1, k>x, and x>0. One can see that box 1 has at least k-x balls in it, this is apparent because if it did not I could move all the balls from box 1 into box k and leave myself with no legal moves (which is impossible). So, we can move k-x balls from box 1 into box k, bringing box k up to k balls, and we may then move all the balls from box k to box 1. We repeat this process for each nonempty box k with k>1. In the end all the balls are in box 1 and the game is trivially won.
I'm not sure why I liked this problem so much, I guess I was just pleasantly surprised to see something so simple on a Putnam. I cannot say that their questions lack creativity, but this particular problem is just the kind of creativity I like.
First of all, lets find some N for which we cannot always win. Specifically, consider that N=1 and there are 1000 balls. Box 999 might have 500 of them and box 1000 has the other 500 of them. In this case we have no legal moves and cannot win. What is the largest N can be so that we still might have no legal moves? To put it another way, when is N big enough to guarantee that we always have a legal move?
The most balls we can have with no legal move is 1 ball in box 2, 2 balls in box 3, 3 balls in box 4,..... k-1 balls in box k. If we have any more balls than that it will be guaranteed that we always have at least one legal move. That number of balls is 1+2+3+4+..+999 = 999*1000/2. So if N is larger than 999/2, so 500 or more, then we always have a legal move. If N is less than 500 we might have no legal moves, thus we may have started in a position with no legal moves.
Now, if N is 500 or larger, we know we always have a legal move, is this enough to guarantee that we can eventually wander our way to a solution? First note that if all the balls were in box 1, we would basically be done, we can move balls from box 1 to any target box simply by moving them 1 at a time. In fact, if we want to move balls from box i to box j, it costs us nothing to move from box i to box 1 then from box 1 to box j, so we might as well only consider moves to and from box 1.
So, assume N is 500 or larger, we have some boxes that have enough balls in them such that we can perform a move. Make all the moves you can from those boxes to box 1, such that when we are done the only legal moves we have left are from box 1. When we are done this box 1 must be nonempty, for if box 1 was empty we would have no moves, and that is impossible for N at least 500. Now, either all the balls are in box 1 or they are not, if all the balls are in box 1 we are done, we can solve the problem as mentioned earlier. If not all the balls are in box 1, there exists some k and x where box k has x balls in it, with k>1, k>x, and x>0. One can see that box 1 has at least k-x balls in it, this is apparent because if it did not I could move all the balls from box 1 into box k and leave myself with no legal moves (which is impossible). So, we can move k-x balls from box 1 into box k, bringing box k up to k balls, and we may then move all the balls from box k to box 1. We repeat this process for each nonempty box k with k>1. In the end all the balls are in box 1 and the game is trivially won.
I'm not sure why I liked this problem so much, I guess I was just pleasantly surprised to see something so simple on a Putnam. I cannot say that their questions lack creativity, but this particular problem is just the kind of creativity I like.
Balls In Boxes
New puzzle o'clock! I should probably be working instead of blogging, but blogging is so much more fun. Anyway, I found something of a neat puzzle on the Putnam 2010 exam. Usually those exams are just filled with semi-impossible math problems involving stupid functions, but there was one question on that exam I thought was pretty cool as a puzzle:
Naturally, the fundamental nature of the solution is not particularly sensitive to the number 1000, in the actual Putnam they used 2010, cause thats how they roll.
There are 1000 boxes, labelled 1 through 1000. There are 1000*N balls in the boxes, distributed randomly between the boxes. You will be playing a 1 player game, trying to average out the balls in the boxes, so that each box has exactly N balls in it.
The only legal move in the game is to select a number K and move exactly K balls from box K into any other box. So you could go to box 247 and move exactly 247 balls from that box into any other box. If box 247 has fewer than 247 balls in it, you cannot do this, so you don't get to move any of them. You are allowed to keep making legal moves as long as you like, and you win if every box has exactly N balls in it.
Given that in total there are 1000*N balls in the 1000 boxes, for what values of N is it always possible to win, regardless of the initial configuration of the balls?
Naturally, the fundamental nature of the solution is not particularly sensitive to the number 1000, in the actual Putnam they used 2010, cause thats how they roll.
Forward Is Backward
Some time ago, I had presented Jon with the balls in a bag puzzle, and he had suggested the following reverse puzzle:
Anyway, I'm going to just solve this reverse problem on the spot, it seems like the thing to do. Let F(k) be the average number of steps it takes to get from a state with k red balls to a state with one red ball. Note that knowing the number of red balls totally specifies a state, since all non-red balls are of unique colours. F(1)=0 trivially, and we seek F(N), the state with N red balls. The probability that we move from a state with k red balls to a state with k-1 red balls (I will call this P(k)) is the chance that we draw exactly two red balls from the bag, that is:
Therefore, for F(N) we have:
Alright, so this (much easier) problem has the same answer as the "forward" ball problem. I guess in some sense it is the correct reversal of the initial problem, since it has the same answer. I would love to find a way to show that these two problems have the same answer (that does not rely on using the fact that they both give (N-1)^2), so that way we can solve the harder one just by doing the easier one. Anyway, thats all I got here, if you can find a way to show that these problems are equivalent, feel free to give it in the comments.
Consider a bag with N red balls. At each step, you select two balls from the bag and if they are the same colour, you repaint one of them a new unique colour. If they are different, then do nothing. Either way, place the two balls back in the bag and begin a new step. Given long enough, eventually all the balls in the bag will be of different colours, on average how many steps does it take?Its clear that this is some sort of reverse of the original problem, however, it is not clear that this is actually the "best" reverse. One could also give the newly coloured balls "random colours from the list of N colours" instead of new unique ones, but it turns out this problem is much more awful.
Anyway, I'm going to just solve this reverse problem on the spot, it seems like the thing to do. Let F(k) be the average number of steps it takes to get from a state with k red balls to a state with one red ball. Note that knowing the number of red balls totally specifies a state, since all non-red balls are of unique colours. F(1)=0 trivially, and we seek F(N), the state with N red balls. The probability that we move from a state with k red balls to a state with k-1 red balls (I will call this P(k)) is the chance that we draw exactly two red balls from the bag, that is:
P(k)=k/N*(k-1)/(N-1)Of course, if something happens with probability p, then on average we need 1/p tries to have it happen once (I proved this back in the post where I gave the solution to the prisoner problem). Naturally then, we have:
F(k)-F(k-1)=(N-1)N/(k-1)kand since F(1)=0, we can just express F(m) as F(m)-F(m-1)+F(m-1)-F(m-2)+...+F(2)-F(1), to give
F(m)=Σ N(N-1)/k(k-1)summing k from 2 to m.
Therefore, for F(N) we have:
N(N-1)Σ 1/k(k-1)summed k from 2 to N. This series telescopes, the terms look like 1/1-1/2+1/2-1/3+1/3-1/4+...-1/(N-1)+1/(N-1)-1/N. The final result is then that:
=N(N-1)Σ [1/(k-1)-1/k]
F(N)=N(N-1)[1-1/N]Weird.
=N(N-1)[(N-1)/N]
=(N-1)^2
Alright, so this (much easier) problem has the same answer as the "forward" ball problem. I guess in some sense it is the correct reversal of the initial problem, since it has the same answer. I would love to find a way to show that these two problems have the same answer (that does not rely on using the fact that they both give (N-1)^2), so that way we can solve the harder one just by doing the easier one. Anyway, thats all I got here, if you can find a way to show that these problems are equivalent, feel free to give it in the comments.
Its All Red
Time to post the solution to the balls in a bag problem from last time. The solution actually gets pretty crazy, and I actually had to make up a tiny amount of new math (new to me, anyway) in order to justify the solution that Matt came to me with, but all in all it was a good adventure.
First of all, we are going to select a single colour of ball from the bag (let it be called "red") and only watch the progress of that colour. If red is ever eliminated we will declare the experiment a failure and try again, if red is ever the only colour left we ask how many steps it took. Naturally this means that only 1/N of our experiments even end in success, so I will have to account for that at the end, but we will cross that bridge when we come to it. Next, let us define a function F(k,m) as the probability that we are in a state with k red balls after m steps. Naturally F(1,0)=1, F(k,0)=0 for k ≠ 1, and the asymptotic behaviour of F in m is
In words, this is that our initial condition has exactly 1 red ball, and in the long run we will either have all red balls (probability 1/N) or no red balls (otherwise). It is worth noting that we expect that there are no experiments that run forever (that would be limm->∞F(k,m)=nonzero for k neither N nor 0), that have a nonzero probability. This is to be contrasted with the chance that the expectation value of the path length being infinity, which I have not ruled out yet. Of course, summing F(k,m) over k always gives 1.
Alright, now that we have that, we need to find the recursion relation on F. If we are entering the (m+1)th step, the chance that we get to having k red balls is given by:
that is, the chance we drew a red then non-red from k-1, plus the chance we drew a non-red then red from k+1 and the chance we drew two red or two non-red from k. This can be written as:
Why I separated out that F(k,m) term will be apparent later.
Let us now make a series of vectors, Vm with N-1 elements so that the kth element of the vector Vm is given by F(k,m). Then the recursion relation gives us
and the matrix M is specified by the recursion relation. Note that V only keeps track of having 1 through N-1 red balls left, so information "leaks" out the ends of it and the sum of the elements of V is not conserved. It is also worth noting that Vm tends to the zero vector as m tends to infinity, no matter how the initial data for V looked (that point will turn out to be extremely important later, make sure you convince yourself of it now).
Ok, let us try to get a feel for the matrix M that iterates on V. The diagonal of M is the term that keeps F(k,m) at F(k,m+1), that is to say that the kth element on the diagonal is 1-2k(N-k)/(N(N-1)). There are also off-diagonal terms adjacent to the diagonal, but everything else is zero. For notational convenience, I will denote N(N-1)=Z. For some large N, the first part of the matrix looks like:
The kth diagonal element is 1-2*k(N-k)/Z, above and below the kth diagonal element is k(N-k)/Z. Every column adds to 1, except for the first and last columns, which represent probability leaking out the ends.
Now that we have this, what the heck do we do with it. Well, we want to find the probability that we end on the mth step, times m, summed over all m. That gives us the expectation value of what step we end on. The probability that we end on the mth step is the last element of Vm-1 (the penultimate state) times (N-1)/N (the chance we draw a red ball) times 1/(N-1) (the chance we draw the final non-red ball). So we want
summed over m. Actually this is not quite right, since only 1/N of the experiments even end the way we want, we must also multiply by N. Anyway, we know that Vm-1=Mm-1V0, and V0 is given as the column vector [1,0,0,0,...] (which I will write as [1,0,0,0,...]T, for lack of ability to write column vectors).
To put it together, we seek to find
summed over m=0 to ∞ of course.
Much of that is just constants relative to the sum, and we really just need to evaluate
Now, if instead of a matrix M, we had a real number, x, we could easily use
so we would like to say:
Ok, so can we take the derivative with respect to a matrix? Well, its not at all uncommon to do that in physics, we often consider scalar function S(M) as define the derivative (dS/dM)ij as the derivative of S with respect to the ijth component of M. This means dS/dM is a matrix. Following this up, we would expect that if we have a matrix function T(M) with two component indices (such as M2 or M-1), then dT/dM would have four indices. If we define the derivative dT/dM to have two indices by using the definition
summing over k (as we do in matrix multiplication), then using
it is easy to show that
for all integers n (to get the inverses, you must use that d/dM (M-1M)=0).
Alright, so we can now say with confidence that
So now we just need a way to evaluate Σ Mm. Again, if this were a real number x, we would simply say that
(as long as |x|<1) so how can we do something similar for a matrix? First of all, let us consider the pth partial sum, Σ Mm summed m from 0 to p. It is easy to see that
so as long as we have (1-M) being invertible and limp->∞Mp+1=0, then we can say that Σ Mm=(1-M)-1
Remember when I said that Vm tends to zero no matter what the initial data is? this fact can prove both of the statements that we need. A matrix is really just defined in terms of how it acts on vectors, thus if a matrix obeys the relationship limp->∞MpV=0 for all vectors V, then it means that limp->∞Mp=0, since it really apparently is the zero matrix. We knew from before that this is true for our matrix M. I'll admit that I have not really proven it, but it is apparent from the physics of the problem (people who know me will understand that when I say something is "apparent from the physics of the problem", I really mean "I don't know how to prove this, but it is so obvious from the way things are set up, I feel no need to").
So we can now say with confidence that
when we take the sum to infinity. Now, can we invert the matrix (1-M) (which I will call W)? Well, first let us assume that W has no inverse. This means that W must have a null space, that is to say there is a nonzero vector U such that WU=0. This naturally implies that (1-M)U=0 so MU=U, U is an eigenvector with eigenvalue 1. But this means that MpU=U for all p, and so that is even true in the limit of large p, but for large p we have Mp must vanish. This is a contradiction proving that W (=(1-M)) is invertible.
So, earlier, we had seen that the answer to the question we seek was given by
which we can now rewrite as
That is, we seek the inverse of the matrix (1-M) and we want the element in the last row and first column in the square of said matrix.
W looks like
Z being N(N-1) as before. We can actually just factor out 1/Z now, and get
as the expression for WZ.
Now, if we want the last element in W-2, we want the last row and the first column of W-1 and we need no other information about W-1 except that it exists (and it does). Find a row vector that gives 1 when it acts on the last column of W and gives 0 for all other columns (you might want to write W on paper now, to get a feel for it). We find that the last row in the matrix W-1 is [1,2,3,4,5...,N-1], you might want to try out W in a few simple cases of N=3,4,5 to convince yourself of this. We also need the first column in the matrix W-1, that is, we need a column vector that gives 1 when it acts on the first row of W, and 0 when it acts on any other row. The vector is [Z/N, Z/2N, Z/3N, Z/4N, ....., Z/(N(N-1))]T. Naturally, the last element of the first column and the first element of the last row agree.
Finally, we multiply this last row and first column to get the element of the last row and first column of W-2 Z/N+Z/N+Z/N+..., and we have a total of N-1 terms, but Z is N(N-1).
So we have (N-1)^2, our final answer. I have a bit more to write about this puzzle, but this seems like quite enough as it is.
First of all, we are going to select a single colour of ball from the bag (let it be called "red") and only watch the progress of that colour. If red is ever eliminated we will declare the experiment a failure and try again, if red is ever the only colour left we ask how many steps it took. Naturally this means that only 1/N of our experiments even end in success, so I will have to account for that at the end, but we will cross that bridge when we come to it. Next, let us define a function F(k,m) as the probability that we are in a state with k red balls after m steps. Naturally F(1,0)=1, F(k,0)=0 for k ≠ 1, and the asymptotic behaviour of F in m is
limm->∞F(N,m)=1/N
limm->∞F(0,m)=(N-1)/N
limm->∞F(k,m)=0 for all other k
In words, this is that our initial condition has exactly 1 red ball, and in the long run we will either have all red balls (probability 1/N) or no red balls (otherwise). It is worth noting that we expect that there are no experiments that run forever (that would be limm->∞F(k,m)=nonzero for k neither N nor 0), that have a nonzero probability. This is to be contrasted with the chance that the expectation value of the path length being infinity, which I have not ruled out yet. Of course, summing F(k,m) over k always gives 1.
Alright, now that we have that, we need to find the recursion relation on F. If we are entering the (m+1)th step, the chance that we get to having k red balls is given by:
F(k,m+1)=[(k-1)/N]*[(N-(k-1))/(N-1)]F(k-1,m)
+[(N-(k+1))/N]*[(k+1)/(N-1)]F(k+1,m)
+[k/N*(k-1)/(N-1)+(N-k)/N*(N-k-1)/(N-1)]F(k,m)
that is, the chance we drew a red then non-red from k-1, plus the chance we drew a non-red then red from k+1 and the chance we drew two red or two non-red from k. This can be written as:
F(k,m+1)=1/(N(N-1))*
[(k-1)(N-k+1)F(k-1,m)+
(N-k-1)(k+1)F(k+1,m)-
2k(N-k)F(k,m)]
+F(k,m)
Why I separated out that F(k,m) term will be apparent later.
Let us now make a series of vectors, Vm with N-1 elements so that the kth element of the vector Vm is given by F(k,m). Then the recursion relation gives us
Vm+1=MVm
and the matrix M is specified by the recursion relation. Note that V only keeps track of having 1 through N-1 red balls left, so information "leaks" out the ends of it and the sum of the elements of V is not conserved. It is also worth noting that Vm tends to the zero vector as m tends to infinity, no matter how the initial data for V looked (that point will turn out to be extremely important later, make sure you convince yourself of it now).
Ok, let us try to get a feel for the matrix M that iterates on V. The diagonal of M is the term that keeps F(k,m) at F(k,m+1), that is to say that the kth element on the diagonal is 1-2k(N-k)/(N(N-1)). There are also off-diagonal terms adjacent to the diagonal, but everything else is zero. For notational convenience, I will denote N(N-1)=Z. For some large N, the first part of the matrix looks like:
[1-2(N-1)/Z, 2(N-2)/Z, 0, 0, 0, ....]
[(N-1)/Z, 1-2*(2(N-2))/Z, 3(N-3)/Z, 0, 0, ....]
[0, 2(N-2)/Z, 1-2*(3(N-3))/Z, 4(N-4)/Z, 0, ....]
....
The kth diagonal element is 1-2*k(N-k)/Z, above and below the kth diagonal element is k(N-k)/Z. Every column adds to 1, except for the first and last columns, which represent probability leaking out the ends.
Now that we have this, what the heck do we do with it. Well, we want to find the probability that we end on the mth step, times m, summed over all m. That gives us the expectation value of what step we end on. The probability that we end on the mth step is the last element of Vm-1 (the penultimate state) times (N-1)/N (the chance we draw a red ball) times 1/(N-1) (the chance we draw the final non-red ball). So we want
Σ m/N [0,0,0,....0,1]Vm-1
summed over m. Actually this is not quite right, since only 1/N of the experiments even end the way we want, we must also multiply by N. Anyway, we know that Vm-1=Mm-1V0, and V0 is given as the column vector [1,0,0,0,...] (which I will write as [1,0,0,0,...]T, for lack of ability to write column vectors).
To put it together, we seek to find
Σ m [0,0,0,....0,1]Mm-1[1,0,0,0,...]T
summed over m=0 to ∞ of course.
Much of that is just constants relative to the sum, and we really just need to evaluate
Σ m Mm-1
Now, if instead of a matrix M, we had a real number, x, we could easily use
d Σ xm/dx = Σ m xm-1
so we would like to say:
Σ m Mm-1=d Σ Mm/dM
Ok, so can we take the derivative with respect to a matrix? Well, its not at all uncommon to do that in physics, we often consider scalar function S(M) as define the derivative (dS/dM)ij as the derivative of S with respect to the ijth component of M. This means dS/dM is a matrix. Following this up, we would expect that if we have a matrix function T(M) with two component indices (such as M2 or M-1), then dT/dM would have four indices. If we define the derivative dT/dM to have two indices by using the definition
dT/dMij=Σ (d/dMik)Tkj
summing over k (as we do in matrix multiplication), then using
(d/dMij)Mkl=δ ikδ jl
it is easy to show that
dMn/dM=nMn-1
for all integers n (to get the inverses, you must use that d/dM (M-1M)=0).
Alright, so we can now say with confidence that
Σ m Mm-1=d Σ Mm/dM
So now we just need a way to evaluate Σ Mm. Again, if this were a real number x, we would simply say that
Σ xm=1/(1-x)
(as long as |x|<1) so how can we do something similar for a matrix? First of all, let us consider the pth partial sum, Σ Mm summed m from 0 to p. It is easy to see that
(1-M)Σ Mm=1-Mp+1
so as long as we have (1-M) being invertible and limp->∞Mp+1=0, then we can say that Σ Mm=(1-M)-1
Remember when I said that Vm tends to zero no matter what the initial data is? this fact can prove both of the statements that we need. A matrix is really just defined in terms of how it acts on vectors, thus if a matrix obeys the relationship limp->∞MpV=0 for all vectors V, then it means that limp->∞Mp=0, since it really apparently is the zero matrix. We knew from before that this is true for our matrix M. I'll admit that I have not really proven it, but it is apparent from the physics of the problem (people who know me will understand that when I say something is "apparent from the physics of the problem", I really mean "I don't know how to prove this, but it is so obvious from the way things are set up, I feel no need to").
So we can now say with confidence that
(1-M)Σ Mm=1
when we take the sum to infinity. Now, can we invert the matrix (1-M) (which I will call W)? Well, first let us assume that W has no inverse. This means that W must have a null space, that is to say there is a nonzero vector U such that WU=0. This naturally implies that (1-M)U=0 so MU=U, U is an eigenvector with eigenvalue 1. But this means that MpU=U for all p, and so that is even true in the limit of large p, but for large p we have Mp must vanish. This is a contradiction proving that W (=(1-M)) is invertible.
So, earlier, we had seen that the answer to the question we seek was given by
Σ m [0,0,0,....0,1]Mm-1[1,0,0,0,...]T
which we can now rewrite as
[0,0,0,....0,1]W-2[1,0,0,0,...]T
That is, we seek the inverse of the matrix (1-M) and we want the element in the last row and first column in the square of said matrix.
W looks like
[2*(N-1)/Z, 2(2-N)/Z, 0, 0, 0, 0,.....]
[(1-N)/Z, 2*2(N-2)/Z, 3(N-3)/Z, 0, 0, 0,.....]
[0, 2(N-2)/Z, 2*3(N-3)/Z, 4(N-4)/Z, 0, 0,.....]
.....
Z being N(N-1) as before. We can actually just factor out 1/Z now, and get
[2*(N-1), 2(2-N), 0, 0, 0, 0,.....]
[(1-N), 2*2(N-2), 3(3-N), 0, 0, 0,.....]
[0, 2(2-N), 2*3(N-3), 4(4-N), 0, 0,.....]
[0, 0, 3(3-N), 2*4(N-4), 5(5-N), 0,.....]
.....
as the expression for WZ.
Now, if we want the last element in W-2, we want the last row and the first column of W-1 and we need no other information about W-1 except that it exists (and it does). Find a row vector that gives 1 when it acts on the last column of W and gives 0 for all other columns (you might want to write W on paper now, to get a feel for it). We find that the last row in the matrix W-1 is [1,2,3,4,5...,N-1], you might want to try out W in a few simple cases of N=3,4,5 to convince yourself of this. We also need the first column in the matrix W-1, that is, we need a column vector that gives 1 when it acts on the first row of W, and 0 when it acts on any other row. The vector is [Z/N, Z/2N, Z/3N, Z/4N, ....., Z/(N(N-1))]T. Naturally, the last element of the first column and the first element of the last row agree.
Finally, we multiply this last row and first column to get the element of the last row and first column of W-2 Z/N+Z/N+Z/N+..., and we have a total of N-1 terms, but Z is N(N-1).
So we have (N-1)^2, our final answer. I have a bit more to write about this puzzle, but this seems like quite enough as it is.
Balls In A Bag
I have been pretty consistent in posting just once a week, and thats mostly just been so I don't run out of blogging material, but Matt recently solved a problem that we have been working on for nearly 3 years so I really wanted to post the solution as soon as I was able to work out the wrinkles. This is the problem as I first learned it on the forums at xkcd:
Doing the problem "properly" is very difficult, and I would only suggest it if you are crazy. However, solving it in the cases of N=2,3,4 is not particularly hard, and from that you will be able to guess what the answer should be.
Consider you have a bag filled with N balls, each with a different colour. At each step you will randomly select a ball from the bag, look at its colour, and select another ball from the bag, and repaint the second ball to the colour of the first one. After doing that, place both balls back into the bag and begin a new step.
After doing this enough times, it will eventually happen that all the balls in the bag will have the same colour. On average, how many steps does it take for this to happen?
Doing the problem "properly" is very difficult, and I would only suggest it if you are crazy. However, solving it in the cases of N=2,3,4 is not particularly hard, and from that you will be able to guess what the answer should be.
Ball Solutions
So, last time I introduced a ball problem, and I guess its time to show the solution. The solution is actually really simple, but I feel like doing a full-blown derivation.
First, let us define f(n,m) to be the solution to our problem, specifically it is how many black balls will be left if we started with n white and m black balls. We know f on the boundary cases:
First, let us find f(1,m)
Actually, after the fact, you can intuit the answer in the limit of large m (does it still count as intuiting it after the fact?). If m is large, you can picture many black balls in a line, with a few white balls in the mix. If they are sorted randomly, and then taken from one end how many black balls will be after the last white ball? The white balls will evenly divide up the black balls into n+1 groups, and so at the end there will be m/(n+1) black balls.
First, let us define f(n,m) to be the solution to our problem, specifically it is how many black balls will be left if we started with n white and m black balls. We know f on the boundary cases:
1. f(0,m)=mTo get the rest, consider that from a given position with n white balls and m black balls, we have a m/(n+m) chance to remove a black ball, and a n/(n+m) chance to remove a white ball. This means that:
2. f(n,0)=0
f(n,m)=m/(n+m)*f(n,m-1)+n/(n+m)*f(n-1,m)From here we can start to figure stuff out.
First, let us find f(1,m)
f(1,m)=m/(m+1)*f(1,m-1)+1/(m+1)*mFrom here, you can find f(1,1)=1/2, f(1,2)=1, f(1,3)=3/2 and guess f(1,m)=m/2. Alright, great, then a similar process on f(2,m) gives you that it is m/3, and this leads one to the general guess of f(n,m)=m/(n+1). Since it is already known to be true for the boundary cases, it suffices to show that when this formula holds for f(n-1,m) and f(n,m-1) it then holds for f(n,m). Something of a double induction:
f(1,m)=m(m+1)*(f(1,m-1)+1)
f(n,m)=m/(n+m)*f(n,m-1)+n/(n+m)*f(n-1,m)Yep, it works.
f(n,m)=m/(n+m)*(m-1)/(n+1)+n/(n+m)*m/n
f(n,m)=m/(n+m)*((m-1)/(n+1)+1)
f(n,m)=m/(n+m)*(m-1+n+1)/(n+1)=m/(n+1)
Actually, after the fact, you can intuit the answer in the limit of large m (does it still count as intuiting it after the fact?). If m is large, you can picture many black balls in a line, with a few white balls in the mix. If they are sorted randomly, and then taken from one end how many black balls will be after the last white ball? The white balls will evenly divide up the black balls into n+1 groups, and so at the end there will be m/(n+1) black balls.
Ball Problems
Man, I sure expected to post more often than once a week when I started this stupid thing. Eh, whatever, who reads this anyway? Anyway, time to introduce a new problem. I originally learned this problem somewhere randomly on the intertubes.
Yeah, OK, thats all I got. Solution to follow later.
Consider you have a bag with n white balls and m black balls in it. You randomly pull balls out of the bag, one at a time, until you have drawn all the white balls. On average, how many black balls will be left when you stop?
Yeah, OK, thats all I got. Solution to follow later.
Subscribe to:
Posts (Atom)
