12
$\begingroup$

Way back when, I took a course in stochastic processes in college. I remember being frustrated by the plethora of abstract proofs without much in the way of how to use them to get actual results. It seems that every theorem in intro stoch. processes is about when something is a martingale (super/sub) under various operations OR if a particular stopping time is finite.

My difficulty was always translating these theorems to concrete results. Calculating actual hitting time probabilities, for example, always seemed to reduce to a large (or possibly infinite) number of conditional probably statements to calculate. The actual answers always involved just a few elegant lines, so I knew I was missing something.

My questions as follows:

  1. What types of stochastic processes are even solvable in closed from (i.e., when do you have to use a computer?...if that's easier to answer). I think Martingales are, but how general is that?
  2. For martingales, should I approach them indirectly, by setting up some sort of recursive relation or a relation that directly uses the quantity I want (E.g., $P(X_{t \wedge \tau} = x))$, as opposed to trying to directly derive the answer?
  3. For sub/super Martingales, is the strategy to reduce them to a martingale (for example, via Doob decomposition $X=M+A$ and then correcting the $A$ term to make it a martingale) and then apply martingale strategy above?

I think that was my major stumbling point back in college...I had taken engineering calculus and mathematical statistics, but I felt it didn't equip me with the correct mindset for stoch. processes.

Could someone comment on my above three points (are they generally correct?) and/or offer strategies for working with martingales to get concrete results (i.e., to calculate actual numbers?)

$\endgroup$
12
+100
$\begingroup$

Let me answer questions 2) and 3) before dealing with 1).

For second question: Martingales are tools which we can use to reduce complicated computations (example computing conditional probabilities), into appealing to a plethora of results about Martingales which you learnt for example in Stochastic process courses. In the research world, probabilists try to understand a problem into the language of some stochastic process, and if there is a martingale hidden in the process, then it hugely simplifies the problem. Two mostly used theorems about martingales are : martingale convergence theorem and the optional stopping theorem. Rather than throwing out more abstract rumblings, let me give you a concrete example.

The following is a simple version of the so-called 'urn problem'. I am telling you this problem, because through this problem I got the first taste of what researc probability is all about and learnt how martingales can be useful! Let us suppose you have a bin with two colored balls: black and white. Let us start with $1$ black and $1$ white just for the sake of concreteness. Now the rule is this: we randomly draw a ball, every time we pick a ball, we have to put in an extra ball of the same color. For example, if we pick a white ball, we have to put back the picked white ball along with an extra white ball. Now we can ask, does the fraction of white balls converge almost surely? It is easy to see that after $n$ draws, there are $n+2$ balls in the bin. Now when we try to prove something converges, we try to find a martingale so that we can use the martingale convergence theorem. But it is very unclear, what the martingale is here. So lets do a back of the envelope computation. let $W_n,B_n$ be the number of black, white balls respectively after $n$ draws. Clearly, $$ E(W_{n+1}|W_n,B_n) = (W_n+1)\frac{W_n}{n+2} +W_n (1- \frac{W_n}{n+2}) = W_n(1+\frac{1}{n+2}) $$

so $W_n$ does'nt turn out to be a martingale (we want the fraction of whites anyway). But a trained probabilist immediately sees that even though $W_n$ is not a martingale, $$W_n'=\frac{W_n}{\prod_{j=1}^{n-1}(1+1/j)}$$ is. This is simply a back-calculation trying to equate both sides of the calculation above, you can try it yourself! Now all that is left is to find the asymptotics of $a_n:=\prod_{i=1}^n(1+1/i)$ and a bit more computation (which I will not do here!) shows that $a_n /n \to 1$. Now using Martingale convergence theorem, and he previous observation, we can show: $$ \frac{W_n}{n+2} = \frac{W_n}{a_n}\frac{a_n}{n} \to W $$ for some random variable $W$. Determining what $W$ is though is a separate question, and martingale theory can only tell us so much.

Anyway, the point of the above example is to show you a typical situation in which martingales can come in handy. For sub or super martingales, sometimes the decomposition comes in handy, especially in stochastic calculus, but in most cases I have encountered the $A$ part is hard to understand, but still the convergence theorem holds under the right conditions! Sometimes backward martingales are also useful.

For question 1), depends on what you call solvable. In mathematics community, computer simulations showing something is not something considered as a ''proof''. There are many open questions, which have been shown by a computer to be true without any shade of doubt, but is still considered not solved by the mathematics community. The Riemann hypothesis is a prime example of this. However, there is actually something called ''exactly solvable models'', where one can find exact answer to some questions (like how many configurations are there in such and such domain under such and such constraints etc), however such models are few and far between. Mostly, we are happy to accurately approximating a model, and show some convergence results, as in the above example. Rather than finding a formula for the exact distribution of $W_n$, probabilists are more interested in the asymptotics, and martingale techniques are just one of many ways to deal with this.

Hope all this made sense and I could somehow answer your question which probably we can spend days discussing! :)

$\endgroup$
  • $\begingroup$ thank you very much! I see that martingales are invoked not because we can get exact solutions form them, but because they help clarify and move one towards the true problem. E.g., finding $W$ in your example. Also, it sounds like closed form solutions are really left to simple cases, so the benefit for professional probabilist is its ability to reduce the number of things to prove to get to a new theorem. Thanks for your helpful answer. $\endgroup$ – user76844 Oct 22 '14 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy