Transcript Random Walk

Random Walks
Presented By Cindy Xiaotong Lin
Why Random Walks?


A random walk (RW) is a useful model in
understanding stochastic processes across
a variety of scientific disciplines.
Random walk theory supplies the basic
probability theory behind BLAST ( the most
widely used sequence alignment theory).
What is a Random Walk?

An Intuitive understanding: A series of
movement which direction and size are randomly
decided (e.g., the path a drunk person left behind).

Formal Definition: Let X a fixed vector in the
d-dimensional Euclidean space R d and X , n  1 a
sequence of independent, identically distributed (i.i.d.)
real-valued random variables in R d. The discrete-time
stochastic process S  S n : n  1 defined by
0
n
Sn  X 0  X1   X n
is called a d-dimensional random walk
Definitions (cont.)

If X 0 and RVs X n take values in I d ,
then S , n  1
is called d-dimensional
lattice random walk.
In the lattice walk
 case, if we only allow
the jump from X  ( x ,..., x ) to Y  ( x   ,..., x  
where
 k  1 or  1 , then the
process is called d-dimensional sample
random walk.
n

1
1
d
1
1
d
d
)
Definitions (cont.)
A random walk is defined as restricted
walk if the walk is limited to the interval
[a, b].
The endpoints a and b are called
absorbing barriers if the random walk
eventually stays there forever;
or reflecting barriers if the walk reaches
the endpoint and bounces back.
Example: sequence alignment modeled as RW
| | | ||| ||
|||
ggagactgtagacagctaatgctata
gaacgccctagccacgagcccttatc
Simple scoring schemes:
at a position: +1, same nucleotides
-1, different nucleotides
*
Example (cont.): simple RW
Ladder point
Ladder Point (LP):the point in the walk lower
than any previously reached points.
Excursion: the part of the walk from a LP until
the highest point attained before the next LP.
Excursions in Fig: 1, 1, 4, 0, 0, 0, 3;
BLAST theory focused on the maximum heights
achieved by these excursions.
Example (cont.): General RW

Consider arbitrary scoring scheme
(e.g. substitution matrix)
Primary Study of RW: 1-d simple RW
RW: Consider a 1-d simple RW starting at h,
restricted to the interval [a, b], where a
and b are absorbing barriers,
Pr( X  1)  p and Pr( X  1)  q
n
n
Problems: I. (Absorption Probabilities) what is the
probability that eventually the walk
finishes at b (or a) rather than a (or
b), i.e.,  h (or u h )?
II. What is the mean number of steps
taken until the walk stops ( mh )?
Methods


The Difference Equation Approach
 Classical
The Moment-Generating Function Approach
 Ready to generate to more complicate
walk
Difference Equation Approach (M1)
Assume:  h the probability that the simple
random walk eventually finishes (absorbed)
at b.
Difference Equation obtained by comparing
the situation just before and after the first
step of the walk:
(7.4)
 h  p h1  q h1
Initial Conditions:
 a  0, b  1
(7.5)
M1 (cont.): solutions

Solve Equ 7.4, using the theory of homogeneous
difference equations
when p  q :
h 

 *h
e
 *b
e
 *a
e
 *a
e
 *  log
q
p
The same procedure can be used to obtain the
probability that the walk ends at a,
uh 
 *b
e
 *b
e
 *h
e
 *a
e
M1 (cont.): mean number of steps mh

Difference Equation:
mh  1  pmh1  qmh1

Initial Conditions:

Solution:
ma  mb  0
 *h
 *a
ha ba e e
mh 

 *b
 *a
q p q p e e
Moment-Generating function Approach (M2)

Recall the definition of mgf of a random variable Y:
m( )  E (eY )   e PY ( y )
y
y

In our case, mgf of random variable X n
is:
m( )  qe   pe

According to Theorem 1.1, there exists a unique
nonzero value  * of  such that
m( * )  1
(7.12)
M2 (cont.)

The mgf of the total displacement after N steps is from
(2.17)
(qe

 *
* N
 pe )  1, ( N  0)
When the walk has just finished, the total displacement is
either
bh
or a  h with the probabilities of
h
or u h respectively:

 he
( b  h ) *
a  (1  h )e
( a  h ) *
1
M2 (cont.)
Therefore, we have
 he
( b  h ) *
Thus,
h 
a  (1   h )e
( a  h ) *
e h
*
 e a
*
e b
*
 e a
*
1
Which is identical to (7.9), the solution from
difference equation approach.
M2(cont.): Mean number of steps
until the walk stops
Assume the total displacement after N steps is
TN 

N
j 1
S
j
Theorem 7.1(Wald’s Identity) states:
E ( m( )  N eTN )  1
Derivative with respect to 
E (TN )  E ( S )m h
on both sides, and obtain
M2(cont.)

In E (TN )  E ( S )m h
,
The mean of displacement in N steps
(7.24)
E (TN )   h (b  h)  uh (a  h)
The mean of step size
E (S )  p  q

Which states: the mean value of the final total
displacement of the walk, is the mean size of each
step multipled by the mean number of steps taken
until the walk stops
M2(cont.)

The mean of number of steps until the walk
stops,
uh (a  h)   h (b  h)
mh 
pq
Which is agree with the result from
difference equation approach
An Asymptotic case:
a walk BLAST concerns
The walks BLAST concerns are,

h  0; a  1; b  
a walk without upper boundary and ending at -1.
Applying the previous results and b  
We get the following Asymptotic results:



The probability distribution of the maximum value
that the walk ever achieves before reaching -1 is in
the form of the geometric-like probability.
The mean number of steps until the walk stops,
m0 
1
q p
General Walk
Suppose generally the possible step sizes are,
and their respective
 c,c  1,...,0,..., d  1, d
probabilities are, p c , p c 1,..., pd


The mean of step size is negative, i.e.,
E (S ) 
d

j c

jp j  0
The mgf of S(step size) is,
m( ) 
d

j c
p j e j
General Walk (cont.)

According to Theorem 1.1, there exists unique
positive  * , such that,
d

j c

p je
j *
1
To consider the walk that start at 0, with stopping
boundary at -1 and without upper boundary, impose
an artificial barrier at y  0
The possible stopping points can be,
 c,c  1,..., y,..., y  d  1.

And Wald’s Identity states,
E(e T )  1 where, TN is the total displacement
when the walk stops.
*
N
General Walk

Thus,
1
Pe
k c
k
k
*

y  d 1

ky
Pk e
k *
1
Where, Pk is the probability that the walk
finishes at the point k.
The mean of number of steps until the walk
stops A or m0 would be
jR j

E (T N )
j 1
A

E ( S )  d jp j
j c
c
General Walk: unrestricted


Objective: Find the probability distribution of the
maximum value that the walk ever achieves before
reaching -1 or lower.
Define:


the probability that in the unrestricted walk,
the maximum upward excursion is y or less;
Qk
is the probability that the walk visits the
positive value k before reaching any other positive
value.
FYu n r ( y )
General Walk: unrestricted

Therefore,
y
_
FYu n r ( y )  Q   Qk FYu n r ( y  k );
k 0
_
Q  1  Q1  Q2  ...  Qd
The event that in the unrestricted walk the maximum upward excursion is y or less is
the union of the event that the maximum excursion never reaches positive values and
the events the first positive value achieved by the excursion is k, k=1,2,…y, then the
walk never achieves a further height exceeding y-k

Applying the Renewal Theorem,
lim (1  FYu n r ( y )) e
y  
_
V  f (Q, Qk ,  * )
y *
V,
we have,
General Walk: restricted
Consider general walk starting at 0, lower barrier at -1.
The size of an excursion of the unrestricted walk can
exceed the value y either before or after reaching
negative value, i.e.,
c
F *Yunr ( y)  F *Y ( y)   R j F *Yunr ( y  j )
j  1
Where, F Y ( y ) the probability that the size of an
excursion in the restricted walks exceeds the value
up y. R j is the probability that the first negative
value reached by the walk is j .
*
General Walk: restricted

Then,
FY ( y )  Pr(Y  y ) ~ Ce
*
c
_
C
Q (1   R j e
 j *
 y *
)
j 1
(1  e

*
d
)(  kQk e
k 1
k *
)
,
Application: BLAST


BLAST is the most frequently used method for
assessing which DNA or protein sequences in a large
database have significant similarity to a given query
sequence;
a procedure that searches for high-scoring local
alignments between sequences and then tests for
significance of the scores found via P-value.
The null hypothesis to be test is that for each
aligned pair of animo acids, the two amino acids
were generated by independent mechanism.
BLAST (cont.) : modeling


The positions in the alignment are numbered from
left to right as 1, 2,…, N. A score S(j, k) is allocated
to each position where the aligned amino acid pair
(j,k) is observed, where S(j,k) is the (j,k) element in
the substitution matrix chosen.
An accumulated score at position i is calculated as
the sum of the scores for the various amino acid
comparison at position 1, 2,…,i. As i increases, the
accumulated score undergoes a random walk.
BLAST (cont.) : calculating parameters


Let Y1, Y2,… be the respective maximum heights of the
excursions of this walk after leaving one ladder point
and before arriving the next, and let Ymax be the
maximum of these maxima. It is in effect the test
statistic used in BLAST. So it is necessary to find its null
hypothesis distribution.
The asymptotic probability distribution of any Yi is
shown to be the geometric-like distribution. The values
*
of C and
in thisdistribution depend on the
substitution matrix used and the amino acid frequencies
{pj} and {pj’}. The probability distribution of Ymax also
depends on n, the mean number of ladder points in the
walk.
Discussion

???