Archive

Archive for the ‘Differential Equations’ Category

On Patch by Patch Products, Part II - (RWLA,MCT,GT,AM Part IV)

October 15th, 2010 3 comments

Last time I talked about a concept I invented, and based on my studies on Markov chains.  They are, essentially, "continuous matrices" (a surface on  [0,1] \times [0,1] ) with the property that they add to 1 if we take the integral with respect to  x for any  y , in analogy to the requirement in the usual Markov matrix treatment.  I dubbed such "patches," and explained a way to construct them.  In my previous post, I began thinking that patches seem to be very special, in the sense that self patch powers can represent the state of a liquid in time, if we allow ourselves to be a little imaginative.  Let's say that we disturb a uniform distributed patch to an initial state, the initial state patch, like this:

 p(x,y) = 1 - cos(2 \pi x) cos(2 \pi y)

It is easy to see that if we integrate with respect to  x our result is 1, so that it is indeed a patch. (I also constructed this function by letting  f_1(x) = cos(2 \pi x), g_1(y) = cos(2 \pi y), f_2(x) = 1 and calculated that  g_2(y) = 1 using the technique I talked about here).

Let's say we have depressed the liquid at the four corners and center of the confined space (necessarily a cube of dimensions  1 \times 1 \times h ), essentially giving it energy. Next calculate the patch powers (as described in my previous posts).  Interestingly, if we map the patch powers of such liquid, they will converge to a steady state, just like Markov matrixes would:

 p(x,y) = 1 - cos(2 \pi x) cos(2 \pi y)

 p_2(x,y) = 1 + \frac{cos(2 \pi x) cos(2 \pi y)}{2}

 p_3(x,y) = 1 - \frac{cos(2 \pi x) cos(2 \pi y)}{4}

 p_4(x,y) = 1 + \frac{cos(2 \pi x) cos(2 \pi y)}{8}

 p_5(x,y) = 1 - \frac{cos(2 \pi x) cos(2 \pi y)}{16}

 p_6(x,y) = 1 + \frac{cos(2 \pi x) cos(2 \pi y)}{32}

The evolution in time of this particular patch is easy to guess (although I should, technically, prove this by induction... I do in my next post):

 p_t(x,y) = 1 - \frac{cos(2 \pi x) cos(2 \pi y)}{(-2)^{t-1}}

for  t \in \mathbb{Z^+} , and letting this parameter represent both time and the patch power.  Of course, if we integrate with respect to  x any of these, the result is 1, and so, they are, indeed, patches.

I would like to state in a different post the conditions in which a steady-state is achievable; my suspicion is that, in analogy to Markov chains, steady-state happens if the patch is non-zero for some power (and above) on  [0,1] \times [0,1] , a property that is called regularity within that context, and of course, I would like to be able to calculate the steady state as easily as it can be done with discrete Markov chains (I was afraid that, in this particular example, I wouldn't be able to achieve steady state because of the initial patch having zeroes at the corners and center).  It's pinned as one of my to-dos.  At any rate, the fact that there are patches that converge to a state (a 2D surface), and, specifically, that can converge to the uniform distribution surface, suggests that such systems, from the viewpoint of Physics, must dissipate energy and there is linked the concept of entropy.  Of course from a probabilistic point of view, entropy in this sense is non-existent; patches merely describe the probability of movement to another "position" on each  y fiber.

There are of course patches that do not converge to the uniform surface distribution, but to other types: in my previous post, the patch I constructed converged to a plane that is tilted in the unit cube.  I wonder if such cannot have a physical interpretation that relates it to gravity: the liquid experiences a uniform acceleration (gravity) normal to the (converging) plane, which of course says, from a physical interpretation, "the cube is tilted."  Again from the probabilistic point of view, the concept of gravity is an explanatory link to Physics, but the end-state arises without its action on the fluid at all!

There are fun topological considerations too: the fact that we can do this on the unit cube does not preclude us from doing it in, for example, a unit cylinder (a cup or mug!), provided we can find the appropriate retract-into-the-square function and vice-versa.  This I think might be very interesting to map movement in all kinds of containers.

I have already talked about a couple potential venues in Group Theory, which I really would also like to go into further at some point.

As in other posts, another possible area of investigation is the evolution of the surface in smaller bits of time. I was able to link, in previous Markov treatments, discrete representations of Markov chains to continuous time differential equations.  Here is where it would be immensely interesting to see if patches, under this light, do not converge to partial differential equation representations.  Which leads me to the last point, regarding Navier-Stokes turbulent flow (which I admit know very little about), and a potential link to its differential equation representation:

Here is why I think that turbulent flow can be explained by generalizing patches a little bit, to "megapatches" (essentially 3d-patches or tensors), since, now we can think not of a 2D surface converging, but a 3D one in time: a water sphere in space (I once saw a cool video on this and was left thoroughly fascinated) or a water balloon being poked could be understood this way, for example, so that the movement of water throughout the flexible container could be similarly traced (by mapping the probability of movement in the container)!  I need to flesh this out a little more, but I think it's also very interesting, potentially.

These studies make me ask myself, again: what is the relationship between stochastic processes and deterministic representations?  They seem to be too intimately linked to be considered separate.

On Patch by Patch Products - (RWLA,MCT,GT,AM Part III)

October 12th, 2010 No comments

In my previous post, I described the concept of a "patchix" and of a special kind, the "patch." I described how to multiply a continuous function on  [0,1] by a patch(ix). Today I want to talk about how to multiply a patch by a patch and certain properties of it.

In my description in my informal paper, I basically said that in order to (right) multiply a patchix by a patchix, say  p(x,y) with  q(x,y) , we would have to send  p(x,y) \rightsquigarrow p(1-y,t) and then integrate as:

 r(x,t) = \int_0^1 p(1-y,t) \cdot q(x,y) dy \rightsquigarrow r(x,y)

If the patchix is furthermore special, so that both  \int_0^1 q(x,y) dx = \int_0^1 p(x,y) dx = u(y) = 1 , the uniform distribution on [0,1] (so that  u of any fiber is 1), then  p(x,y) and  q(x,y) are "patches." I want to show that, when we "patchix multiply" two patches we obtain another one. Here's why: assume then  p(x,y) and  q(x,y) are "patches." Then the resultant  r(x,t) is a patch too if  \int_0^1 r(x,t) dx = u(t) = 1 . Thus:

 \int_0^1 r(x,t) dx = \int_0^1 \int_0^1 p(1-y,t) \cdot q(x,y) dy dx

If there is no issue with absolute convergence of the integrals (as there shouldn't be in a patch), by the Fubini theorem we can exchange the order of integration:

 \int_0^1 \int_0^1 p(1-y,t) \cdot q(x,y) dx dy = \int_0^1 p(1-y,t) \int_0^1 q(x,y) dx dy

The inner integral evaluates to  u(y) = 1 by hypothesis. Then we have  \int_0^1 p(1-y,t) dy = u(t) = 1 because the transformation  x \rightsquigarrow 1-y changes the orientation so that the direction of integrating to 1 now changes to be in the  y direction ( dx \rightsquigarrow -dy ). Nicely, we have just proven closure of patches.

Because this strongly suggests that patches may form a group (as may patchixes with other properties), I want to attempt to show associativity, identity and inverses of patches in my next post (and of other patchixes with particular properties).

For now, I'm a little more interested in solving a concrete example by calculating self-powers. In my last post, I constructed the following patch:

 p(x,y) = x^2 y^3 + x \left( 2 - \frac{2 y^3}{3} \right)

To calculate the second power, send  p(x,y) \rightsquigarrow p(1-y,t) . I get, in expanded form, from my calculator:

 p(1-y,t) = t^3 y^2 - \frac{4 t^3 y}{3} + \frac{t^3}{3} - 2y + 2

so that

 p_2(x,t) = \int_0^1 p(1-y,t) \cdot p(x,y) dy = \frac{29 x}{15} + \frac{t^3 x}{90} + \frac{x^2}{10} - \frac{t^3 x^2}{60}

Last, let's send  p_2(x,t) \rightsquigarrow p_2(x,y) = \frac{29 x}{15} + \frac{y^3 x}{90} + \frac{x^2}{10} - \frac{y^3 x^2}{60}

We can corroborate that this is a patch by integrating

 \int_0^1 p_2(x,y) dx = \int_0^1 \frac{29 x}{15} + \frac{y^3 x}{90} + \frac{x^2}{10} - \frac{y^3 x^2}{60} dx = 1 which is indeed the case.

To calculate the third power, we can:

 p_3(x,t) = \int_0^1 p(1-y,t) \cdot p_2(x,y) dy = \frac{1741 x}{900} - \frac{t^3 x}{5400} + \frac{59 x^2}{600} + \frac{t^3 x^2}{3600}

Then, send  p_3(x,t) \rightsquigarrow p_3(x,y) = \frac{1741 x}{900} - \frac{y^3 x}{5400} + \frac{59 x^2}{600} + \frac{y^3 x^2}{3600}

Again, we can corroborate that this is a patch by

 \int_0^1 p_2(x,y) dx = \int_0^1 \frac{1741 x}{900} - \frac{y^3 x}{5400} + \frac{59 x^2}{600} + \frac{y^3 x^2}{3600} dx = 1

which is the case.

Here's a countour 3D-plot of  p(x,y), p_2(x,y) \ldots p_7(x,y) : in other words, the 7-step time evolution of the patch (the "brane").  By looking at the plot, you can probably begin to tell where I'm trying to get at:  the patch evolution shows how a fluid could evolve in time (its movement, oscillation), provided the appropriate first-patch generator can be found for a particular movement.  The fact that, if patches mirror Markov "thinking", a patch that will eventually settle to its long-term stable distribution means that this (patch) treatment, when applied to the physical world, takes into account some sort of "entropy," or loss of energy of the system.  Also some sort of "viscosity," is my belief.  The patch evolution catches nicely and inherently all relevant physical properties.  I will continue to explore this in my next post, I think.

The above image has been scaled differently for the different functions so that they can be better seen as they converge.  In my next post, I would like to expound on the evolution of the following first-patch:

On Lanchester’s Differential Equations and WWII: Modeling the Iwo Jima Battle

August 18th, 2010 1 comment

Almost at the end of World War II, a battle to the death between US and Japanese forces took place off Japan in the island of Iwo Jima.  We can definitely apply a Lanchesterian analysis to this encounter; in fact, it has already been done by Martin Braun in Differential Equations and their Applications, 2nd ed. (New York: Springer and Verlag, 1975).  If  x represents the number of US soldiers and  y represents the number of Japanese troops, Braun estimates that  a = 0.05 and  b = 0.01 approximately.  Assuming then that the initial strength of the US forces was hovering around 54,000, and that of the Japanese was 21,500, we'd be interested in knowing the trajectory of the battle and see who wins.  I've used the method described in my previous post to obtain estimates for the proportion of  soldiers alive in  X = US and in  Y = Japan , namely the Markovization or discretization (or Eulerization) method, and this is what we come up with.  We assume the battle is fought to the death and there are no reinforcements from either side:

 L = \left[ \begin{array}{ccc} 1 - 0.05 \cdot \frac{p_{alive,y}}{p_{alive,x}} & 0 & 0.05 \cdot \frac{p_{alive,y}}{p_{alive,x}} \\ 0 & 1 - 0.01 \cdot \frac{p_{alive,x}}{p_{alive,y}} & 0.01 \cdot \frac{p_{alive,x}}{p_{alive,y}} \\ 0 & 0 & 1 \end{array} \right]

The attrition constants are within the range so that all entries are less than one as required by a Markov transition matrix provided the excess ratio of one army population to another is not too large (also, each row sums to 1).  The matrix is time-dependent, however, because each time the proportion of alives in any army changes according to the strength of the other army (proportional to both numerical superiority and technology, as can be seen in the matrix above, thus, from the Markov chain vantage point, the probability of death at each time step changes), as modeled by Lanchester's continuous differential equations.  Here are the proportion trajectories I came up with, computing at each time step the above matrix and pulling the original vector through:

Iwo Jima battle

It's pretty clear that, despite having the technology advantage, the Japanese lose because of numerical inferiority after about 59 time-steps.  The approximate proportion of US soldiers at the end of the battle is 0.35 (of the total soldier population), or about 26,276 soldiers, a HUGE decline from the initial 54,000 (roughly 0.72 of the total soldier population).  The Japanese army essentially obliterated half the soldier population of the US, a testament to their ferocity in battle.

My Calculus book (Deborah Hughes-Hallet, Andrew M. Gleason, et al., New York, John Wiley & Sons, Inc., 1994, p.551) suggests that the US in fact would have had 19,000 soldiers that could have stepped in as reinforcements: this does not matter really if the reinforcements come at the end of the battle, the battle has already been won with 54,000 soldiers, but it does alter the outcome significantly if they are added to the original soldiers at the beginning of battle (namely the US has 73,000 troops, or 0.78 of the total soldier population): the Japanese army would lose in roughly 34 time-steps (to the death), and the number of US soldiers left standing would be about 55,420, or 0.59 of the total soldier population: the Japanese obliterate only about 25% of the US troops.

In my next post, I want to discuss Dan's (from Giant Battling Robots) pdf document that he provided, essentially looking at a different stochastic model related to warfare and battle.  It's pretty neat, although it counts each potential outcome as a Markovian state (and each state is linked "downward" by a transition probability so that a given probability governs the death of one soldier in either army).  Thanks Dan!

On Stochastic Processes

August 11th, 2010 1 comment

Why can't I shake the feeling that a stochastic process really... isn't? In previous posts we have been able to frame a deterministic system in terms of its Markov transform matrix, and going backward really doesn't seem like a problem. So what's going on, I can't help but wonder?  Are deterministic systems a subclass of random processes? Are they isomorphic spaces, or convergent at the limit as we take smaller pieces of time?  Was Einstein right, that it all converges to a determined state, and "God does not roll dice?"  What do you think?

On Lanchester's Differential Equations and their Transform into a Markov Transition Matrix (or, the Markovization of the Lanchester Equations)

August 10th, 2010 7 comments

I have been very curious as to whether the Markovization of differential equations is applicable to all systems, linear or not.  In the case of the SIR differential equations, Markovization was possible even when the system is both non-linear and coupled.  I think that perhaps there is an algorithm to frame the differential equations thusly... I haven't fleshed it out completely (other than by using quite a bit of intuition, as in the SIR case).  Markovization, I think, is distinct from putting differential equations in state-space form; the vector pulled through the state-space matrix represents the trajectories of a function and its derivatives, not the trajectories of a set of functions related in that their sum is one: probabilities or proportions.  Who knows, though, a happy mix may be possible.

I was examining a Calculus book, specifically by Deborah Hughes-Hallet, Andrew M. Gleason, et al. (New York, John Wiley & Sons, Inc., 1994), and came across this very interesting problem that models how armies or soldiers fight it out... and tries to predict who wins.  I hope you don't judge: even after having read the most complicated books in mathematics, I honestly believe that revisiting more basic books can bring about insights that one didn't think of before.  Maybe even ground the complicated knowledge one acquired, or refine it.  Such has been my own experience... so I think it's a useful exercise, for all of those who have resisted "going back to the basics." If you are one, perhaps you are missing the opportunity to bridge the gaps you may (or not) still have!  :-\

The problem on page 550 says that, if  x represents the number of soldiers from army  X and  y represents the number of soldiers from army  Y , the rate at which soldiers in one army are injured or die can be thought of as proportional to the number of "firepower" the other army can concentrate on them.  The model was first thought by F.W. Lanchester:

 \frac{dx}{dt} = -ay

 \frac{dy}{dt} = -bx with  a, b > 0 .

In order to Markovize Lanchester's differential equations, we need to flesh out what the states are: clearly, you can be alive and belong to army  X , or army  Y , or be dead (from a different vantage point, we could have "Dead from  X " and "Dead from  Y " if we wanted to count each individually).  The Markov transition matrix should look something like this, then:

 L = \left[ \begin{array}{ccc} something & 0 & something \\ 0 & something & something \\ 0 & 0 & 1 \end{array} \right]

where  L_{1,1} represents the probability of being alive in army  X (if you are from army  X ) after a time step (or the proportion of alive soldiers in  X after a time step),  L_{1,2} represents the probability of "defecting" to army  Y if you are in army  X (I assume such doesn't happen),  L_{1,3} represents the probability of dying if you are in army  X .  Then  L_{2,1} represents the probability of defecting to army  X if you are in army  Y (I also assume this doesn't happen),  L_{2,2} represents the probability of being alive in army  Y , if you are from army  Y , and  L_{2,3} is the probability of dying if you are in army  Y .  The third row of  L simply represents the fact that one cannot come back from the dead once dead:  there are no zombies (such may be in fact possible in videogames, for example, hence why I make a point of saying this).

The next order of business is to note that the total population does not change (alives and deads).  Thus we would have that:

 p_{alive,x} = x/N

 p_{alive,y} = y/N , and

 p_{alive,x} + p_{alive,y} + p_{dead} = 1 .  Rewriting Lanchester's equations in terms of proportions, we would have that:

 \frac{d p_{alive,x}}{dt} = -a p_{alive,y}

 \frac{d p_{alive,y}}{dt} = -b p_{alive,x}

To be complete, we must model what the rate of change of the dead is, which we can figure out by differentiating in time the equation  p_{alive,x} + p_{alive,y} + p_{dead} = 1 .  In effect, what I'm saying is that, Lanchester's equations are incomplete - they are missing the key information that:

 \frac{d p_{dead}}{dt} = a p_{alive,y} + b p_{alive,x}

This equation basically states that the dead increases as the rate at which soldiers in army  X are put down and the rate at which soldiers in army  Y are put down.

Euler's method suggests that to write the approximation to these differential equations, we need think of the derivative not at the limit, but taking tiny time steps.  So in the following equation

 lim_{\Delta t \rightarrow \infty} \frac{\Delta p_{alive,x}}{\Delta t} = -a p_{alive,y}

let's forget about the limit for a second, and solve thus:

 \Delta p_{alive,x} \approx -a p_{alive,y} \Delta t

and

 p_{alive,x} (t+\Delta t) \approx p_{alive,x} (t) - a p_{alive,y} \Delta t .  Writing all differential equations thus:

 p_{alive,y} (t+\Delta t) \approx p_{alive,y} (t) -b p_{alive,x} \Delta t and

 p_{dead} (t+\Delta t) \approx p_{dead} (t) + a p_{alive,y} \Delta t + b p_{alive,x} \Delta t

Euler's method gives us just what we need for our transition matrix construct.  If the approximations are in fact equalities, from the point-of-view of Markov chain theory, the left-hand side is the next-step vector, and the right-hand side explains how this vector would be obtained by a transformation on the at-step vector.  In terms of Markov dynamics:

 \textbf{p(t +} \Delta t \textbf{)} = \textbf{p(t)} \cdot L

Playing a bit with the matrix  L , it should look like:

 L = \left[ \begin{array}{ccc} 1 - a \cdot \frac{p_{alive,y}}{p_{alive,x}} \Delta t & 0 & a \cdot \frac{p_{alive,y}}{p_{alive,x}} \Delta t \\ 0 & 1 - b \cdot \frac{p_{alive,x}}{p_{alive,y}} \Delta t & b \cdot \frac{p_{alive,x}}{p_{alive,y}} \Delta t \\ 0 & 0 & 1 \end{array} \right]

Letting  \Delta t be unity,

 \textbf{p(t +1)} = \textbf{p(t)} \cdot L

with

 L = \left[ \begin{array}{ccc} 1 - a \cdot \frac{p_{alive,y}}{p_{alive,x}} & 0 & a \cdot \frac{p_{alive,y}}{p_{alive,x}} \\ 0 & 1 - b \cdot \frac{p_{alive,x}}{p_{alive,y}} & b \cdot \frac{p_{alive,x}}{p_{alive,y}} \\ 0 & 0 & 1 \end{array} \right]

and, I think, we have successfully Markovized the differential equations, in effect discretizing them at unit time steps.  We should be cautious though, because now both  a, b have additional restrictions in order that the entries of  L remain below or equal to 1 (and specifically, the sum of each row must be equal to one).

Euler's method in effect is the link here between the continuous differential equations and the Markov transition matrix.  In the SIR discretization of my previous post, I went backwards, showing how we can write continuous differential equations from the Markov transition matrix.

Several interesting things to note about the matrix  L : the probability of death, if one is in army  X is proportional to the attrition  a and by how many soldiers army  Y exceeds  X at the time.  A similar argument works for the death probability of soldiers in  Y , with attrition  b and excedent of  X to  Y .

As with the SIR equations, since  L is really changing every time step, it is  L(t) .  So, from initial conditions, the amount of soldiers alive in army  X , army  Y , and dead at time step  n can be calculated using the discretized matrix by pulling the original vector through, as:

 \textbf{p(t +} n \Delta t \textbf{)} = \textbf{p(t)} \cdot L(t) \cdot L(t + \Delta t) \cdot \ldots \cdot L(t + (n-1) \Delta t)

In my next post, I want to model, as in the Calculus book I mentioned, the Iwo Jima encounter during World War II, the fight between Japan and the US, and solving the trajectory numerically using the discretization above.

An additional note, from examining our assumptions of matrix  L , we realize now simple ways in which we could extend Lanchester's differential equations, by filling in "probabilities that a soldier will defect to the other army."  We have indeed now enriched the model in the sense that we can now take into account other complicated dynamics (the least of which is the "creation of zombies").  I think this is very useful in any model, because it allows us to contemplate transitions into states we wouldn't have considered otherwise, and, more powerfully, allows us to transform our mindset to the realm of differential equations, where we can have DE-related insights, and back again, where we can have Markovian insights.