wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> random motion in a rectangle
        
(Message started by: JocK on Jan 9^th, 2005, 11:06am)

Title: random motion in a rectangle
Post by JocK on Jan 9^th, 2005, 11:06am

A particle at the centre of a rectangle starts a perfectly random Brownian motion. Given that the likelihood it first hits a longer boundary is twice as large than the likelihood that it hits a shorter boundary first, determine the aspect ratio (ratio of long side to short side) of the rectangle.

Title: Re: random motion in a rectangle
Post by rmsgrey on Jan 9^th, 2005, 12:01pm

::[hide]roughly 1.4[/hide]::?

As a (vaguely) educated guess

Title: Re: random motion in a rectangle
Post by JocK on Jan 9^th, 2005, 1:55pm

on 01/09/05 at 12:01:53, rmsgrey wrote:

::[hide]roughly 1.4[/hide]::?

As a (vaguely) educated guess

Close, but no sigar. (Rounded off to one decimal place, the solution is not 1.4.)

Title: Re: random motion in a rectangle
Post by towr on Jan 9^th, 2005, 3:06pm

Another guess, ::[hide]1.62[/hide]::
Or maybe ::[hide]1.57[/hide]::
;D

Title: Re: random motion in a rectangle
Post by THUDandBLUNDER on Jan 9^th, 2005, 5:12pm

Was this puzzle inspired by SIAM 2002 Problem #10 (http://web.mat.bham.ac.uk/marijke/SIAM2002/siam-Xm.html)?
It has a rectangle of 10 x 1 and a probability of hitting one of the shorter sides of only 1 in 2605802 (!)

So I think the ratio L/W should be pretty small.
How about [hide]1.15[/hide]?

Title: Re: random motion in a rectangle
Post by BNC on Jan 9^th, 2005, 10:14pm

My guess would be ::[hide]1.73[/hide]::

Title: Re: random motion in a rectangle
Post by towr on Jan 10^th, 2005, 12:41am

on 01/09/05 at 22:14:15, BNC wrote:

My guess would be ::[hide]<hidden>[/hide]::

That's what I thought of as well just before I went to sleep yesterday..
It's what you get by considering a wave starting at the center and looking what part of the energy hits what side. But the result for the similar problem mentioned by Thud doesn't correspond to the one given in the page he links to.

Title: Re: random motion in a rectangle
Post by BNC on Jan 10^th, 2005, 1:37am

on 01/10/05 at 00:41:00, towr wrote:

Yeah, I noticed it too... :-/

Title: Re: random motion in a rectangle
Post by towr on Jan 10^th, 2005, 2:18am

The reason why it's wrong is also mentioned in the page Thud links to, the capture at the edges changes the distribution inside the rectangle (so it stops being a nice gaussian wave).

I think I'll wait to see what my simulation will yield as a result before making any more guesses. But that might take the rest of the day to finish.

Title: Re: random motion in a rectangle
Post by Barukh on Jan 10^th, 2005, 9:50am

Here's my try: [smiley=square.gif][hide]1.29...[/hide][smiley=square.gif]

Title: Re: random motion in a rectangle
Post by towr on Jan 10^th, 2005, 1:38pm

I suspect my simulation program must be screwed up, I get about 1.70, which all things considering may be a bit high.
Not much reason to hide it, we're just bidding numbers here without further justifaction.

Title: Re: random motion in a rectangle
Post by JocK on Jan 11^th, 2005, 9:23am

Barukh... I think you are close... very close..! 8)

(Getting a rough approximation shouldn't be too difficult... I'm very curious though what accuracy will be reached...)

Title: Re: random motion in a rectangle
Post by SWF on Jan 11^th, 2005, 5:23pm

I am convinced that probability should be governed by the same PDE as diffusion. If for a point (x,y) the probability of random walk reaching the long vertical sides before one of the horizontal sides is [phi](x,y), and the rectangle has dimensions 2 by 2*h, [phi] must satisfy:

0 = [partial]²[phi]/[partial]x² + [partial]²[phi]/[partial]y² with boundary conditions [phi]([pm]1,y) = 1 and [phi](x,[pm]h)=0

Solution for probability at any point in the rectangle is:

[phi](x,y) = (4/[pi])*[sum] (-1)ⁿ/(2n+1) cos(a_ny) cosh(a_nx)/cosh(a_n)

where sum is over n=0 to infinity and a_n=(2n+1)[pi]/2/h. For probability of reaching one of the long sides first to be double of it reaching a short side first, [phi](0,0)=2/3:

[pi]/6 = [sum] (-1)ⁿ/(2n+1)/cosh((2n+1)[pi]/2/h)

Solving for h gives: 1.279261571171...

Title: Re: random motion in a rectangle
Post by Barukh on Jan 12^th, 2005, 4:17am

SWF, I am just curious how did you solve the last equation for h?

From different sources, I've got an elementary expression that can be easily computed and gives the same result as SWF's, but its derivation includes a few steps that I still don't understand. I will try to consolidate my efforts and explain it here later.

Title: Re: random motion in a rectangle
Post by THUDandBLUNDER on Jan 12^th, 2005, 6:52am

Quote:

[pi]/6 = [sum] (-1)ⁿ/(2n+1)/cosh((2n+1)[pi]/2/h)

According to the above notation, what is w/x/y/z?
What does the above formula give for h = 10?

Title: Re: random motion in a rectangle
Post by SWF on Jan 12^th, 2005, 7:04pm

Barukh, I just solved that last equation numerically. I would be interested in the more elementary solution. Often using functions of a complex variable and conformal mapping a more simple solution can be found that does not require an infinte series. By the way I found another expression that can be used to find h:

[pi]/12 = [sum] (-1)ⁿ tan^-1( exp(-(2n+1)[pi]/2/h) )

ThudandBlunder, I have no idea what you mean by "w/x/y/z", unless some of the special symbols like pi or subscripts are showing up strangely for you. When h is 10, that formula gives probability of reaching a long side first as 0.999999616...

Title: Re: random motion in a rectangle
Post by Barukh on Jan 13^th, 2005, 4:07am

Here’s what I know so far.

First of all, it is clear that the SIAM Challenge #10 mentioned by T&B, is just the inverse of the problem stated (up to parameters given). Also, it was clear to me that if I don’t want to rely on the Monte-Carlo method, I need some advanced technique from high math that I don’t master. So, I went to learn what the winners of the contest had to suggest. In what follows, I will describe what I liked most. Sometimes, I will omit details – partially because I cannot explain them, and partially because they are too technical.

I thought that if we were given the circle with the marked arcs - instead of the rectangle with long and short sides – then the solution would be trivial (see the drawing), since the probability would be simply [alpha]/[pi]. The real question is: how do we transform the rectangle to the circle so that the probability of hitting the small arc is the same as the probability of hitting the small side? It turns out that the needed transformation is the conformal mapping – as was correctly suggested by SWF. The conformal mapping (CM) is a transformation that preserves angles.

Hmm, if you ask me why CM leaves the sought probability unchanged – I will say that I don’t understand. One of the possible answers would be that the Brownian process stated in the problem obeys the Laplace Equation, and the solutions of the latter are preserved under CM (my friend mathematician I talked to this morning, confirmed this and told it’s not difficult to prove).

Now, let’s see, how do we get the required transformation. This is dealt in Complex Analysis and took me a lot of time to understand at the very high level. Usually, it is done in two steps: first, the rectangle is transformed onto the half-plane using Complete Elliptic Integrals of the first kind, and then the half-plane is transformed onto the unit circle using Mobius transformations. It sounds frightening, but the essentials are easy to comprehend: the complete elliptic integral is a function E(k) of the parameter k, and it turns out that the aspect ratio r of the rectangle and the arc length [alpha] of its circle image are related by the following formula:

r = E(cos([alpha]/2))/E(sin([alpha])/2)
(again, I don’t know how to prove this, but it shouldn’t be difficult for the specialist).

At this point, it seems that we didn’t get too far. Fortunately, there is an elegant way to evaluate elliptic integrals using the Arithmetic-Geometric Mean (http://mathworld.wolfram.com/Arithmetic-GeometricMean.html) (AGM) of 2 numbers. In fact, we have:

E(k) = AGM(1, k).
The following nice article (http://numbers.computation.free.fr/Constants/Pi/piAGM.html) (section 4.2) provides an insight. AGM is such a simple algorithm that can be programmed at the advanced calculator.

Going back to the conditions of the problem, we see that [alpha] = [pi]/3, and therefore r = AGM(1, [sqrt]3/2) / AGM(1, 1/2) = 1.27926157117100..

It is interesting to mention that for the problem posted at SIAM Challenge, this approach also works, but requires an iteration process to find the [alpha].

Title: Re: random motion in a rectangle
Post by JocK on Jan 13^th, 2005, 12:33pm

Nice job SWF and Barukh!

Title: Re: random motion in a rectangle
Post by SWF on Jan 13^th, 2005, 8:53pm

I found deciding that the probability was a solution to Laplace equation was the tough part. How to solve this partial differential equation in a rectangle with simple boundary conditions is fairly well known- at least the solution by infinite series is. As for this probability following Laplace equation, I justified to myself by noticing that starting at the center of a circle, the first point reached on the cirfumference is equally likely all around. So [phi] (as defined above) in the center of the circle equals the mean value of [phi] on the circumference. I remembered that this is a property of solutions to the Laplace Equation.

Barkuh, after you suggested there is an elementary solution, I briefly tried conformal mapping, but immediately quit upon seeing elliptic integrals. I was not familar with that AGM relation to elliptic integrals. Thanks for explaining all of that.

Here is a side exercise: Starting with the expression I gave above where [pi]/6=...cosh()..., how did I convert it to [pi]/12=...arctan()...? (complex variable transformations not required).

Title: Re: random motion in a rectangle
Post by TenaliRaman on Jan 15^th, 2005, 1:53am

cosh(x) = (e^x+e^-x)/2
1/cosh(x)
= 2e^-x(1/(1+e^-2x))
= 2[sum](e^-x)²ⁱ⁺¹

Let x = [(2n+1) [pi] /2h]

Sub this expression in the formula involving cosh.
This will give us a double sum expression.

Interchange the order of summation, the inner sum then becomes the arctan series and we are done!!

-- AI