10
$\begingroup$

Hi there,

Hopefully the mathematics community can help me out this one, I'm currently studying my senior capstone at my college, and decided to do some research on a chapter in Stanley Farlow's book "Partial Differential Equations for Scientists and Engineers". Basically in one of the chapters he describes a way one can create a game to approximate solutions to PDE's by using the various difference formula's.

Farlow gives a few examples in his book. Namely the dirichlet problem on a square with the laplace equation, however I'd like to extend this result to parabolic and hyperbolic PDE's, and then eventually extend those results to 3-dimensional games. My problem is that I'm unable to find any past research using game theory in this manner other than this one chapter in this book. And I'm not sure if my own foundation in numerical solutions is good enough to do this thing on my own. In other words, I need help.

To give an example of what the game is, start with an nxm lattice, then pick an interior point and run a Monte Carlo simulation that computes random walks from any point $u_{i,j}$ on the lattice to a bound. The game ends when the player hits the bound, and is then given a value(prize) that depends on the boundry/initial conditions. It turns out that the solution to the pde using finite difference equations at that point is the average of the four neighboring points, and so on. Here are some of the questions I NEED to answer, and it would be of great help if I could get some direction on them:

  1. Do you think the random walks on the bounded lattice are self avoiding? I.e. Can the player intersect with the path they've already made? This would definitely change the outcome of the probabilities of a player reaching the bound.

  2. Are there any other good undergraduate-ish texts/resources that give examples of employing finite difference methods on nonlinear PDE's and PDE's with variable coefficients such as $u_{xx} + \sin(x)u_{yy}=0$? (with appropriate boundary/initial conditions) Or just good undergrad resources in general for numerical methods for PDE's? I've gone to my library to check some books out, and some of them are way way way over my head, so I've got to be careful.

  3. What would be the best way to code such a program to compute these walks? I'm pretty sure it's doable in both Mathematica and C++, as to what kind of plan I would make to write it..I've no idea yet.(Making the program would answer definitively if the walks are self avoiding or not)

Google books has a slice of the chapter online, http://books.google.com/books?id=DLUYeSb49eAC&pg=PA347&lpg=PA347&dq=%22tour+du+wino%22&source=bl&ots=vmsz2z6uAP&sig=rZiqwWJ8ESgokmYmBga8qtGVG8U&hl=en&ei=dEaOTp26EeTKsQLg1LymAQ&sa=X&oi=book_result&ct=result&resnum=4&ved=0CDIQ6AEwAw#v=onepage&q=%22tour%20du%20wino%22&f=false

I wish there was someone like Erdos who could just have insane memory to remember past papers on a topic.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
12
$\begingroup$

The connection between random walks, diffusion, and the heat equation is an amazing example of "the unreasonable effectiveness of mathematics." However, it's important to understand that this doesn't extend to other PDE's.

I'd encourage you to make the effort to dig a little deeper so that you understand why a Monte Carlo simulation of a random walk gives solutions to the heat equation. The keys to this are understanding how the binomial distribution applies to the random walk, understanding that the limiting case of the binomial distribution is the normal distribution, seeing that the normal distribution (in particular its probability density function) is a solution to the heat equation, understanding that the linearity of the heat equation allows you to use superposition of solutions, and finally understanding how boundary conditions for your random walk and your heat equation can be made equivalent.

Once you understand all of this, it will become obvious that you don't want to use a self-avoiding random walk in your Monte Carlo simulation- the distribution of the regular random walk is normal and does the right thing for this problem.

In terms of implementing this on the computer, I would suggest that you start with an expample in one space dimension rather than 2 or 3 dimensions. I would also suggest doing this in a computational environment (such as Maple, Mathematica, MATLAB, R, or Python) that already has facilities for generating pseudo-random numbers and plotting the results of your simulation.

A separate, equally large project would be to learn about finite difference methods for the solution of the heat equation boundary value problem. It turns out that this is not as simple as just plugging in finite difference approximations for the derivatives- you also have to work carefully to come up with a stable numerical scheme. Analyzing the stability of your scheme will involve Fourier analysis- it gets complicated.

To answer your specific questions:

  1. You don't want self-avoiding random walks.

  2. Finite difference methods for the heat equation are addressed in many introductory textbooks on numerical analysis. The discussion in Burden and Faires (which has been through many editions and now has new coauthors...) might be suitable for you. Methods for nonlinear PDE's are a more advanced topic.

  3. As I've suggested above, you'll want to use an environment with built-in tools for random number generation and plotting.

Improve this answer
$\endgroup$
6
  • $\begingroup$ My answer may not have been clear about one important point- I'm talking about the time dependent heat equation (which is a parabolic BVP.) The elliptic version of the problem in which you find the steady state solution is easier but not as interesting. Also, in my experience of teaching this to students at your level, it's been considerably easier to start with the problem in one space dimension and time rather than starting in two dimensions. $\endgroup$
    – Brian Borchers
    Oct 9, 2011 at 15:22
  • $\begingroup$ "The connection between random walks, diffusion, and the heat equation is an amazing example of 'the unreasonable effectiveness of mathematics.'" Why do you say that? To me, it seems like those three subjects ought to be intimately related: both diffusion and heat transfer are accomplished, on the microscopic level, by randomly walking particles. However, I have no background in any of the three subjects---is there some subtlety that makes the connection more surprising than it appears at first glance? $\endgroup$
    – Vectornaut
    Oct 9, 2011 at 21:42
  • 1
    $\begingroup$ You're right of course that from a physical point of view this isn't too surprising, since heat diffusion is about random vibration at the molecular scale. However, if you start with the mathematical problem $u_{t}=u_{xx}$, it's quite surprising that the solution should have any connection to probability theory. Most of my students (mathematics majors in a senior modeling course) have limited physics backgrounds and are surprised by this. $\endgroup$
    – Brian Borchers
    Oct 9, 2011 at 22:21
  • 1
    $\begingroup$ Thank you for the enormous amount of info you've given me, it's going to be a huge amount of help since there is extremely little literature on the application of games and solutions to PDE's. From what I've been reading about the 1-D heat equation is that the Crank-Nicolson is essentially the best way of approximating it, in most of the books that I've found at my library they've introduced the finite difference method for it, and then basically introduce this new method that does not have stability problems. Unless I'm not understanding something, why wouldn't I just employ the other method? $\endgroup$
    – DaveNine
    Oct 10, 2011 at 0:50
  • 1
    $\begingroup$ Yes, Crank-Nicholson is unconditionally stable. The naive FTCS (forward differences in time, centered differences in space) scheme isn't stable unless you're careful about picking $\Delta x$ and $\Delta t$. If you just want to solve an equation, then by all means, use Crank-Nicholson, but if you want to understand what's going on, then the FTCS scheme is a good place to start. $\endgroup$
    – Brian Borchers
    Oct 10, 2011 at 1:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.