Dynamic Systems and Applications 15 (2006) 35-42

DISCRETE TWO DIMENSIONAL DIFFUSION PROBLEM ON A HALF PLANE

RICHARD AVERY^{1} AND GLENN BERMAN^{2}

College of Natural Sciences, Dakota State University, Madison, SD 57042 USA. 1E-mail: rich.avery@dsu.edu 2E-mail: glenn.berman@dsu.edu

Dedicated to John Baxley on the occasion of his retirement from Wake Forest University.

ABSTRACT. We find the solution of the partial difference equation,

Δ_{t}v(x, y, t) = −r∇_{x}v(x, y, t) + lΔ_{x}v(x, y, t) + uΔ_{y}v(x, y, t) − d∇_{y}v(x, y, t),

for any integer y and positive integers x and t, with initial condition v(x, y, 0) = f(x, y), and (absorbing) boundary condition v(0, y, t) = 0. This corresponds to a discrete two dimensional diffusion equation. The Green’s function will be determined using random walk techniques. AMS (MOS) Subject Classification. 39A12, 37H10.

1. PRELIMINARIES

Diffusion is a physical process and partial difference equations have been used with limiting processes to form partial differential equations that have provided successful models in the physical sciences. However, there are situations, as discussed by Mollison [10] and investigated by Durrett and Levin [6], where it is important to recognize the discrete steps and maintain a minimal stepsize. See Okubo [11] for a discussion of these issues as related to the biological and ecological sciences. Partial difference equations can be used to address such problems, with [7] offering mathematical biology examples. Some of these problems can be viewed as random walks [2, 11]. We will look for an analytic solution to discrete diffusion on the half plane. The derivation of the Green’s function, which will play a key role in the formulation, will require that the reader is familiar with basic combinatorial techniques related to random walks. Green’s functions for partial difference equations can be found in the literature. They have been studied by Van Der Pol [14], de Boor et al. [4] and Veit [13] among others. However their approach applies Fourier series arguments. For example, Van Der Pol found a formula for the diagonal values of the Green’s function but

Received September 30, 2004             1056-2176 $15.00 \begin{matrix}c \\ ◯ \end{matrix}Dynamic Publishers, Inc.

36 RICHARD AVERY AND GLENN BERMAN

then left an infinite number of calculations to find the value of the Green’s function elsewhere applying symmetry arguments. We will find the Green’s function for the discrete two dimensional diffusion problem on the half plane by considering a random walk. This will involve a straightforward derivation resulting in a known formula for the Green’s function. Avery and Berman [3] considered discrete diffusion on the plane without boundaries. The addition of one boundary will require a technique similar to a gamblers ruin problem applying the reflective principle for random walks. See [12] and the references contained therein for a thorough reference to the techniques and known results regarding random walks. The use of the Green’s function to solve discrete diffusion equations will require the reader has an understanding of Green’s functions and their applications as well as a basic understanding of discrete calculus. Books on the subject include Kelley and Peterson [9], Elaydi [8] and Agarwal [1].

2. INTRODUCTION TO A DISCRETE TWO DIMENSIONAL DIFFUSION EQUATION ON THE HALF PLANE

In this paper we will find the solution of the two dimensional discrete diffusion equation on a half plane given by,

v(x, y, t + 1) = v(x, y, t)
+ r[v(x − 1, y, t) − v(x, y, t)]
+ l[v(x + 1, y, t) − v(x, y, t)]
+ d[v(x, y + 1, t) − v(x, y, t)]
+ u[v(x, y − 1, t) − v(x, y, t)],

(for x a positive integer, y an integer and t a non-negative integer), with initial condition

v(x, y, 0) = f(x, y),

and (absorbing) boundary condition

v(0, y, t) = 0.

Thus by collecting terms, we want to find a solution of

v(x, y, t + 1) = s v(x, y, t) + r v(x − 1, y, t) + l v(x + 1, y, t)
+d v(x, y + 1, t) + u v(x, y − 1, t),

with initial condition,

v(x, y, 0) = f(x, y)

and (absorbing) boundary condition,

v(0, y, t) = 0,

DISCRETE TWO DIMENSIONAL DIFFUSION 37

where s = 1−r−l−d−u, r, l, d, u ∈ [0, 1]. The constants r (right), l (left), u (up) and d (down) correspond to the proportion of material (whatever v is modeling) moving from higher concentrations to lower concentrations (application of Fick’s Law) in the respective directions.

Note, if for each fixed pair of integers w and z, we can find a function P such that

P (x, y, w, z, t + 1) = s P (x, y, w, z, t)
+ r P (x − 1, y, w, z, t)
+ l P (x + 1, y, w, z, t)
+ d P (x, y + 1, w, z, t)
+ u P (x, y − 1, w, z, t),

for all positive integers x, integers y and all non-negative integers t that satisfy the initial condition

P (x, y, w, z, 0) = δ_{x,w}δ_{y,z},

and boundary condition

P (0, y, w, z, t) = 0,

then the (unique) solution of our discrete two dimensional diffusion equation on the half plane is

v(x, y, t) = ∑_{w=−∞}^{∞} ∑_{z=−∞}^{∞} P (x, y, w, z, t)f(w, z),

and the sum converges since there are only a finite number of terms on the right hand side that are not zero. We find the function P, which we will call the Green’s function for the discrete two dimensional diffusion problem on the half plane, that satisfies these conditions by considering random walks.

3. A RANDOM WALK

Define a random walk in the half plane as a movement in the two dimensional lattice

𝕎 × ℤ = {(x, y) : x is a non-negative integer and y is an integer}

with the properties that, the walker is absorbed on contact with the boundary (when x = 0), and regardless of the current location and time, the walker moves Right with probability r, moves Left with probability l, moves Up with probability u, moves Down with probability d and Stays with probability s (r + l + u + d + s = 1), and at each time interval, the walker must complete one of the five operations (which we will refer to as steps). Furthermore, for w and z fixed integers, we will assume that the walker is at (w, z) initially.

Let

P (x, y, w, z, t)

be the probability that the walker started at (w, z) initially and is at (x, y) after t steps (has traveled from (w, z) to (x, y) with no contact with the boundary). At time zero, we know the location of the walker. That is, at time zero, the walker is at (w, z) (where w and z are fixed integers) with probability 1 (zero everywhere else). Hence,

P (x, y, w, z, 0) = δ_{x,w}δ_{y,z}.

From conditional probability, the probability that the walker was at (w, z) initially and is at (x, y) (where x is a positive integer, not on the boundary) at time t + 1 corresponds to the sum,

P (x, y, w, z, t + 1) = s P (x, y, w, z, t) + r P (x − 1, y, w, z, t)
+ l P (x + 1, y, w, z, t) + d P (x, y + 1, w, z, t)
+ u P (x, y − 1, w, z, t),

since the walker must have been one step (Left, Right, Up, Down, or Stay) from (x, y) at time t, and the corresponding coefficients are the probabilities of such steps. Thus the solution of this random walk is the Green’s function for the two dimensional discrete diffusion problem on the half plane as previously remarked. In the following theorem, we find a formula for P when x ≥ w and y ≥ z. Note, if the walker touches the boundary then the walker is absorbed! Let

V (x, y, w, z, t, j, k) = ( \begin{matrix}t \\ |y − z| + k \end{matrix} ) ( \begin{matrix}t − (|y − z| + k) \\ k \end{matrix} )

S(x, y, w, z, t, j, k) = ( \begin{matrix}t − (|y − z| + 2k) \\ t − |x − w| − 2j − |y − z| − 2k \end{matrix} )

H(x, y, w, z, t, j, k) = \{ \begin{matrix}( \begin{matrix}|x − w| + 2j \\ j \end{matrix} ) − ( \begin{matrix}|x − w| + 2j \\ j − w \end{matrix} ) & if j ≥ w \\ ( \begin{matrix}|x − w| + 2j \\ j \end{matrix} ) & if j < w \end{matrix}

P_{1}(x, y, w, z, t, j, k) = r^{x−w+j}l^{j}u^{y−z+k}d^{k}s^{t−(x−w)−(y−z)−2k−2j}

and

R_{1}(x, y, w, z, t, j, k) = (V · S · H · P_{1})((x, y, w, z, t, j, k).

Theorem 3.1. If x ≥ w, y ≥ z, and t ≥ (x − w) + (y − z), then

P (x, y, w, z, t) =\begin{aligned}⌊ & \frac{t−(x−w)−(y−z)}{2} & ⌋ \\ & ∑ \\ & k=0 \end{aligned}\begin{aligned}⌊ & \frac{t−(x−w)−(y−z)−2k}{2} & ⌋ \\ & ∑ \\ & j=0 \end{aligned}R_{1}(x, y, w, z, t, j, k).

Proof. To start at (w, z) and end up at (x, y) after t steps, the walker must have taken at least x − w Rights and y − z Ups. Thus there are

t − (x − w) − (y − z)

additional steps that must be taken. The walker can take k additional Ups where k is between 0 and

⌊\frac{t − (x − w) − (y − z)}{2}⌋

since for each additional Up the walker must take a Down (additional Ups are paired with Downs) to end up with the vertical component y. This leaves

t − (x − w) − (y − z) − 2k

steps to be taken. With the

t − (x − w) − (y − z) − 2k

steps to be taken, the walker can take j additional Rights where j is between 0 and

⌊\frac{t − (x − w) − (y − z) − 2k}{2} ⌋,

since for each additional Right, the walker must take a Left (additional Rights are paired with Lefts) to end up with a horizontal component of x. This leaves

t − (x − w) − (y − z) − 2k − 2j

steps remaining which must all then be Stays.

If j ≥ w, then some of these walks will reach the boundary and the walker will be absorbed. We will count the number of walks that avoid the boundary by applying the Fundamental Theorem of Counting. First we will count the number of different walks (positions of the steps) with y −z +k Ups, k Downs and t−(y −z)−(x−w)−2j −2k Stays. There are

( \begin{matrix}t \\ y − z + k \end{matrix} ) ( \begin{matrix}t − (y − z + k) \\ k \end{matrix} ) ( \begin{matrix}t − (y − z + 2k) \\ t − (y − z) − 2j − (x − z) − 2k \end{matrix} )

40 RICHARD AVERY AND GLENN BERMAN

such walks which corresponds to (V · S)(x, y, w, z, t, j, k) (where we have used the V to refer to the vertical component of the walk and S for the stay component of the walk). The remaining positions are Rights and Lefts, but some of these walks will be absorbed and others will not be absorbed. By the reflective property (one dimensional, namely the horizontal component), it is known that the number of walks with initial point w > 0 and terminal point x > 0 that are absorbed in x − w + 2j steps (reach the boundary 0 at some step) with horizontal steps of positive one and negative one is the same as the number of walks from −w to x in x − w + 2j steps, since there is a bijection between these two types of walks. The bijection is defined by reflecting the steps leading up to the first point of intersection with the boundary, that is changing ups to downs and vice versa for the steps leading up to the initial intersection with the boundary. See [12] and the references contained therein for more details concerning the reflective principle. The number of walks from −w to x in x − w + 2j steps is given by

( \begin{matrix}x − w + 2j \\ j − w \end{matrix} ) ,

(where j − w corresponds to the number of rights in such a walk), and the total number of walks from w to x in x − w + 2j steps with j lefts is given by

( \begin{matrix}x − w + 2j \\ j \end{matrix} ) .

Therefore the number of walks from w to x in x − w + 2j with j lefts that are not absorbed is given by

( \begin{matrix}x − w + 2j \\ j \end{matrix} ) − ( \begin{matrix}x − w + 2j \\ j − w \end{matrix} ) .

Note, if j < w, then there are not enough steps in the horizontal direction for the walk to reach the boundary. Therefore the number of walks that avoid the boundary in x−w +2j steps, with initial point w and terminal point x, and with j lefts is given by H(x, y, w, z, t, j, k) (where we have used H to refer to the horizontal component of the walk).

Therefore, the number of different walks consisting of (y − z) + k Ups, k Downs, (x − w) + j Rights, j Lefts and t − (x − z) − (y − z) + 2k + 2j Stays that avoid the boundary is

(V · S · H)(x, y, w, z, t, j, k),

each with probability

P_{1}(x, y, w, z, t, j, k) = r^{x−w+k}l^{k}u^{y−z+j}d^{j}s^{t−(x−w)−(y−z)−2k−2j}.

Therefore,

P (x, y, w, z, t) =\begin{aligned}⌊ & \frac{t−(x−w)−(y−z)}{2} & ⌋ \\ & ∑ \\ & k=0 \end{aligned}\begin{aligned}⌊ & \frac{t−(x−w)−(y−z)−2k}{2} & ⌋ \\ & ∑ \\ & j=0 \end{aligned}R_{1}(x, y, w, z, t, j, k).

If t < (x − w) + (y − z), then P (x, y, w, z, t) = 0 since there are fewer steps taken, t, then the minimum number of required steps, (x − w) + (y − z), to get from the initial point (w, z) to the point (x, y). The remaining cases are proven in the same manner. Define the functions P_{2}, P_{3} and P_{4} by

P_{2}(x, y, w, z, t, j, k) = r^{j}l^{w−x+j}u^{y−z+k}d^{k}s^{t−(w−x)−(y−z)−2k−2j},
P_{3}(x, y, w, z, t, j, k) = r^{j}l^{w−x+j}u^{k}d^{z−y+k}s^{t−(w−x)−(z−y)−2k−2j},

and

P_{4}(x, y, w, z, t, j, k) = r^{x−w+j}l^{j}u^{k}d^{z−y+k}s^{t−(x−w)−(z−y)−2k−2j}.

Then define

R_{i}(x, y, w, z, t, j, k) = (V · S · H · P_{i})(x, y, w, z, t, j, k)

and

H_{i}(x, y, w, z, t) =\begin{aligned}⌊ & \frac{t−|x−w|−|y−z|}{2} & ⌋ \\ & ∑ \\ & k=0 \end{aligned}\begin{aligned}⌊ & \frac{t−|x−w|−|y−z|−2k}{2} & ⌋ \\ & ∑ \\ & j=0 \end{aligned}R_{i}(x, y, w, z, t, j, k)

for i = 1, 2, 3, 4. Therefore, for x, w, t nonnegative integers and y, z integers,

P (x, y, w, z, t) = \{ \begin{matrix}H_{1}(x, y, w, z, t) & if x ≥ w, y ≥ z and t ≥ |x − w| + |y − z| \\ H_{2}(x, y, w, z, t) & if w ≥ x, y ≥ z and t ≥ |x − w| + |y − z| \\ H_{3}(x, y, w, z, t) & if w ≥ x, z ≥ y and t ≥ |x − w| + |y − z| \\ H_{4}(x, y, w, z, t) & if x ≥ w, z ≥ y and t ≥ |x − w| + |y − z| \\ 0 & if t < |x − w| + |y − z|. \end{matrix}

REFERENCES

[1] R.P. Agarwal, Difference Equations and Inequalities, Marcel Dekker, Inc., New York, 1992.

[2] H. Berg, Random Walks in Biology, Princeton University Press, New Jersey, 1993.

[3] R.I. Avery and G. Berman, A note concerning a discrete two dimensional diffusion problem and random walks, International Journal of Pure and Applied Mathematics 14 (2004), 103-109.

[4] C. de Boor, K. Höllig and S. Riemenschneider, Fundamental solutions for multivariate difference equations, Amer. J. Math. 111 (1989), 403-415.

[5] R. Courant, K. Friedrichs and H. Lewy, On partial difference equations of mathematical physics, IBM J. Res. Develop. 11 (1967), 215-234.

[6] R. Durrett and S.A. Levin, The importance of being discrete (and spatial), Theor. Pop. Biol. 46 (1994), 363-394.

[7] L. Edelstein-Keshet, Mathematical Models in Biology, McGraw Hill, New York, 1988.

[8] S.N. Elaydi, An Introduction to Difference Equations, Springer-Verlag, New York, 1996.

[9] W. G. Kelley and A. C. Peterson, Difference Equations: An Introduction with Applications, Academic Press, San Diego, 2001 .

[10] D. Mollison, Spatial contact model for ecological and epidemic spread, J. Roy. Statist. Soc. B 39 (1977), 283-326.

[11] A. Okubo and S. A. Levin, Diffusion and Ecological Problems Modern Perspectives, Springer-Verlag, New York, 2001.

[12] K. H. Rosen, Handbook of Discrete and Combinatorial Mathematics, CRC Press, New York, 2000.

[13] J. Veit, Boundary value problems for partial difference equations, Multidimens. Systems Signal Process 7 (1996), 113-134.

[14] B. Van Der Pol, Probability and Related Topics in Physical Sciences, Appendix IV: The Finite Difference Analogy of the Periodic Wave Equation and the Potential Equation, Interscience Publishers,Inc., New York, 1959.