Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $(X_t)_{t\ge0}$ be a Markov chain on a finite state space $\Omega$, with transition probability $P$. Let $T$ be a stopping time such that $T=\min \{t\ge 0;X_t \in A \subset \Omega \}$.  If $f(x)=E_x(T)$ is such that

$$f(x)=0, x \in A$$ $$f(x)= 1+\sum_{y \in \Omega }P(x,y)f(y), x \notin A$$

How can I show that $f$ is uniquely determined by the previous equation?

I'm not clear on what I have to prove here.

I guess the proof goes as: Suppose $\exists g \ni g \ne f$ and $g(x)=E_x(T)$.

But I don't see any sense here.

share|improve this question
1  
Could you give some more information about $X$? Seems that it is in a discrete time and the state space is $\mathbb Z_+$ but some details from your side will help understanding it. Is it Markov? –  Ilya Sep 28 '11 at 13:59
    
Yes, the process is Markov on a finite state space. I though this information doesn't change the spirit of the proof. Sorry, if it does. –  Nicolas Essis-Breton Sep 28 '11 at 14:10
2  
There is something fishy here: if $(f(x))_x$ solves your relations and if $f\ge0$ everywhere, then using $f\ge0$ in the RHS yields $f\ge1$ everywhere, hence using $f\ge1$ in the RHS yields $f\ge2$ everywhere, and so on, hence $f$ is identically $+\infty$. Looks like you did not copy faithfully the source you are taking this from. –  Did Sep 28 '11 at 14:16
2  
@Nicolas There is the germ of a reasonable question here, but you really have to put more effort into your post. For instance, the equation $f(x)=E(T)$ has a variable $x$ on the left but not on the right. Did you really want a constant function? Also, in your equation did you really want to condition on $X_0\neq 0$? Are you possibly leaving out important information like boundary values?? If you take some time to make your question more precise, then you will get better answers. –  Byron Schmuland Sep 28 '11 at 14:47
1  
When $T$ is the first hitting time of a subset $A$ of the state space $S$ by a Markov chain $(X_t)_t$ on $S$, one usually defines $f(x)=E_x(T)$ for every $x$ in $S$ (hence $f=0$ on $A$). Then $f(x)=1+\sum_yq(x,y)f(y)$ for every $x$ not in $A$, where $q(x,y)=P(X_1=y\mid X_0=x)$. You could say if this is the (classical) setting you have in mind. –  Did Sep 28 '11 at 15:40
show 4 more comments

2 Answers

up vote 2 down vote accepted

Ok, so let us put the equation in the one line: $$ f(x) = 1_{A^c}(x)+1_{A^c}(x)\sum\limits_{y\in \Omega}P(x,y)f(y).\quad (1) $$ Here $1_{A^c}(x)$ is an indicator function of $A^c = \Omega\setminus A$. I.e. $1_{A^c}(x) = 1$ for $x\in A^c$ and $1_{A^c}(x) = 0$ for $x\in A$. Let us consider now the homogeneous version of the very same equation (which I happened to investigate in my first post): $$ g(x) = 1_{A^c}(x)\sum\limits_{y\in \Omega}P(x,y)g(y). \quad(2) $$

Note again that the equation is linear so the solutions of these equations built the linear space. Of course, $g^* = 0$ is a solution of (2). In the simplest case when $A^c$ is finite, an equation (2) has a unique bounded solution iff $A^c$ does not have absorbing subsets since $g(x)$ is a probability that $x$ will never leave $A^c$.

Of course it's iff the determinant of $P'$ which is build only by rows and columns from $A^c$ is non-zero. This led me to the idea that non-uniqueness of (1) in this case depends only on the absorbing subsets of $A$. About existence of solution for (1) we 'may not care' since there is at least one function which admits this equation, namely $f(x)=\mathsf E_x[T_A]$. On the other hand, such function takes values from the extended real line for which case uniqueness of the solution is unclear for me.

Consider again the previous example. Let $P$ be a unit matrix of dimension two, so $p(1,1) = 1$, $p(1,2) = 0$ and $p(2,1) = 0, p(2,2) = 1$. Let us solve it for $A = \{1\}$. If you write your equation for this case you will have $f(1) = 0$ and $f(2) = 1+f(2)$, so the solution of the latter equation is either $-\infty$ or $\infty$ though I am not so experienced in solution of such equations. Well, you can say that the solution is unique if you are looking only for non-negative solutions.

The point is the following: theory of uniqueness for such equations based on fact that solutions build up the vector space. Hence, for any solution $f^*$ of (1) and non-zero solution $g^*$ of (2) you can claim that $f^*+\alpha g^*$ is a solution of (1) which is different than $f^*$. On the other hand, if $f^*$ take infinite values then $f^*+\alpha g^*$ can coincide (at least in symbols) with $f^*$.

Let us consider arbitrary $A^c$. What does mean that (2) has a non-zero solution? The invariance probability is the maximal solution of (2) which lies in $[0,1]$. Let us denote it by $g^*$. So, for each point in which $g^*>0$ it holds that $\mathsf E_x[T_A] = \infty$ (is it clear?). For such points, $f^* = \infty$ and hence $f^*(x)+\alpha g^*(x) =\infty = f^*(x)$, though this statement is quite informal for me.

I cannot give you a complete formal answer to your question since I was always looking only for bounded solutions of such equations. The latter paragraph gives a guess that the solution is indeed unique since non-uniqueness of solution of (2) will appear only in points where $f^*$ is infinite and hence will not influence $f^*$. On the other hand, I didn't consider the case when (2) may have unbounded solution. E.g. by Lebesgue's convention $0\cdot\infty = 0$ so one can say that $g = 1_{A^c}\cdot\infty$ admits (2), if for any $x\in A^c$ there is a transition to $A^c$, as well as $g=0$.

Anyway, I think you need a person more experienced in solving linear equations with unbounded solutions. the other advise is the following - if you want to calculate the solution, you will certainly need to cut-off points in which $\mathsf E_x[T_A] = \infty$. So you will have something like $$ f(x) = \begin{cases}0,&\text{ if }x\in A, \\ \infty,&\text{ if }x\in B \\ 1+\sum\limits_{y\in\Omega}P(x,y)f(y), &\text{ if }x\in (A\cup B)^c \end{cases} $$

I haven't deal with the problem of the average hitting time, so maybe there are smarter ways to solve it. Regards.

share|improve this answer
    
I want to be sure, I understand your answer. You first solve the homogeneous system $$ f(x) = 1_{A^c}(x)\sum\limits_{y\in \Omega}P(x,y)f(y). $$ Since the solution is not unique if there is an absorbing state, then the solution to the nonhomegous system is not uniquely determined. Did I understand correctly? Is it right to then infer that, if there is no absorbing state, showing that the solution is unique, amount to show that the homogenous system have a unique solution. That is it's determinant is different than zero. –  Nicolas Essis-Breton Sep 28 '11 at 17:32
    
Nicolas: beware that the first equation written in this post is not the same as yours and does not correspond to $f(x)=E_x(T)$. –  Did Sep 28 '11 at 17:51
    
I think Gortaur answer is applicable to my revised post. The equation he states at the beginning of his post is the same as mine except for the constant term $1$. –  Nicolas Essis-Breton Sep 28 '11 at 20:29
    
Nicolas: the same as [yours] except for the constant term 1... which makes all the difference! Maybe you do not realize this but in most cases (irreducible chain, nonempty $A$) the only solution to the equation written in this post is $f=0$ everywhere. Thus this tells you nothing about the rather different function $f(x)=E_x(T)$ you said you were interested in. –  Did Sep 29 '11 at 5:53
    
@NicolasEssis-Breton: My first answer was incorrect since I misunderstood the equation in your question. I apologize. I fixed it - so it may be not a complete answer, but rather some ideas on this topic. You may think of dis-accepting it, which may encourage other members to contribute - there should be people more familiar with the problem, or more experienced in arithmetic of infinities. –  Ilya Sep 29 '11 at 6:45
show 5 more comments

For the general case, the solution to

$$f(x)=0, x \in A \tag{1}$$ $$f(x)= 1+\sum_{y \in \Omega }P(x,y)f(y), x \notin A$$

is not unique. The probabilistic meaningfull solution is then given by the least nonnegative solution to the system. As explain in the document pointed by Gortaur http://www.statslab.cam.ac.uk/~james/Markov/s13.pdf.

If $P$ is irreducible, we can show the solution is unique as follow. Suppose $g$ is another solution to the system then $g \ne f$ and

$$g(x)=0, x \in A \tag{2}$$ $$g(x)= 1+\sum_{y \in \Omega }P(x,y)g(y), x \notin A$$

Susbtracting $(1)$ and $(2)$, we have

$$f(x)-g(x)=0, x \in A \tag{3}$$ $$f(x)-g(x)= \sum_{y \in \Omega }P(x,y)(f(y)-g(y)), x \notin A \tag{4}$$

By $(4)$, $f-g$ is harmonic for $P$ on $A^c=\Omega-A$. If $f-g$ is constant then by $(3)$, $f-g$ is identically zero and $f=g$, which is a contracdiction. Suppose $f-g$ is not constant. Since $f-g$ is harmonic on $A^c$ then it must attain its maximum and minimum value in $A$, by $(5)$ below. Hence, by $(3)$, $f-g$ is identically zero, which is a contradiction.

$(5)$: Maximum principle: Suppose $P$ is the transition matrix of an irreducible Markov chain, with finite state space $\Omega$. If $h$ is not constant and harmonic on $A\subset \Omega$, then $h$ achieves its maximum in $A^c$. A similar claim hold for the minimum of $h$.

share|improve this answer
    
Before you obtained (4), did you show that $f,g$ are finite on $A^c$? –  Ilya Oct 3 '11 at 12:36
    
@Gortaur: no, I assume that $f$ and $g$ are finite on $A^c$. I think this is the case, if all state of $A^c$ communicate, that is $A^c$ has no absorbing state. But I'm not sure. –  Nicolas Essis-Breton Oct 3 '11 at 19:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.