I Jump probability of a random walker

Tags:
1. May 17, 2017

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 lenght 1 in the positive direction
• do a step of lenght 1 in the negative direction
• stay motionless (don't go anywhere, nor the negative nor the positive direction. It's 0-lenght step)
thanks.

2. May 17, 2017

andrewkirk

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$.

3. May 17, 2017

Staff: Mentor

@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.

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.

4. May 17, 2017

andrewkirk

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\})$.

5. May 18, 2017

grquanti

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?

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?

6. May 18, 2017

andrewkirk

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)$$

7. May 18, 2017

Staff: Mentor

@andrewkirk: Ah you are right, I missed the part about the conditional probability.
You know something about sums of Tij.

8. May 18, 2017

grquanti

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...

9. May 18, 2017

Staff: Mentor

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 Pi to get rid of the remaining sum.

10. May 18, 2017

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!

11. May 18, 2017

Staff: Mentor

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

12. May 22, 2017

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$