This too Will Pass

More Ito

Posted on March 1, 2011 by putnam120

Last time I introduced the Ito integral. Here’s are some of the key facts that were mentioned:

$I(t)$ is a martingale.

$I(t)$ is continuous.

$I(t)$ is $\mathcal F(t)-\mbox{measurable}$ .

Here are some other results that wasn’t mentioned last time (and won’t be proven here) but it very important.

$\displaystyle \mbox{Var}I(t)=\mathbb E I^2(t)=\mathbb E\int_0^t\Delta^2(u) \,du$ .

$[I,I](t)=\int_0^t\Delta^2(u) \,du$

These equations show the difference between quadratic variation and the variance of a random variable. Notice that the quadratic variation depends on the path taken by the underlying Brownian motion. However, the variance can be though of as an averaging over all possible paths.

Ito-Doeblin Formula

Suppose that $f(x)$ is a “nice” function, and you want to evaluate $\int_0^tf(x) \,dW(x)$ . As we saw last time the answer might not be what you expect. So how do we get around this? This is where the Ito-Doeblin formula comes to the rescue.

Theorem: Let $f(t,x)$ be a function such that $f_x, f_t,\mbox{ and}, f_{xx}$ are continuous. Then we have that

$\displaystyle f(T,W(T))=f(0,W(0))+\int_0^Tf_t(t,w(t))dt+\int_0^Tf_x(t,w(t))dW(t)+\frac{1}{2}\int_0^Tf_{xx}(t,W(t))dt$

This is known as the integral form of the formula, I will present the differential form later. If you look at this you should think of a Taylor expansion of a function. In fact this is how the theorem is proved. The reason that you only need the second order approximation, is because it can be shown that the value of all the higher order terms are 0.
The integral form is nice since it specifies an exact functional solution to the following differential equation.

$df(t,W(t))=df_t(t,W(t))dt+df_x(t,W(t))dW+\frac{1}{2}df_{xx}(t,W(t))dt$

This is known as the differential form, and in my opinion is easier to work with. At least as far as proofs and “simple” calculations are concerned.

Example

Calculate $\displaystyle\int_0^Te^{W(t)} \,dW(t)$ .
Well since we have been talking about the Ito-Doeblin formula for a while, it is only natural that that is where we should start. We will choose $f(t,W(t))=\exp\{W(t)\}$ , and one application of the formula gives

$\displaystyle e^{W(T)}-e^{W(0)}=e^{W(T)}-1=\int_0^Te^{W(t)} \,dW(t)+\frac{1}{2}\int_0^Te^{W(t)} \,dt$

Ito Process

We can generalize the process $I(t)$ even further. Originally we have that it is an integral with respect to Brownian motion, but what if we added in a component that wasn’t quite as random? Let

$\displaystyle X(t)=\int_0^t\Theta(u) \,du+\int_0^t\Delta(u) \,dW(u)$

It is possible for both $\Theta$ and $\Delta$ to be random or deterministic, either way $X(t)$ is called an Ito process.
It can be shown that $X(t)$ more or less has the same properties as $I(t)$ , and this shouldn’t be too hard to believe. However, one very important fact is that we also have a version of Ito’s formula for this process, here it is in differential form:

$\displaystyle df(t,X(t))=df_t(t,X(t))dt+df_x(t,X(t))dX(t)+\frac{1}{2}df_{xx}(t,X(t))dt\ \ \ \ (1)$

and from the definition of $X(t)$ we have that,

$\displaystyle dX(t)=\Theta(t)dt+\Delta(t)dW(t)$ .

So making this substitution and rearranging terms yields:

$\displaystyle df(t,X(t))=\left(df_t(t,X(t))+{\Theta(t)}df_x(t,X(t))+\frac{1}{2}df_{xx}(t,X(t))\right)dt+\big(\Delta(t)df_x(t,X(t))\big)dW(t)\ \ \ \ \ (2)$

Although $(2)$ is more complete it is a little harder to remember, and I find that using $(1)$ works just as well and is in fact easier to work with.

Posted in Brownian Motion, Martingale | Leave a comment

Ito Integral

Posted on January 31, 2011 by putnam120

It just hit me that I don’t have a post on the Ito Integral. It is the integral of choice for financial mathematics, plus it’s pretty interesting.

Construction

For the rest of the post we will let $W$ denote Brownian motion, unless otherwise stated. Furthermore, let $\mathcal{F}(t)$ be a filtration, and $\Delta(t)$ an adaptive process.
If we view $W(t)$ as the stock/asset price at time $t$ , and $\Delta(t)$ is our position (number of stocks we own), then for a fixed $T$ our gain over $[0,T]$ is

$\displaystyle I(t)=\int_0^T\Delta(t) \,d{W(t)}$

There are a few things that should be mentioned before we continue. First of all, $W(t)$ is not differentiable. This makes things a little more “interesting”, since if we had a differentiable function $g(t)$ we would have that $\int f(t) \,dg(t)=\int f(t)g'(t) \,dt$ . Secondly, it should be mentioned that this lack of differentiability is due to the fact that $W(t)$ has nonzero quadratic variation.

So to get around this we will define the integral in what I consider to be similar to how one constructs the Lebesgue integral. The integral is first defined for simple functions, $\phi_n$ . In this case the simple functions are a little different from the ones used for the Lebesgue integral. And then we define the integral of a general function, $\phi$ , as the limit of $\int\phi_n \,dW(t)$ where $\phi_n\to\phi$ (The convergence is $L^2$ convergence).

So let us get started. First we create, $0=t_0<t_1<\ldots<t_n\le T$ , a partition of $[0,T]$ . A function $f$ is said to be "simple" if $f(t)$ is constant on $[t_n,t_{n+1})$ . So for these simple functions the Ito integral is defined as follows:

$\displaystyle I(t)=\int_0^T\Delta(t) \,dW(t)=\sum_{i=0}^{n-1}\Delta(t_i)\left[W(t_{i+1})-W(t_i)\right]+\Delta(t_n)\left[W(T)-W(t_n)\right]$

For those of you that have some measure theory background you can kind of think of $W(b)-W(a)$ as the measure of the interval $[a,b)$ . Yes, technically this might not (well it probably wouldn’t) work as a measure in the usual sense, but it can be useful in helping make sense of the integral.

Now suppose that $\phi_n$ is the simple function associated with the partition $\{t_0,\cdots,t_n\}$ and satisfies $\phi_n(t_i)=\phi(t_i)$ . Then as $\max |t_{i+1}-t_i|\to 0$ it is clear that $\phi_n\to\phi$ . Thus as mentioned above the integral of $\phi$ is defined as the limit of the integral of the $\phi_n$ ‘s.

With this, it can be shown that
$\displaystyle \int_0^TW(t) \,dW(t)=\frac{1}{2}[W(T)]^2-\frac{1}{2}T$ .
The derivation of this can be found in any textbook, since it seems to be the example of choice, in some cases it is the only example presented.

Attention: In the construction of the Lebesgue integral we choose our simple functions so that $\phi_n\le\phi$ . However, here we do not make this assumption. The reason for this is that if we think of the $\{[t_i,t_{i+1})\}$ as the trading periods, then we must choose our position at the beginning of the period, and before knowing how the stock price will change.
If instead, we let $\phi_n$ take the value at the midpoint of the interval we end up with the Stratonovich integral. I’m not sure what happens if you use the right endpoint, though I expect something similar to the Ito Integral.

Properties

I won’t give a formal proof of any of these claims, but they should be obvious.

$\displaystyle I(t)=\int_0^t\Delta(x) \,dW(x)$

$I(t)$ is continuous in $t$ .
This one is not all the surprising since $W(x)$ is continuous and we are working with an integral.
If $I_1=\int\Delta_1 \,dW$ and $I_2=\int\Delta_2 \,dW$ , then $I_1+I_2=\int(\Delta_1+\Delta_2) \,dW$ .
Also somewhat obvious.
$I(t)$ is a martingale. As a result $\mathbb EI(t)=0$ for all $t$ .
Proving this takes a little more effort so I suggest you look in a textbook or online since I won’t provide a proof.
$I(t)$ is $\mathcal F(t)\mbox{-measurable}$

I’ve made this post long enough, so I’ll provide some examples and useful facts in the next post.

Posted in Brownian Motion, Expected value and Variance, Martingale | Leave a comment

The Island

Posted on January 22, 2011 by putnam120

I was introduced to a new band Sleigh Bells…but you don’t want to hear about. So I’ll get back to the math talk. Today I’m going to talk about a brainteaser, that I’m sure you have heard before, and if not you will like.

The Question

Here is one version of the puzzle statement, that I got from my friend at TerminalOfPuzzle.

There is an island on which there are 201 people. 100 of them have brown eyes, 100 of them have blue eyes, and 1 has green eyes. No islander knows his or her own eye color, and though they can all see each other, no islander is aware of the exact eye color distribution either. This is arguably unfortunate, because according to the rules of the land, you’re trapped on the island unless you can determine your eye color with certainty. If you somehow do manage to figure it out, you must on the same day gather your belongings and leave the island, never to return, on the ship that brings supplies each night. There are no mirrors or other reflective objects anywhere on the island, and the islanders won’t risk using the ocean water either. To make matters worse, eye color is a taboo topic, so the islanders can’t help each other. There has been only one exception: one day, let’s call it day 1, the green-eyed person said “I see a person with blue eyes.” This was so shocking to the islanders that eye color would henceforth never be brought into discussion ever again. What happens on this island? Who, if anyone, leaves the island and when?

Now if you haven’t solved or seen this puzzle before I won’t ruin it for you. However, I will provide these few hints. First off, the people with brown eyes don’t matter. They might as well have any eye color for all you care, well any color but blue of course. Second 201 is kind of hard to work with at first, so try working with smaller number like 3, 5, etc.

Variations

In this version of the puzzle the inhabitants of the island are aware that there are only 3 possible eye colors. However, they do now know that all colors are represented on the island. What happens in this version of the puzzle?

This time there are only 2 possible eye colors, blue and green. Once again the inhabitants are well aware of this fact. Furthermore, suppose that there are $n$ people with blue eyes and $m$ people with green eyes. What happens now?

Assume the same conditions as the previous version. However, this time there is a genetic disease that causes a problem with their vision. Each day, with probability $p>0$ , a person will see green as blue, and blue as green. Let $p(j)$ be equal to the number of days before $j$ people have left the island. What are $\mathbb P(p(j))$ and $\mathbb Ep(j)$ ?

The answer to the first two are rather “simple”, but I’m not sure about the last one. There is a chance that the problem itself could be poorly stated. Regardless I’ll work on it some and ‘fix’ any problems as they arise. If you have anything to add, please feel free to do so.

Posted in Uncategorized | Leave a comment

Maximum Value

Posted on January 18, 2011 by putnam120

Recently I have been getting a lot of visits (well what I consider a lot) to this blog because of the Knapsack Problem. Since this seems to be so popular, and people don’t want to go to Wikipedia, I suppose I will dedicate at least one post to the topic.

Problem Statememtn

Suppose that you have a collection of objects $a_1, a_2,\cdots, a_n$ , with respective weights $w_1, w_2,\cdots, w_n$ and value $v_1, v_2,\cdots, v_n$ . Your task is to find a subset of these items with maximum value. However, this is one condition, the items you choose must be able to fit in a bag that can only carry a maximum weight of $W$ before breaking.

For those of you that are more mathematically inclined, and want to see the short version of the problem, here it is;

$(1)\ \ \ \ \ \ \max\sum v_ix_i\mbox{ such that }\sum w_ix_i\le W\mbox{ and }x_i\in\{0,1\}$

Where $x_i=1$ means that you choose to take object $a_i$ , and $x_i=0$ means that you do not.

Solutions

I will present two different approaches to solving this problem. Both these approaches can be applied to a wide range of problems, so the reasoning behind the algorithms is more important than the particular cases that follow.
In the solutions it is assumed that $x\in\mathbb R^n$ , and $0\le x\le 1$ means that $0\le x_i\le 1$ for $i=1, 2,\cdots, n$ .

Branch and Bound

In this approach, instead of solving the problem as it is presented in $(1)$ we consider the relaxation

$(2)\ \ \ \ \ \ \max\sum v_ix_i\mbox{ such that }\sum w_ix_i\le W\mbox{ and }0\le x\le 1$ .

You should notice that any feasible solution (one that satisfies the constraints) to $(1)$ is also a feasible solution to $(2)$ . The reason we consider the relaxation is because there might be a way to quickly obtain an answer.

So suppose that we find $x^*$ to be the optimal solution to $(2)$ . If it turns out that $x^*_i\in\{0,1\}$ we also have that $x^*$ is optimal for $(1)$ . Well this is not interesting at all, so without loss of generality suppose that $x^*_1\notin\{0,1\}$ . So even though $x^*$ is optimal for $(2)$ it is not feasible for $(1)$ . To fix this small oversight we split $(2)$ into two subcases:

$(2.1)\ \ \ \ \ \ \max\sum v_ix_i\mbox{ such that }\sum w_ix_i\le W\mbox{ and }0\le x\le 1\mbox{ and }x_1=0$

and

$(2.2)\ \ \ \ \ \ \max\sum v_ix_i\mbox{ such that }\sum w_ix_i\le W\mbox{ and }0\le x\le 1\mbox{ and }x_1=1$

Now the optimal value of each of these problems will have $x^*_1\in\{0,1\}$ . Furthermore, if we let $V, V_1, V_2$ be the optimal values of $(2), (2.1),\mbox{ and }(2.2)$ it is clear that $V_1\le V$ and $V_2\le V.$ Now suppose we have found $x(1)$ to be the optimal solution to $(2.1)$ and $x(2)$ for $(2.2)$ , and $V_1 > V_2$ .

If $x(1)$ satisfies the constraints of $(1)$ then we are finished. If not, we then split $(2.1)$ into two problems, similar to how we split $(2)$ into two problems. Now these problems give optimal values $V'_1, V'_2$ . We then see which of $V_2, V'_1,\mbox{ and }V'_2$ is largest, and check to make sure that its optimal point satisfies the constraints of $(1)$ . If it does not, we just split it into two problems, solve those problems, and compare our list of optimal values and points.

I’ll leave it to you to show that this process will not only terminate, but also find the optimal solution to $(1)$ .

The reason for the Branch in the name of this approach is obvious. If our optimal solution to is not feasible for $(1)$ we split (branch) it into two subproblems.
To see the reason for Bound is as follows. Suppose that we perform the process and have a set of optimal values $V_1<V_2<\cdots<V_n$ and optimal points $x(1), x(2),\cdots, x(n)$ . Then the solution to $(1)$ has optimal value of at most $V_n$ . However, if we must split because $x(n)$ does not satisfy the necessary constraints, then the optimal values from the subproblems will be at most $V_n$ . So we therefore have a bound on the possible optimal value.

The Branch and Bound approach rest on the assumption that you are able to solve the relaxed problem. Usually it is assumed that solving the relaxed problem is not only possible, but can be done rather quickly.

Dynamic Programming

I won’t go into too much (if any) detail about what dynamic programming is. However, I will say this; the main idea is that the optimal solution for $P(n+1)$ can be built from the optimal solution for $P(n)$ , kind of like induction if you think about it.

In our case we will let $P(i,j)$ be the maximum value we can achieve by only using objects $x_1,\cdots, x_i$ and with maximum weight of $j$ . Thus our desired answer is $P(n,W)$ .

For the sake of simplicity we will define $P(0,j):=0$ for all $j$ . Now how do we determine the value of $P(i,j)?$ Well there are two cases

Case 1: $w_i>j$
In this case it is not possible to add object $a_i$ without exceeding out weight constraint. Thus $P(i,j)=P(i-1,j)$ .

Case 2: $w_i\le j$
In this case we have two choices. We can either take object $a_i$ or we can leave it behind.
If we leave it behind then $P(i,j)=P(i-1,j).$
However, if we choose to take it we must remember that the total weight is equal to $j$ . Therefore, if object $a_i$ is taken we have that $P(i,j)=v_i+P(i-1,j-w_i).$

In this case $P(i,j)=\max\{P(i-1,j),v_i+P(i-1,j-w_i)\}.$

Conclusion

As you can see, the dynamic programming solution is easier to program, but I feel that it is also nice to know the branch and bound approach. After reading the above solutions you should be able to quite easily create your own code. For the dynamic programming approach I suggest using arrays since recursion can be quite expensive. As for the branch and bound solution, I suggest using some sort of heap in order to store the information about the subproblems that you will create.

Other Forms

Here are some other problems that can be though of as variants of the Knapsack problem, even though at first glance they might not appear to be. All of these problems can be solve by adjusting the above solutions to the original Knapsack problem. Although the above solutions might work, they might not be the most efficient.

Example 1

Given an integer $s$ and a collection of integers $A=\{a_1, a_2, \cdots, a_n\}$ does there exist a subset $S\subseteq A$ such that

$\displaystyle\sum_{a_i\in S}a_i=s$

Case 1: $s>0$ and $a_i\ge 0$ .
In this case our optimization problem can be written as

$\max\sum a_ix_i\mbox{ such that }\sum a_ix_i\le s\mbox{ and }x_i\in\{0,1\}.$

So if the answer to this problem is $s$ then such a subset $A$ does exist. Otherwise, the answer is no.

If $s<0$ and $a_i\le 0$ then just multiply by $-1$ and solve the problem in the above form.

Case 2: $s=0$
The problem can now be written as (although it is no longer a linear program)

$\min\left|\sum a_ix_i\right|\mbox{ such that }x_i\in\{0,1\}.$

If the answer is $0$ then there is a subset sums to $0$ , otherwise there is not.

Example 2

Suppose that there are $c_i$ copies of each item. Then we can either treat each copy as unique, or instead solve

$\max\sum v_ix_i\mbox{ such that }\sum w_ix_i\le W\mbox{ and }x_i\in\{0, 1,\cdots, c_i\}.$

Posted in Optimization | Leave a comment

Optimization

Posted on January 7, 2011 by putnam120

When I first started graduate school the only optimization problems I knew how to solve were of the form:

$\displaystyle\min_{x\in K}f(x)$

Where $f(x)$ has a second derivative and $K$ is a compact subset of $\mathbb R^n$ . Needless to say, this really doesn’t get you that far, or at least not many interesting problems can be put into this form.

Of course there were optimization problems other than this, that I knew how to solve. For instance, the Knapsack problem. I was first introduced to this during a programming team practice where we were covering dynamic programming. But because of this, I never really considered this to be an “optimization problem”.

Well this year I took my first course in linear optimization, with a small section on non-linear optimization. Just so you know how little I knew about the subject when I took this class, you can say that linear inequality was the only phrase mentioned in the first lecture that I had prior knowledge about. Obviously I learned quite a bit, though it almost seems trivial at this point. For a good portion of the course we were interested in solving problems of the form

$\displaystyle\min\sum c_ix_i\mbox{ subject to the condition that }Ax=b\mbox{ and }x\in K$

where $K$ is a closed convex cone, and $A$ is a $m\times n$ matrix of full rank. The condition that $K$ be a closed convex cone can be dropped, it just happens that this is what we considered. Furthermore, you can also consider constraints where $Ax\le b$ and $Ax\ge b$ (and also with strict inequality).

Returning to the knapsack problem, it should be “obvious” (don’t worry it wasn’t to me at first) that we can put it in terms of a linear program (an optimization problem with linear constraints, and linear function to optimize). If we let $\omega$ be the weight vector for each item, $W$ be the total weight the knapsack can hold, and $v$ be the value vector, our problem is thus

$\displaystyle\max\sum v_ix_i\mbox{ such that }\sum\omega_ix_i\le W\mbox{ and }x_i\in\{0,1\}$ .

Here $A$ is a $1\times n$ matrix, so we just replace $Ax$ by the sum. Actually this problem would better be described as an integer programming problem, but that’s not the point.

I’m not going to go into theory since this blog is about probability and not optimization. Though if anyone knows of a place where they coexist (and I am sure there is one) PLEASE LET ME KNOW!

What interest me most, is the algorithms used to the kinds of problems. Most people (well maybe not most, but most once you restrict to the obvious collection) have heard of the simplex method, and the “less famous” ellipsoid method and interior point method. In addition to these, there are other method, some which depend on the form of the problem.

Recently I have been coding solutions to a few problems, and came across one where the best solution I could think of was $O(n!)$ . Well it turns out I had the right approach, but was unnecessarily searching the entire search space looking for the answer. The reason I mention this is because in the problem I was trying to minimize a linear objective function. However, I couldn’t think of a nice mathematical way to represent all of the constraints. So for some reason I decided that a good place to start would be reading about integer programming (don’t ask me why). Luckily I ended up reading about combinatorial optimization, a term I had heard before but never really took the time to see what it was.

The readings didn’t really help me solve the problem (I ended up having to use recursion and some other things to cut the search space down), but it did get me more interested in the subject. So for the remainder of my break (about 13 days) I plan to continue reading. As a result new post will be on hiatus for a while, unless they are optimization related in some way.

Posted in Optimization | Leave a comment

Renewals and Repeats 3

Posted on December 27, 2010 by putnam120

So far we have just presented a lot of properties of theorems about renewal processes. This isn’t that much of an issue but examples are always nice.

Example 1

Suppose that buses arrive at a station at times $T, 2T,\dots$ (buses in this example are always on time an can hold an infinite number of people). Additionally, suppose that passengers arrive according to a Poisson process with rate $\lambda$ . What is average waiting time per passenger?
Solution: The time that the $i^{th}$ passenger arrives is $S_i$ , and thus by time $T$ there are $N(T)$ passengers waiting for the bus. The time that each person waits is $T-S_i$ , and thus the average wait time is

$\displaystyle \frac{1}{N(T)}\left(\sum_{n=1}^{N(T)}(T-S_n)\right)=T-\frac{1}{N(T)}\sum_{n=1}^{N(T)}S_n$

Then taking the expected value will give us the expected, average waiting, time. In an earlier post we showed that $\mathbb E\left[\mathbb E[X|Y]\right]=\mathbb EX$ . Since $T$ is not random, we are only interested in finding the expected value of the $\frac{1}{N(T)}\sum S_n$ term.

$\mathbb E\left(\mathbb E\frac{\sum S_n}{N(T)}|N(T)\right)=\mathbb E\left(\mathbb E\frac{\sum U_{(i)}}{N(T)}|N(T)\right)=\mathbb E\left(\frac{N(T)T}{2}\cdot\frac{1}{N(T)}\right)=\frac{T}{2}$ .

In order for the above proof to make sense (to you since I already know what everything means) a few things need to be explained. If $U_1, U_2,\dots, U_n\sim U(0,T)$ (uniform on 0 to T) then we denote the order statistics by $U_{(1)}, U_{(2)},\dots, U_{(n)}$ where $U_{(1)}\le U_{(2)}\le\dots\le U_{(n)}.$ Each $U_{(i)}$ has an expected value of $\frac{T}{2}$ . Finally, later we will show that if we know $N(T)=n$ then $(S_1, S_2,\dots, S_n)$ has the same distribution as $(U_{(1)},\dots, U_{(n)})$ .

Therefore, the expected average waiting time for a passenger is $\frac{T}{2}$ , which is what you would have expected. We only have to consider the time interval $[0,T]$ since once that first bus leaves, the process “restarts”. That is one of the cool things about renewal processes, you usually only need to consider the first time period.

Example 2:

Now suppose that the arrival times of the buses is no longer deterministic. Instead, the expected waiting time between buses is $T$ . It can be shown that the expected waiting time is strictly larger that $\frac{T}{2}$ . In fact it is equal to $\dfrac{\mathbb EY_1^2}{2\mathbb EY_1}$ .
This will/might be proven in a future post, so no need to dwell on it yet. If you must see a proof, do a search for Google search for the inspection paradox.

Theorem

Given that $N(T)=n$ then $(S_1, S_2,\dots, S_n)$ has the same distribution as $(U_{(1)},\dots, U_{(n)})$ , where $U_{(i)}$ is the $i^{th}$ order statistic for the uniform distribution on $[0,T]$ .

proof: The density of $(U_{(1)},\dots,U_{(n)})$ is given by $f(t_1,\dots,t_n)=\dfrac{n!}{T^n}$ , if $t_1\le t_2\le\cdots\le t_n$ , and $0$ otherwise.
Choose $t_1<t_2<\cdots<t_n$ , and let $h_i$ be such that $t_i+h_i<t_{i+1}$ . Now consider

$P\left(N(t_i+h_i)-N(t_i)=1\ \mbox{for }i=1,2,\dots,n\ \mbox{and no other events in }[0,T]\right)$

Since we have a Poisson process, this is equal to

$\lambda h_1e^{-\lambda h_1}\cdots\lambda h_ne^{-\lambda h_n}e^{-\lambda(t-h_1-\dots-h_n)}=\lambda^nh_1\cdots h_ne^{-\lambda t}\ \ \ \ \ \ (1)$

Now we consider the probability that $S_i\in [t_i,t_i+h_i]$ , given that there are a total of $n$ renewals. Therefore,

$\displaystyle P\left(t_i\le S_i\le t_i+h_i\ \mbox{for }i=1,\dots,n\ |\ N(T)=n\right)=\frac{(1)}{P(N(T)=n)}\ \ \ \ (2)$

Using the fact that $N(t)$ is a Poisson process with rate $\lambda$ we have that

$P(N(T)=n)=\frac{(\lambda t)^n}{n!}e^{-\lambda t}$

Then clearly $(2) = \frac{n!}{T^n}h_1\cdots h_n$ , so if we divide both sides by $h_1\cdots h_n$ and let $h_i\to 0$ we arrive at the desired density.

Posted in Distributions, Expected value and Variance, Renewal Theory | Leave a comment

Renewals and Repeats 2

Posted on December 26, 2010 by putnam120

Near the closing of the previous post, the functions $U(t)$ and $V(t)$ were introduced. The form $U(t)=\mathbb EN(t)$ is not all that useful when you want to do explicit calculations. It should be noted that when $N(t)$ is a Poisson process, the calculation of $\mathbb EN(t)$ is rather simple, but in other situations this is not the case.

Recall that from the post on expected value, we can write $\displaystyle\mathbb EX=\sum_{n=1}^\infty P(X\ge n)$ . Therefore, we can rewrite the expression for $U(t)$ .

$\displaystyle U(t)=\sum_{n=1}^\infty P(N(t)\ge n)=\sum_{n=1}^\infty P(S_{n-1}\le t)$

The last equality follows from the fact that if more than $n$ events occur in $[0,t]$ then the $n^{th}$ event (which is $S_{n-1}$ ) must occur in this interval. A useful inequality we will use is that $S_{N(t)-1}\le t < S_{N(t)}$ .

The above expression is an improvement from what we started with, but we can do much better. Recall that the $Y_i\sim F$ are independent, and therefore, $S_n\sim F^{n*}$ . And thus we finally arrive at the expression

$\displaystyle U(t)=\sum_{n=0}^\infty F^{n*}(t)$

Properties of N(t)

We will assume that $\mathbb Y_1=\mu<\infty$ . The reason for this is so that we may apply the strong law of large numbers.

$\displaystyle P(N(t)<\infty)=1$ .
proof: Let $A$ be the set of sequences such that $\frac{S_n}{n}\to\mathbb EY_1=\mu$ . Thus, by the string law of large numbers, $P(A)=1$ . Now define $B=\{N(t)=\infty\}$ , this is the set of sequences for which $N(t)=\infty$ . For $\omega\in B$ we have that $S_n(\omega)\le t$ for all $n$ . Here $S_n(\omega)$ is the value of $S_n$ for the sequence $\omega$ . We have that $S_n(\omega)\le t$ because $N(t)=\infty$ , an infinite number of renewals in $[0,t]$ . Now for $\omega\in A$ there exist $K(\omega)$ such that $\frac{S_n(\omega)}{n}>\frac{\mu}{2}$ for $n > K(\omega)$ . Which means that $S_n(\omega)>\frac{n\mu}{2}$ for $n>K(\omega)$ . From this we can see that $S_n(\omega)\to\infty$ as $n\to\infty$ , and therefore $A\cap B=\emptyset$ , so $P(B)=0$ .
If $0\le\gamma<\frac{1}{F(0)}$ then $\displaystyle\sum_{n=0}^\infty\gamma^n F^{n*}<\infty$ .
$N(t)$ has a moment generating function. So all moments of $N(t)$ are finite, so $U(t)<\infty$ and $V(t)<\infty$ .
$N(t)\to\infty$ as $t\to\infty$ almost surely.
proof: $N(t)$ is nondecreasing in $t$ , so for any $n$ we have that $\{N(t)>n\}\subset\{N(t')>n\}$ for $t'\ge t$ . Using this fact and the continuity for measures,
$\mbox{ }\\\$
$\displaystyle P(N(t)\to\infty,\ t\to\infty)=P(\exists t'\ s.t.\ N(t')\ge n\mbox{ for arbitrary n})=\\\\P(\lim_t\{N(t)>n\})=\lim_tP(\{N(t)>n\})=\lim_tP(S_n\le t)=\\\\\lim_t G*F^{n*}(t)=1$ .
If $P(Y_0<\infty)=1$ then $\frac{N(t)}{t}\to\frac{1}{\mu}$ as $t\to\infty$ .
Let $Var(Y_1)=\sigma^2$ then as $t\to\infty$ we have that the distribution of $N(t)$ approaches a normal distribution with mean $\displaystyle\frac{t}{\mu}$ and variance $\displaystyle\frac{t\sigma^2}{\mu^3}$ .

For the above claims that don’t have proof, you can refer to Adventures in Stochastic Processes by Sidney Resnick (the chapter on Renewal Processes) or possibly any other Stochastic Processes book.

I know that this is a long list, but most of them are what you would expect, so nothing all that astonishing.

Posted in Central limit theorem, Poisson Process, Renewal Theory | Leave a comment

This too Will Pass

More Ito

Ito-Doeblin Formula

Example

Ito Process

Ito Integral

Construction

Properties

The Island

The Question

Variations

Maximum Value

Problem Statememtn

Solutions

Branch and Bound

Dynamic Programming

Conclusion

Other Forms

Example 1

Example 2

Optimization

Renewals and Repeats 3

Example 1

Example 2:

Theorem

Renewals and Repeats 2

Properties of N(t)

Recent Posts

Categories

Archives

Follow “This too Will Pass”