Method of Characteristics or How I Started Worrying and Loathe Quasi-linear PDEs: Part 1

I emailed my adviser…at least I think she’s my adviser. I had an adviser, but was later given her as an adviser, then she went on sabbatical and was reassigned to my original adviser, but now he’s on sabbatical, so I’m not 100% sure. Regardless, she’s someone of mathematical authority who tells me what I do and I subsequently obey.

After failing my qual on financial mathematics I decided to change some things in my life. One of them is actually being proactive and begin preparing for my qual on Partial Differntial Equations (PDEs) in four months.Her advice was “be sure to solve any problem in Applied Partial Differential Equations” by Ockendon, Howison, Lacey, and Movchan. Which is doable if I can solve two a day. Well, that was one piece, the others were take different quals.

Quasi-linear PDEs are the second worst type of PDEs after and nonlinear  PDEs. Or to phrase it positively, the third best type of PDEs after linear PDEs and semi-linear PDEs.

Life is already complex, so we restrict ourselves to a function u of two variables x,y. Anymore variables doesn’t provide additional insight, any less and it is not a PDE and this isn’t a post about how I loathe Ordinary Differential Equations (ODEs).

Suppose our function u(x,y) satisfies the PDE a(x,y,u)\frac{\partial u}{\partial x}+b(x,y,u)\frac{\partial u}{\partial y}=c(x,y,u) . We can graph u and get a surface laying in three dimensional space. We can rewrite our PDE as an inner product of two vectors (a,b,c) \cdot (\frac{\partial u}{\partial x},\frac{\partial u}{\partial y},-1) =0.

(\frac{\partial u}{\partial x},\frac{\partial u}{\partial y},-1)  is the normal vector to the surface u(x,y), which means (a,b,c) is in the tangent plane of u(x,y) at any specific point.

Our plan of attack is introducing a “time” parameter to construct a curve (x(t),y(t),u(t)) that will satisfy our PDE and consequently trace a path on the solution surface of u. This approach allows us to convert our PDE into a system of ODEs, which makes life simpler.

Thus we need to solve \frac{dx}{dt}=a(x(t),y(t),u(t)), \frac{dy}{dt}=b(x(t),y(t),u(t)), \frac{du}{dt}=c(x(t),y(t),u(t)) . We can’t fully solve a system of ODEs without specifying initial conditions or starting point. As we change the initial conditions we produce different curves. We add a second parameter to vary our starting points so we have a family of curves that when collected produces the two-dimensional surface of u. So at time t=0 we let x(0)=x_0(s),y(0)=y_0(s),u(0)=u_0(s). Our choice of x_0(s),y_0(s),u_0(s) will be determined by the boundary/initial condition of our original PDE.

Ockendon, Howison, Lacey, and Movchan’s give a cute problem. They try to model the process of proof-reading a textbook. They construct a family of functions p_n(t) which represent the probability after time t spent proof-reading, there are still n errors in the draft. Then they construct the function p(x,t) = \sum_{n=0}^\infty p_n(t)x^n , and the resulting generating function satisfies the PDE \frac{\partial p}{\partial t}+\mu(x-1)\frac{\partial p}{\partial x}=0. We now need to set an initial or boundary condition. If the book contains N errors, they set the initial condition p(x,0)=x^N where x is between 0 and 1.

If you’re having difficulties interpretation is confusing, it’s okay. I actually emailed Lacey trying to understand the intuition of x and he replied the important part are the family of functions p_n(t), and the generating function p(x,t) is actually obscure. Besides, this isn’t a post about quantifying the editorial process, but about how to solve a certain class of PDEs.

We’ve already introduced a lot, and now have used t in two completely different ways. So let’s rewrite their example PDE as \mu(x-1)\frac{\partial u}{\partial x}+\frac{\partial u}{\partial y} = 0 to be consistent with the notation in the exposition. This is actually a pleasant introduction to the method of characteristics. This PDE is actually not just semi-linear but entirely linear (it’d be strictly semi-linear if the right-hand side was a function c(x,y,u)  instead of 0 (and then in the case c(x,y,u)=g(x,y)u+h(x,y) we would then again get a linear PDE)), which is a nicer class to deal with than quasi-linear PDEs, and nonlinear PDEs are just big “fuck you”s. Our system of ODEs are \frac{dx}{dt}=\mu(x-1),\frac{dy}{dt}=1,\frac{du}{dt}=0. Our initial condition u(x,0)=x^N hints that are initial conditions should probably be x(0)=x_0(s)=s,y(0)=y_0(s)=0,u(0)=u_0(s)=u(x_0(s),y_0(s))=s^N. I’m not going to do all the algebra for you.

Let’s solve. \frac{dy}{dt}=1, so y(t)=t+d_y(s) (our constant of integration is actually a function of s since our curve depends on the value of starting point parameter s), and y(0)=d_y(s), since y(0)=y_0(s)=0 we have y(t)=t. \frac{du}{dt}=0, u(t)=d_u(s), since u(0)=u_0(s)=s^N we have u(t)=s^N. Now for the non-trivial ODE. \frac{dx}{dt}=\mu(x-1), or \frac{dx}{x-1}=\mu dt. Thus \ln |x-1| = \mu t+ d_x(s). By assumption x is between 0 and 1, so |x-1| = 1-x (I originally skipped this nuance and got the completely wrong answer), hence 1-x(t) = e^{d_x(s)}e^{\mu t}. Plugging in t=0 we have 1-s=e^{d_x(s)}. Therefore 1-x(t)=(1-s)e^{\mu t}. I’m not going to do all the algebra for you.

Sometimes life isn’t simple and we can’t solve for s and t explicitly in terms of x and y, and we just have to plot the characteristic lines but thankfully we can arrive at an explicit solution. We have t=y and s=1+(x-1)e^{-\mu t}, and thus u(x,y)=u(x(t),y(t))=u(t)=(1+(x-1)e^{-\mu y})^N. I’m not going to do all the algebra for you.

Part 2 will cover a quasi-linear PDE with an explicit solution, while Part 3 will cover a quasi-linear PDE with a non-explicit solution expressed parametrically.

As always, all corrections and suggestions are welcomed.

EDITED: Rephrased a paragraph at the suggestion of Andrew Lacey.

How to make coffee

I don’t like coffee, except for one key exception. I love Turkish (armenian, romanian, bulgarian, greek, and basically all former provinces ruled by the Ottoman empire). It might be the greatest Ottoman contribution to the modern rule–considering their worst contribution was the Armenian genocide, getting coffee right is the least they could do.

First, you need a cevze (μπρίκι, ѓезве, jazva, džezva, джезве, τζιζβές, פינג’אן‎‎, xhezve, rakwa, Zezwa, kanaka, ghallāye, турка, ibric, or ibrik–which is one of the few Romanian words I can think as adopted to the English).

Preparing it is dead simple. Add water to your cevze. And unfiltered ground to your cevze, wait for it boil, stir so it reduces. Repeat three times.  Serve.

That’s it, no coffee maker, no filters, no weirdly expensive espresso machines. Just a copper pot, and a few spoonfuls of grounds.

As you get to the end, the grounds sink to the bottom. 1) grit builds character, and 2) if you have a gypsy on hand they can divine your future based on the dried grounds.

It’s dead simple, it’s delicious, it puts hair on your chest.

That’s how I make coffee. If I’m forced to drink coffee at a restaurant then I order a double espresso. Because that’s closest I can find, and even then espresso can’t grow hair on your chest. There’s no sludge to toughen you up.

Also, it’s obligatory to smoke while drinking Turkish coffee.

It’s the only coffee worthwhile.

 

Let’s integrate slash do probability the 20th century way! Part 1.

Pre(r)amble

After have-a-dozen blog posts that went nowhere, which is something considering the drivel I have posted, I have something!

In a month and a half, I take my prelim exam in financial mathematics. For the more finance leaning part I’ve been reviewing Shreve’s Stochastic Calculus for Finance series. For the heavier math part I’ve been reviewing Øksendal’s Stochastic Differential Equations. Part of that prep has been doing as many exercises I can.

I’m going to present one of those exercises along with some requisite background. The requisites will be presented in a fairly glossy manner if only because you can (and people do) devote an entire class(es) to this subject.

Warning. Math involved. I’m trying to write as simply as possible without breaking down every single definition, so some mathematical maturity is required. But if something is still unclear, then in all likelihood I’ve done goofed and you should correct me (grammar and spelling too please!).

Probability

Probability is strange. Or really, the discourse and history of probability is strange. To see how strange, just look at one of the few paradoxes attributed to a Bertrand who was not Russell. Please, read it. It’s disturbing. The same problem (what percentage of darts will land in a small circle in the middle), solved three different ways, producing three different results. That’s unsettling.

If you hang around social/medical scientists or statisticians, after three drinks you’ll be sucked into a debate between the frequentism and bayesianism. This is not intellectual masturbation. It’s interesting if you have my perverse tastes and it has a major impact on academic publishing.

But these are all beyond the scope of what will already be a lengthy conversation.

At the end of the post, we should be able to define a random variable in a rigorous factor; one where we can start actually doing probability.

We don’t need to pick a side or argue. We rise above. Enter Kolmogorov. He defines a probability space as having three components and denoted by the triple (\Omega,\mathcal{F},\mathbb{P}).

\Omega is simply a set of objects called the sample space. To be concrete if we wanted to talking about throwing a pair of dice throws, then \Omega_1 = \{(1,1),(1,2),(1,3),\ldots,(5,5),(5,6),(6,6)\}; i.e., \Omega_1 is the set of all possible dice throws. Or if we were talking about infinite series of coin tosses then \Omega_2=\{x_1 x_2 x_3 \cdots\; x_i \in \{H,T\}\} . Thus the sequence of all heads HHHH\cdots is in \Omega_2 , as is the sequence of alternating heads and tails, HTHTHTHT\cdots , is also in \Omega_2 . As is the sequence where the n-th entry is heads if n is prime and tails others. We can also have a more mundane space like \Omega_3 =\mathbb{R}.

\mathcal{F} is called a \sigma-algebra over \Omega. That is, \mathbb{F} is family of subsets of \Omega; i.e., if A \in \mathcal{F} then A \subseteq \Omega . It’s not very difficult to be a \sigma-algebra,  but to be one \mathbb{F} has to have certain properties. (1) \emptyset \in \mathbb{F}, (2) \Omega \in \mathcal{F}, (3) if E \in \mathcal{F} then E^c \in \mathcal{F}., and (4) if A_1,A_2,A_3,\ldots \in \mathcal{F} then \cup_{i =1}^\infty A_i \in \mathbb{F} . We call an element A in \mathcal{F} an event. We should also note there is no requirement that any subset of \Omega is an event.

Harkening back to our previously defined sample spaces, \{(i,j) \in \Omega_1 \}; i+j=7 \} is an event in \Omega_1; i.e, the event where the dice sum to 7. And \{ Hx_2x_3x_4; x_i \in \{H,T\}\} is the set of all sequences where the first toss comes up heads, which is an event in \Omega_2.

If we have \Omega  = \mathbb{R} then we usually consider the Borel \sigma-algebra, which we construct by saying we want all the open sets of \mathbb{R} to be in \mathcal{F} (and consequently all closed sets are also in \mathcal{F}), along with all unions compliments, etc. We usually denote the Borel \sigma-algebra by \mathcal{B}. The way we construct the \mathcal{B}, it is the “smallest” \sigma-algebra that contains all the open sets of \mathbb{R}. Note, we can construct a subset A of the real numbers that is not in \mathcal{B}. So there are subsets of \mathbb{R} that are not events. We can construct them, but usually they’re so odd that generally if you’re think of a subset of the reals, what’s in your head is also in \mathcal{B}. We will talk more about \mathcal{B} when we actually get to  random variables.

Now \mathbb{P} is a function from \mathcal{F} to the interval [0,1]. For each event A, \mathbb{P}(E) assigns a value between 0 and 1. In addition, \mathbb{P} must satisfy three properties: \mathbb{P}(\emptyset)=0, \mathbb{P}(\Omega)=1, and if A_1,A_2,\ldots are mutually disjoint (A_i \cap A_j = \emptyset when i \neq j), then \mathbb{P}(\cup_{i=1}^\infty A_i)= \sum_{i=1}^\infty \mathbb{P}(A_i). This is an intuitive set of requirements: the probability of nothing happening is 0, the probability of something happen is 1, and the probability of a collection of disjoint events is the sum of the probability of each event.

Going back to our coin toss example, (\Omega_2), it makes sense that the we can assign the probability of the event where the first toss is heads is 1/2 and the probability of the event of all tosses where the first is tails is also 1/2.  We can also assign the probably of the event where the sequences start HH, HT, TH, and TT as 1/4. Where the first three tosses are HHH,HHT,HTH,HTT,THH,THT,TTH, and TTT is 1/8, and so on and so forth. By this train of assignments, it’s not hard to show \mathbb{P} ( \{HHHHHHH \cdots \})=0. So there are non-empty events that have probability (or measure if we get ahead of ourselves) of 0.

This is technical, but it sidesteps a lot of non-technical arguments. What’s the probability of something happening? It’s simply the number which \mathbb{P} assigns to an event A \in \mathcal{F}. It’s boring, but we can work with it, and not have to talk about the frequency of an infinite number of events, estimates and beliefs, and it even solves the above linked paradox. In all three cases, the set of events is different, so of course there should be different answers. The downside is we have to choose what we call events and choose the probabilities assigned to them. There’s no reason to think our choice and assignments are a natural or even appropriate. Kolmogorov doesn’t debate, he just calculates numbers and pushes symbols. He’s dull like that.

Finally,  we can define a random variable. It’s simply a function X from our sample space \Omega to the real numbers \mathbb{R}. We can actually be more general and say X:\Omega \to \mathbb{R}^n but we won’t need to think about multiple dimensions for our purposes. We also need X to be \mathcal{F}-measurable. That means if we take a set B from the our Borel \sigma-algebra \mathcal{B}, then the set \{ \omega \in \Omega: X(\omega) \in B\} is an element of \mathcal{F}. Or more succinctly \{X^{-1}(B) \} \in \mathcal{F} for all Borel sets B \in \mathcal{B}

Next for Me

Now we know the modern formulation of probability, and have defined random variables in a way that avoids any pitfalls. In the next post we will show how to basic things like to the expected value of a continuous random variable (I don’t care about discrete random variables because of a nifty theorem I’ll talk about in the next post). To do this, we will introduce Lebesgue integration, which is an extension to the integration you learned in high school. To justify this complexity we will have to see where the integration taught at the high school/undergraduate level, Riemann–Stieltjes and Darboux integration, breaks down.

Next for You

I don’t know. It’s Friday. Maybe grab a drink. See some shitty pop-punk band. Do key bumps in the restroom until you get kicked out. Yell, “Well fuck this place. I don’t even want to be hear.” Go home. Netflix. More blow. Complain about the plot holes in The Flash to everyone around the mirrored table. Gum the leftovers your amateur friend couldn’t snort off the mirror. It’s a wide open world.

Postscript

As always, corrections and suggestions are appreciated. And as always “Max, stop being a [racist/sexist/homophobic] epithet,” is not a useful comment or suggestion.
Cheers,
-M

They Come Down

I only sleep sitting up. Beds are foreign. Remote. There’s a long stretch between me and any bed. Both forwards and backwards. And sideways, I’m not there yet to have a bed. There’s still nineteen years for me to cause trouble before I have to worry about crossing myself. Then I suppose I have to be careful. but how careful do I have to be? For all her faults my mother was still leagues above cavorting with the likes of me. My life was boring before it was awful. This is boring too. It’s not fair for something to be terrible and boring.

If I contradict myself it’s because I contain multitudes. Plus I’m high and time is weird.

I don’t even think I have to leave the city. The closest I’d ever to see of myself is seeing some kid hurried along past the beggarman. What can I do? The classic schemes won’t pan out. I won’t have a SSN or birth certificate. My ID is real. The UV activated holographic watermarks shimmer as they should. If I lick my thumb and press it against the microarray strip a bioluminescent green glows in approval. My hair’s all different and I’ve lost weight, but a scan of the QR2-codes written in micro will show my prints and retina match. Besides, even if I could get a bank account, the stock market is a long game as is compound interest and my needs are in the now.

I should walk into the Soviet embassy (they must at least have a consulate here) hand the plastic over, explain what it does (god knows I couldn’t tell them how it works), and ask for a dascha with a maid and one of those masseuses who work topless to come by each week. Or at least like a grand a week. Enough to keep on keepin’ on, but not too much to start attracting attention.  That racket will could until the wall comes down, or I could get thrown into some midwest gulag for being a degenerate in the new SSR of the old US of A.

I rouse and slam the back of my head against the wall. My eyes glance left and my head follows. I stare at the window frame. There’s no window of course. We broke it on the way in, and people don’t really bother draping squats. Black plastic is stretched over and bound with duct tape. There must be a wind blowing because our garbage bag cum window rustles. I don’t know what time it is (only that it’s not mine), but I hope it’s daylight. I always liked daylight. Even though I wasn’t an outdoorsy kid and kept odd hours.

I hope it’s day. I’d like to think there’s kids riding bikes and playing, and doing all the kind of shit we never really did but say we did to guilt the present with an idyllic past. I stare at the plastic and try to conjure an acceptable reality to lie beyond it. I remember seeing blackness though a frame before. It rippled like water. My worldline passes through it.

Review: Virginia

Last Friday I played Virginia by 505 Games. It came to my attention after reading Polygon’s glowing review. I can’t say I’m an extraordinarily busy man, I work part time, I go to school part time, I have a girlfriend part time. But it adds up and these days I generally either play smaller indie games or something that’s easy to pick up and play if only for a few minutes like Overwatch.*

Asides from the occasional triple-A title (Uncharted, Mirror’s Edge and Deus Ex being the most recent ones), I’m generally the pretentious fuck that raves about the indie art games that make Kotaku wet and myself insufferable at parties. So Virginia seemed made for me. But I walked away extremely disappointed.

It’s barely a game; extremely linear, nothing to explore, no choices to make, an entirely on-rails experience; minimalist to a fault. The story itself is fine. You play rookie FBI agent Anne Tarver. Partnered with agent Maria Halepern, you’re tasked with solving the disappearance of a young boy in the titular state. Complicating matters, you’re also tasked to spy on your partner for an Internal Affairs investigation on her. That’s the setup, but as any other review or article on Virginia mentions currents run deeper than that. Comparisons to the X-files, Outer Limits, and Twin Peaks have littered the pixels spilled on Virginia.

Virginia is not paced like most games. Segmented into thirty-odd “scenes” most transitions Jump cuts, flash forwards, symbolic callbacks, and well-crafted montages. Virginia as a story is edited well. I would also even say it’s well-written. Though there is no dialogue, there’s an interesting story, nice character development and even some tender moments of nuanced emotion. But there’s no game there. I feel like it was never meant to be a game, but for economic and political reasons the only way this story could come to market is as an indie game.  It would even be better as a movie/short if only because players make terrible cameramen.

But the Virginia we were given is a game, and as a game it disappoints. Linearity can work well. You may sacrifice the agency of the player, but you don’t have the strange divorce between the character you play and the character as presented by the story. The polar opposite of this is how about every Grand Theft Auto protagonist is an anti-hero in every cutscene, and history’s greatest monster when control is given back to the player. But you need to give a player something to actually do. And asides from collecting a handful of optional trinkets that you sometimes see in later scenes (maybe, and only as decoration), there’s nothing but “press A to continue”.

Gone Home and Firewatch are essentially very linear games with very little to do, and they’re both amazing. Both seem like open worlds. But between finding the various keys you need to open up more doors in Gone Home‘s mansion, and hiking equipment you accumulate in Firewatch, there is a strict path of progression laid out by the developers.

There’s not a lot there in Gone Home, but the little there is fantastic. Explore a new room, get a little more insight of the family–your family–that lives there, and come across a series of notes, letters and diary entries. But you find them. In Virginia a man hands you a dossier, in Gone Home you find your sister’s dark room or read the concert fliers in her room. It may not seem like much a difference, but the mystery and resolution of Gone Home is mine, Virginia’s isn’t.

It feels slightly mean to then compare it to Firewatch if only the scope and ambition of Firewatch is so much larger. I was actually mulling about bringing in Life is Strange into the conversation but that would be too unfair. Disregard Firewatch’s technical superiority. Stripped down, you walk around, there’s a mystery, you find clues, but the interactive dialogue system elevates Firewatch to a game we’ll be talking about for years. Not much concretely changes in gameplay or outcome, but you create an honest-to-god relationship between two characters.

Firewatch and Gone Home‘s use the interactivity of video games to accomplish something, and Virginia ignores that capability. I can’t recommend anyone to play Virginia, but if you were interested, then watch a playthrough online. You’ll have the same experience.
*Though Overwatch is easy to play in the sense that I can invest time in 15 minute intervals, not easy in the sense that I’m good in anyway. There are twenty-two characters in Overwatch and I’m terrible at all of them. I’m kind of proud in a perverse way.

PSA: Allow me to re-introduce myself

I’ve decided to write (again). I’ve made attempts to blog in the past, but it always died off due to time constraints and not really having too much to say. But I have more time now, and after tweeting, making dumb facebook posts, stupid reddit comments, and horrendous code, I realize it doesn’t matter that I have nothing of substance to say. So I’ve come to pollute yet another portion of the Internet.

There’s still a lot to do: travel snippets, technical posts, settling on a proper theme, a proper contact page, networking, understanding the difference between a widget and a gizmo, etc. But for the first time in a few years I feel I have a lifestyle which will allow me to do these things. The last time I had such an ability was in my late-teens/early-twenties and to be honest most of my posts would have been about many bottles of Two-Buck-Chuck can one safely drink while popping Vicodin like Pez (The answer is between 0 and 0.1, but I only learned that after 4).

So welcome to my corner of the Internet. It’s safer here.

PS: I also need to redirect max.baroi.com to go to this site. But until then, please don’t click the link I conveniently provided.