Use of games to approximate solutions to Partial Differential Equations - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T23:10:59Z http://mathoverflow.net/feeds/question/77588 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/77588/use-of-games-to-approximate-solutions-to-partial-differential-equations Use of games to approximate solutions to Partial Differential Equations Davenine 2011-10-09T07:26:38Z 2011-10-09T15:13:12Z <p>Hi there,</p> <p>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.</p> <p>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.</p> <p>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:</p> <ol> <li><p>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.</p></li> <li><p>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.</p></li> <li><p>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)</p></li> </ol> <p>Google books has a slice of the chapter online, <a href="http://books.google.com/books?id=DLUYeSb49eAC&amp;pg=PA347&amp;lpg=PA347&amp;dq=%22tour+du+wino%22&amp;source=bl&amp;ots=vmsz2z6uAP&amp;sig=rZiqwWJ8ESgokmYmBga8qtGVG8U&amp;hl=en&amp;ei=dEaOTp26EeTKsQLg1LymAQ&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=4&amp;ved=0CDIQ6AEwAw#v=onepage&amp;q=%22tour%20du%20wino%22&amp;f=false" rel="nofollow">http://books.google.com/books?id=DLUYeSb49eAC&amp;pg=PA347&amp;lpg=PA347&amp;dq=%22tour+du+wino%22&amp;source=bl&amp;ots=vmsz2z6uAP&amp;sig=rZiqwWJ8ESgokmYmBga8qtGVG8U&amp;hl=en&amp;ei=dEaOTp26EeTKsQLg1LymAQ&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=4&amp;ved=0CDIQ6AEwAw#v=onepage&amp;q=%22tour%20du%20wino%22&amp;f=false</a></p> <p>I wish there was someone like Erdos who could just have insane memory to remember past papers on a topic.</p> http://mathoverflow.net/questions/77588/use-of-games-to-approximate-solutions-to-partial-differential-equations/77607#77607 Answer by Brian Borchers for Use of games to approximate solutions to Partial Differential Equations Brian Borchers 2011-10-09T15:12:53Z 2011-10-09T15:12:53Z <p>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. </p> <p>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. </p> <p>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. </p> <p>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. </p> <p>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. </p> <p>To answer your specific questions:</p> <ol> <li><p>You don't want self avoiding random walks.</p></li> <li><p>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 additions and now has new coauthors...) might be suitable for you. Methods for nonlinear PDE's are a more advanced topic.</p></li> <li><p>As I've suggested above, you'll want to use an environment with built in tools for random number generation and plotting. </p></li> </ol>