

Title: TwoFace Escape Post by william wu on Sep 30^{th}, 2003, 9:59pm After pulling a heist, TwoFace's gang is running from Batman and the cops. Hoping to increase the difficulty of being tracked, the gang heads for the Binary Tree Labyrinth, whose root node begins somewhere in the outskirts of Gotham City. The Binary Tree Labyrinth is a network of tunnels that looks like a binary tree from an eagle's eye view  at every crossroads one can go either left or right, as shown in the picture attached at the bottom. Highlighted in bold is an example path through the labyrinth, which first goes left, then right, then right, then left ... The plan now is to split up. While most of his gang was planning to just run through the Labyrinth in no particular fashion, TwoFace insists on using the randomness of fair coin flips as their guide (as he does for almost all decisions in life). After giving fair coins to each member of his crew, TwoFace orders that everyone use the following policy: At every crossroads, flip your coin. If the coin is heads, go left; if it is tails, go right. All the gangsters start at the root node and run through the labyrinth at the same speed. Finally, a gangster is allowed to stop running (they can't run forever) when he reaches a crossroads and discovers that he is alone. Given there are n gangsters, 1) What is the average number of coin flips that will occur until all the gangsters stop running? 2) What is the average length of the paths taken by each gangster after they all stop running? (Path length is measured by the number of tunnels traversed.) 3) What is the average length of the longest path taken out of all the gangsters, after all they all stop running? Disclaimer: I only worked out part 1) for n=4. I just casually made these problems up. They might be very hard :D 

Title: Re: TwoFace Escape Post by James Fingas on Oct 7^{th}, 2003, 1:49pm I think I've got the first question licked. For n=4, the result is 88/7. My method should work for the second question as well. What I did is define A(n) to be the expected number of coin flips for n people to disappear down the Binary Tree Labyrinth (I think only a very small class of people will find the Binary Tree Labyrinth "cool"). [hide] Then we can define A(n+1) by noting that all n+1 criminals flip a coin, and then we have n+2 possible outcomes, according to how many people go right. For each of these, we know the expected number of flips for the group that goes right and for the group that goes left (and they are A(0), A(1), A(2), ... A(n)). The recursion relation follows below: A(n+1) = n+1+[sum]_{i=0..n+1}(^{n+1}C_{i}/2^{i})(A(i)+A(n+1i)) This is not a true recursion relation, because the right side has some A(n+1) terms, but we can move those over to the left hand side if we want to get persnickety. The relation for the second question is similar: B(n+1) = 1+[sum]_{i=0..n+1}(^{n+1}C_{i}/2^{i})(iB(i)+(n+1i)B(n+1i))/(n+1) The form is similar, but we weight the terms differently. Both of these sums in this simplistic form require O(n[sup2]) to compute (and that's what I did for my answer). For the third question, the answer is not so simple, because we need to know not only the expectation for the deepest branch, but also for the distribution of those branches. We'll probably get better results analytically from first principles.[/hide] 

Title: Re: TwoFace Escape Post by James Fingas on Oct 8^{th}, 2003, 10:56am I think I've got the answer to part C as well. If you change the problem a bit: each criminal waits until ALL criminals are alone before stopping, then the solution is easier (note that this change doesn't affect the maximal distance into the labyrinth). We can then define the following functions:[hide] p(n,k) = probability that the n criminals will stop on or before depth k = # of distributions where they are all alone at depth k / total # of distributions p(n,k) = (2^{k} choose n) / (2^{k})^{n} Note that p(n,k) is zero if 2^{k} < n. Therefore, the probability that the criminals stop at depth k is: q(n,k) = probability that the n criminals will stop on depth k = p(n,k)  p(n,k1) = (2^{k} choose n) / (2^{k})^{n}  (2^{k1} choose n) / (2^{k1})^{n} = [(2^{k} choose n)  2*(2^{k1} choose n)] / (2^{k})^{n} = [(2^{k} choose n)  2*(2^{k1} choose n)] / (2^{k})^{n} The average maximal height is therefore just C(n) = [sum]_{i=0..[infty]}q(n,i)*i I can only calculate this directly up to 30 branches deep because of the large numbers involved. Sterling's approximation should give a good result however. [/hide] 

Title: Re: TwoFace Escape Post by Barukh on Sep 14^{th}, 2006, 3:55am James’s recurrent formula that solves the first question should be corrected in the following way (it maybe just a typo): Of course, we take A_{0} = A_{1} = 0. Also, there is a way to check this formula directly for n = 2 and 3, using the definition of the mean value. 1. The case n = 2 is trivial: A_{2} = [sum]_{n > 0}n2^{n} = 4. 2. The case n = 3 is a bit harder. Note that the numbers of coin flips form the set {3n + 2m}, where m, n are positive integers. Then, we get: A_{3} = 3[sum]_{n > 0} [sum]_{m > 0} (3n+2m) 2^{2nm}, which evaluates to 8. Both values correspond to James’s formula. :D 

Title: Re: TwoFace Escape Post by Whiskey Tango Foxtrot on Sep 14^{th}, 2006, 8:10am Well, I was hoping no one would do this... :/ I guess we can just use this as a starting point, then. I do wish we could have started with some fresh logic, though. 

Title: Re: TwoFace Escape Post by Barukh on Sep 14^{th}, 2006, 9:02am on 09/14/06 at 08:10:50, Whiskey Tango Foxtrot wrote:
I apologize if I did something unexpected. I just read your appeal in the new thread: on 09/11/06 at 10:35:53, Whiskey Tango Foxtrot wrote:


Title: Re: TwoFace Escape Post by Whiskey Tango Foxtrot on Sep 14^{th}, 2006, 11:24am Guess I should have been a little more transparent. :/ Hohum... 

Powered by YaBB 1 Gold  SP 1.4! Forum software copyright © 20002004 Yet another Bulletin Board 