'Grid Theory' ?

If the averages dilute like you say, they will, in the end, settle the entire grid to the same value. This is because any disparity will trend the local surroundings towards equilibrium, and as you repeat, in the end, you'll go all the way out to all connected cells.

What you describe is an application of discrete mathematics; you can look into the fields of (2D) signal processing and graph theory for examples and theory.

There are sea, weather, and other cell based simulations that work like you say, except they add inertia, dampening and sometimes chaotic stimuli to make it more interesting. You'll typically get modes in the system that resonate. This is often used for simulating water surfaces, for example.

Hmm...not totally sure what you mean, but if I had to do something like this(oh the horror!), I would probably have two grids(OldPollution,NewPollution), and an averages grid, and when averaging the values, it would check if the New Average is the same as the Old Average for a tile. If it's different, then it enters another recursive check for all the tiles beside it.

Perhaps simple 2D convolution will work for you. Convolution is basicly operation which takes surrounding tiles (at least in your case) and weights them to get the new value for current tile. Then it moves to next tile and does the exact same thing. Some ASCII:

00100
01210
12421
01210
00100

The numbers represerent the weights, you probably want them to be percentage so that they sum up to one. That way your pollution does not increase or decrease, it just spreads. Or if you wan't your pollution to dissappear in a while then make the sum below one. The tile under weight four is your current tile. Now you just multiply every tiles pollution with its corresponding weight, sum them up and replace the current tiles pollution with that sum.

If your tiles would be pixels this operations would be very very similar to the blur operation you find in many photo editors.

You need some kind of buffering though, because you don't wan't to mix the old values and new values when processing with convolution.

Here's a link which show some code implementing convolution (also called filtering ) with examples of blur and emboss etc: 2D Filtering

You could actually use the texture filtering facilities of OpenGL and perhaps DirectX for this too to speed up your processing if the amount of tiles is huge.

Look up cellular automata