Jump probability of a random walker

[grquanti]

Hello everybody.
I have a Markowian homogeneous random walk. Given the transition matrix of the chain, I know that

$P[ X(t) = i | X(t-1) = j ] ≡ P_{j→i}=T_{ij}$

where $T$ is the transition matrix and $X(t)$ is the position of the walker at time $t$.
Given this formula, I think the following two formulas hold:

$P[ X(t) ≠ j | X(t-1) = i ] = ∑_{k≠j} P_{i→k} = ∑_{k≠j} T_{ki}$

and

$P[X(t) = j | X(t-1) ≠ j ] = ∑_{i≠j} P_{i→j} P_{i}(t-1) = ∑_{i≠j} T_{ji} P_{i}(t-1)$

First of all: it is right?
However the most importat question is: what can I say about

$P[X(t) ≠ j | X(t-1) ≠ j ]$ ?

I think my question is quite general, however I let you note that: in my particular case, in a single time step the walker can:

• do a step of length 1 in the positive direction
• do a step of length 1 in the negative direction
• stay motionless (don't go anywhere, nor the negative nor the positive direction. It's 0-lenght step)

thanks.

 

[andrewkirk]

First of all: it is right?

That second one is not correct.
Taking a sum works for the first case because the events $X(t)=k$ for $k\neq j$ are disjoint for different values of $k$, so we can just add the probabilities. In the second case it is the conditional event $X(t-1)\neq j$ that has multiple parts and there is no theorem we can use about adding probabilities there.

To get a handle on what you need to do, try to write $P[A\ |\ B\cup C]$ in terms of $P[A|B],P[ B ],P[A|C]$ and $P[C]$ where $B$ and $C$ are disjoint events. You could then think of $A$ as the event $X(t)=j$ and $B$ and $C$ as the events $X(t-1)=j-1,\ X(t-1)=j+1$.

 

[mfb]

@andrewkirk: I don't understand the problem you have with the second expression. The initial probabilities are taken into account.
1->3 and 2->3 are disjoint events, for example, and you can sum their probabilities.

However the most importat question is: what can I say about

$P[X(t) ≠ j | X(t-1) ≠ j ]$ ?

Write down a 3x3 matrix (or larger) for T and see which transitions contribute. You can express it as double sum, but you can find a more compact expression.

 

[andrewkirk]

I don't understand the problem you have with the second expression. The initial probabilities are taken into account.
1->3 and 2->3 are disjoint events, for example, and you can sum their probabilities.

Certainly it is true that $X(t-1)=1\wedge X(t)=3$ and $X(t-1)=2\wedge X(t)=3$ are disjoint events. But the sum of their probabilities is $Pr(X(t)=3\wedge (X(t-1)\in\{1,2\})\ )$ not $Pr(X(t)=3\ |\ X(t-1)\in\{1,2\}\ )$. To get the latter we need to divide by $Pr(X(t-1)\in\{1,2\})$.

 

[grquanti]

You can express it as double sum, but you can find a more compact expression.

I think you are suggesting me this:

$P[ X(t) ≠ j | X(t-1) ≠ j ] = ∑_{i≠j}^{k≠j} P_{i→k}P_{i}(t) = ∑_{i≠j}^{k≠j} T_{ki}P_{i}(t)$

It seems reasonable to me, but am I ensured that this summation in not greater than 1?

try to write $P[A\ |\ B\cup C]$ in terms of $P[A|B],P[ B ],P[A|C]$ and $P[C]$ where $B$ and $C$ are disjoint events.

I would say

$P( A | B ∪ C ) = \frac{P(A | B )P(B) + P( A | C )P(C)}{P(B) + P(C)}$

Is it right?

 

[andrewkirk]

I would say

$P( A | B ∪ C ) = \frac{P(A | B )P(B) + P( A | C )P(C)}{P(B) + P(C)}$

Is it right?

Yes.

Now in what you've done above you have the numerator correct, but you have not divided by the denominator, as in this example you just did.
The denominator to divide by is
$$\sum_{k\neq j}P_k(t-1)$$

 

[mfb]

@andrewkirk: Ah you are right, I missed the part about the conditional probability.

It seems reasonable to me, but am I ensured that this summation in not greater than 1?

You know something about sums of T_ij.

 

[grquanti]

You know something about sums of Tij.

Yes, I know that

$∑_i T_{ij}=1 ∀ j$

but I have to do (at least, I think I have to do)

$∑_{i≠j}^{k≠j} T_{ki}P_i$

For sure, the summation over a single index is not greater than one, but here I have to do the summation over two index...

 

[mfb]

You can write it as explicit double sum, then it is easier to see which summation you can do first (as inequality if you just want to compare to 1). Afterwards you can use a similar equation for P_i to get rid of the remaining sum.

 

[grquanti]

Yes, you mean

$∑_{i≠j}^{k≠j} T_{ki}P_i = ∑_{i≠j} P_i ∑_{k≠j}T_{ki} ≤ ∑_{i}P_i = 1$

Thank you!

 

[mfb]

$$∑_{i≠j}^{k≠j} T_{ki}P_i = ∑_{i≠j} P_i ∑_{k≠j}T_{ki} ≤ ∑_{i\neq j}P_i \leq 1$$

 

[grquanti]

$∑_{i≠j}^{k≠j}T_{ki}P_i = ∑_{i≠j}P_i∑_{k≠j}T_{ki} ≤ ∑_{i≠j}P_i ≤ ∑_i P_i = 1$