# Using games to approximate solutions to PDE's

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.

To give an example of what the game is, start with an $n \times m$ lattice, then pick an interior point and run a Monte Carlo simulation that computes random walks from any point $i_{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 boundary/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 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.

Thanks for any advice/help you can give me, I'm also thinking about posting my question to MathOverflow, which is a pretty dang similar site to this.

-D.Sacco

-
"I'm also thinking about posting my question to MathOverflow" - MO is for research-level math, so don't... – J. M. Oct 7 '11 at 0:49
I mean..given the fact that I have yet to see anyone do research in this area..why not? I've pretty much exhausted the resources of my school, so I figured it'd be a good idea to reach out to the community... – DaveNine Oct 7 '11 at 1:14
...at least, not yet. A lot of people here are members of both, and it isn't kosher to duplicate effort. Maybe you can after a few days of not getting answers here... – J. M. Oct 7 '11 at 1:17

This question has been asked and answered on MathOverflow. I have replicated the accepted answer by Brian Borchers below.

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