Difference between revisions of "Biomod/2011/Caltech/DeoxyriboNucleicAwesome/Random Walk Formula"

From OpenWetWare
Jump to: navigation, search
(Parameter Estimation)
(Cumulative Function)
 
(26 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
{{Template:DeoxyriboNucleicAwesomeHeader}}
 
{{Template:DeoxyriboNucleicAwesomeHeader}}
 +
__TOC__
 
=Random Walk Formula=
 
=Random Walk Formula=
__TOC__
+
 
==General Modeling Idea==
+
==Modeling Idea==
The random walk on DNA origami can be modeled as one dimensional random walk with a reflecting and an absorbing barrier (Figure 1). Tracks in the same column are grouped into rectangles, and each step is defined as walking from one rectangle to an adjacent one.  
+
The random walk on DNA origami can be modeled as one dimensional random walk with a reflecting and an absorbing barrier (Figure 1). Tracks in the same column are grouped into rectangles, and each step is defined as walking from one rectangle to an adjacent one. We are interested in expressing the probability of reaching the walker goal as a function of the number of steps taken.  
  
  
Line 12: Line 13:
 
[[Image:RW.bmp|thumb|center|800px|Figure 2. A line segment with N+1 distinct sites. The walker starts the random walk at i and is reflected at N with a probability of β. The random walk ends once it reaches site 0.  ]]
 
[[Image:RW.bmp|thumb|center|800px|Figure 2. A line segment with N+1 distinct sites. The walker starts the random walk at i and is reflected at N with a probability of β. The random walk ends once it reaches site 0.  ]]
  
==Random Walk Formula==
+
==General Approach==
 
Two assumptions are made in our case. 1) The DNA origami is immune to any free floating walkers in solution, meaning that free floating walkers cannot bind to an origami and starts random walking; 2) walkers are immediately absorbed when reaching the rectangles with WGs, despite the presence of two TR2 in the same rectangle.  
 
Two assumptions are made in our case. 1) The DNA origami is immune to any free floating walkers in solution, meaning that free floating walkers cannot bind to an origami and starts random walking; 2) walkers are immediately absorbed when reaching the rectangles with WGs, despite the presence of two TR2 in the same rectangle.  
  
Line 24: Line 25:
  
 
The generating function for <math>h(t;i)\!</math> can be expressed as  
 
The generating function for <math>h(t;i)\!</math> can be expressed as  
<div class="center" style="width:auto; margin-left:auto; margin-right:auto;"><math>H_i (s) = \sum_{t=0}^\infty h(t;1)s^t</math>, <math> |s| <1 \!</math></div>
+
<div class="center" style="width:auto; margin-left:auto; margin-right:auto;"><math>H_i (s) = \sum_{t=0}^\infty h(t;1)s^t,|s| <1 \!</math></div>
  
 
Following Netus (1963), the explicit expression of the generating function is  
 
Following Netus (1963), the explicit expression of the generating function is  
Line 38: Line 39:
 
The explicit expression of <math>h(t;i)\!</math> can thus be deduced from <math>H_i (s)\!</math> using partial fraction expansion (Feller, 1971).
 
The explicit expression of <math>h(t;i)\!</math> can thus be deduced from <math>H_i (s)\!</math> using partial fraction expansion (Feller, 1971).
  
Assume that <math>T_0 (s)\!</math> has <math>k\!</math> distinct roots <math>s_1,s_2,..., s_k , H_i (s)\!</math> can then be decomposed into partial fractions
+
Assume that <math>T_0 (s)\!</math> has <math>k\!</math> distinct roots <math>s_1,s_2,..., s_k . H_i (s)\!</math> can then be decomposed into partial fractions
 
<div class="center" style="width:auto; margin-left:auto; margin-right:auto;"><math> H_i (s) = \frac {\rho_1} {s-s_1} + \frac{\rho_2}{s-s_2} +...+ \frac {\rho_k}{s-s_k} \!</math></div>
 
<div class="center" style="width:auto; margin-left:auto; margin-right:auto;"><math> H_i (s) = \frac {\rho_1} {s-s_1} + \frac{\rho_2}{s-s_2} +...+ \frac {\rho_k}{s-s_k} \!</math></div>
  
Line 50: Line 51:
  
 
==Parameter Estimation==
 
==Parameter Estimation==
Possible positions of walkers on the origami can be grouped into two categories, either in the center of rectangles (Figure 2, Line 2) or at the sides (Figure 2, Lines 1&3), and the values of <math>p\!</math>, <math>q\!</math> and <math>r\!</math> are different in each category. Hence there is a need to find out the distribution of walkers in these two categories in order to estimate <math>p\!</math>, <math>q\!</math> and <math>r\!</math>. Due to the nature of our design, each walker has a probability of 50% to stay at its original track after one branch migration. Assuming no reflecting boundaries, when the walker is in the center (Figure 2, Line 2), the probability of staying in Line 2 after one branch migration is <math>\frac {1}{2}+\frac{1}{2} \times \frac{1}{2}=\frac{3}{4}</math>, while the probability of going to Lines 1 or 3 is <math>1- \frac{3}{4}=\frac{1}{4}</math>. Similarly, when it is in Lines 1 or 3, the probability of staying in the same line after one branch migration is <math>\frac{1}{2}+\frac{1}{2} \times \frac{2}{3}=\frac{5}{6}</math> while the probability of going to Line 2 is <math>1- \frac{5}{6}=\frac{1}{6}</math>. Here we assume no reflecting barrier in the system. The distribution of relative positions of walkers can be modeled using Markov chain as follows.
+
Possible positions of walkers on the origami can be grouped into two categories, either in the center of rectangles (Figure 1, Line 2) or at the sides (Figure 1, Lines 1&3), and the values of <math>p\!</math>, <math>q\!</math> and <math>r\!</math> are different in each category. Hence there is a need to find out the distribution of walkers in these two categories in order to estimate <math>p\!</math>, <math>q\!</math> and <math>r\!</math>. Assuming no reflecting boundaries, when the walker is in the center (Figure 1, Line 2), the probability of staying in Line 2 after one branch migration is <math>\frac {1}{2}\!</math>, while the probability of going to Lines 1 or 3 is <math>\frac{1}{2}\!</math>. Similarly, when it is in Lines 1 or 3, the probability of staying in the same line after one branch migration is <math>\frac{2}{3}\!</math> while the probability of going to Line 2 is <math>\frac{1}{3}\!</math>. Here we assume no reflecting barrier in the system. The distribution of relative positions of walkers can be modeled using Markov chain as follows.
  
Let <math>v(t) = (a, 1–a)\!</math> denote the proportion of walkers in Line 2 <math>(a)\!</math> and Lines 1&3 <math>(1–a)\!</math> after <math>t\!</math> branch migrations. Since all the walkers are planted in the center, <math>v(0) = (1, 0)\!</math>. Define the transition matrix  
+
Let <math>v(t) = (a, 1-a)\!</math> denote the proportion of walkers in Line 2 <math>(a)</math> and Lines 1&3 <math>(1-a)</math> after <math>t\!</math> branch migrations. Since all the walkers are initially planted in the center, <math>v(0) = (1, 0)\!</math>. Define the transition matrix  
  
 
<div class="center" style="width:auto; margin-left:auto; margin-right:auto;"><math> M = \begin{pmatrix}
 
<div class="center" style="width:auto; margin-left:auto; margin-right:auto;"><math> M = \begin{pmatrix}
  \frac{3}{4} & \frac{1}{4} \\
+
  1/2 & 1/2 \\
  \frac{1}{6} & \frac{5}{6}
+
  1/3 & 2/3
 
\end{pmatrix}. \!</math></div>
 
\end{pmatrix}. \!</math></div>
  
 
It follows that
 
It follows that
 
<div class="center" style="width:auto; margin-left:auto; margin-right:auto;"><math> v(t)=v(0). \underbrace{M.M.M...M}_{t} \!</math></div>
 
<div class="center" style="width:auto; margin-left:auto; margin-right:auto;"><math> v(t)=v(0). \underbrace{M.M.M...M}_{t} \!</math></div>
 +
 +
It was found that <math>\lim_{t \to \infty} v(t)= (0.4,0.6).</math>Hence at the stable state, 40% of the walkers are in Line 2 while 60% are in Lines 1 or 3. Since <math>v(4) = v(4) = (0.40007,0.59993)\!</math>, the distribution of relative positions of walkers on the origami stabilizes after approximately 4 branch migrations.
 +
 +
The overall probabilities <math>p, q, r, \alpha,\beta\!</math> can thus be calculated (Table 1).
 +
 +
 +
{| class="wikitable" border="1" cellpadding="2" style="text-align: center"
 +
|+ Table 1. Calculation of overall probabilities used in random walk modeling.
 +
!width="160"|
 +
!width="120"|<div class="center" style="width:auto; margin-left:auto; margin-right:auto;"><math>p\!</math></div>
 +
!width="120"|<math>q\!</math>
 +
!width="120"|<math>r\!</math>
 +
!width="120"|<math>\alpha\!</math>
 +
!width="120"|<math>\beta\!</math>
 +
|-
 +
|| Walkers at the center (Line 2) (40%) || <math>\frac{1}{4}</math>|| <math>\frac{1}{4}</math>|| <math>\frac{1}{2}</math>|| <math>\frac{2}{3}</math>|| <math>\frac{1}{3}</math>
 +
 +
|-
 +
|| Walkers at the sides (Lines 1 and 3) (60%) || <math>\frac{1}{3}</math>|| <math>\frac{1}{3}</math>|| <math>\frac{1}{3}</math>|| <math>\frac{1}{2}</math>|| <math>\frac{1}{2}</math>
 +
 +
|-
 +
|| Overall Probability|| <math>\frac{3}{10}</math>|| <math>\frac{3}{10}</math>|| <math>\frac{2}{5}</math>|| <math>\frac{17}{30}</math>|| <math>\frac{13}{30}</math>
 +
 +
|}
 +
 +
 +
Determination of the overall probabilities allow us to derive the explicit probability distribution functions for SP10, 22 and 34.
 +
 +
==Explicit Expression of Formulae==
 +
The explicit expression for the probability of reaching the walker goal (h(t;i)) as a function of the number of steps taken (t) can then be deduced using the general approach and the estimated parameters.
 +
 +
<math>SP10:  h(t;12)= \begin{cases} 0, 0\leqslant t < 12\\
 +
\frac{8.4287}{19.6975^{t+1}} - \frac{0.6389}{7.5119^{t+1}} +  \frac{0.0938}{5.4569^{t+1}} + \frac{0.0064}{1.0050^{t+1}} - \frac{0.0202}{1.0463^{t+1}} + \frac{0.0378}{1.1365^{t+1}} \\ \quad - \frac{0.0634}{1.2945^{t+1}} + \frac{0.1058}{1.5602^{t+1}} - \frac{0.1876}{2.0242^{t+1}} + \frac{0.3811}{2.9273^{t+1}} - \frac{1.0555}{5.1593^{t+1}} + \frac{8.7388}{16.5916^{t+1}}         
 +
,t \geqslant 12\end{cases}</math>
 +
 +
 +
<math>SP22:  h(t;8)= \begin{cases} 0, 0\leqslant t < 8\\
 +
-\frac{7.6854}{16.0673^{t+1}} + \frac{0.3265}{6.0382^{t+1}} +\frac{0.0143}{1.0111^{t+1}} -\frac{0.0484}{1.1067^{t+1}} +\frac{0.1051}{1.3413^{t+1}} -\frac{0.2323}{1.8564^{t+1}} +\frac{0.6577}{3.1862^{t+1}} -\frac{4.7287}{9.6237^{t+1}}         
 +
,t \geqslant 8\end{cases}</math>
 +
 +
 +
<math>SP34:  h(t;4)= \begin{cases} 0, 0\leqslant t < 4\\
 +
 +
\frac{5.4999}{11.0280^{t+1}} + \frac{0.05677}{1.0434^{t+1}} - \frac{0.2816}{1.5107^{t+1}} + \frac{2.0738}{4.2196^{t+1}}         
 +
,t \geqslant 4\end{cases}</math>
 +
 +
== Cumulative Function==
 +
The cumulative density function of <math>h(t;i)\!</math> can be computed and used to fit with SPEX experimental data.
 +
<div class="center" style="width:auto; margin-left:auto; margin-right:auto;"><math> C(t;i)= \sum_{t=0}^\infty h(t;i)\!</math></div>
 +
 +
A plot of  <math>C(t;i)\!</math> verses <math>t\!</math> can be used as a good model to fit the experimental data (Figure 3), where <math>C(t;i)</math> is the proportion of walkers that reach the walker goal and <math>t\!</math>  is the number of steps needed. It can be found that the number of steps needed for half of the walkers to reach WG decreases as we move SP nearer to the WG.
 +
 +
[[Image:Cumulative_RW.PNG|thumb|center|800px|Figure 3. A plot of the cumulative proportion of walkers reaching the walker goal versus number of steps. Blue, SP10. Green, SP22. Red, SP34. SP10 is the longest track, followed by SP22, while SP34 is the shortest.]]
 +
 +
==Number of Branch Migrations per Step==
 +
To further study the validity of this model, the number of branch migrations per step was calculated in order to obtain the average rate of branch migration.
 +
Let <math>P(x)\!</math> denote the probability of walking to the adjacent column after <math>x\!</math> branch migrations.
 +
 +
For walkers at the center line(Line 2),
 +
 +
<div class="center" style="width:auto; margin-left:auto; margin-right:auto;"><math>P(x) =\begin{cases} \frac {1} {2} \times ({\frac{2}{3}})^{\frac{x}{2}} \times ({\frac{1}{4}})^{\frac{x-2}{2}}, x=2,4,6,8,...\\
 +
  \frac {1}{2} \times ({\frac {2}{3}})^{\frac{x-1}{2}} \times ({\frac{1}{4}})^{\frac {x-1}{2}},x=1,3,5,7,...\end{cases} \!</math></div>
 +
 +
 +
For walkers at the sides (Lines 1 or 3),
 +
 +
<div class="center" style="width:auto; margin-left:auto; margin-right:auto;"><math>P(x) =\begin{cases} \frac {2} {3} \times ({\frac{1}{4}})^{\frac{x}{2}} \times ({\frac{2}{3}})^{\frac{x-2}{2}}, x=2,4,6,8,...\\
 +
  \frac {2}{3} \times ({\frac {1}{4}})^{\frac{x-1}{2}} \times ({\frac{2}{3}})^{\frac {x-1}{2}},x=1,3,5,7,...\end{cases} \!</math></div>
 +
 +
 +
The expected number of branch migrations in each case per step can hence be calculated as
 +
 +
<div class="center" style="width:auto; margin-left:auto; margin-right:auto;"><math>\sum_{x=1}^\infty xP(x),x=1,2,3,4,... \!</math></div>
 +
 +
It follows that the expected number of branch migrations per step is <math>\frac{9}{5}\!</math> and <math>\frac{8}{5}</math> for walkers at the center and sides, respectively.
 +
 +
Taking into account that 40% of walkers are in Line 2 while 60% are in Lines 1 and 3, the overall number of branch migrations per step is thus
 +
<div class="center" style="width:auto; margin-left:auto; margin-right:auto;"><math>40% \times \frac{9}{5} + 60% \times \frac{8}{5} = 1.68</math></div>
  
 
=References=
 
=References=

Latest revision as of 05:20, 2 November 2011

DeoxyriboNucleicAwesomeHeader.jpg

Saturday, December 16, 2017

Home

Members

Project

Protocols

Progress

Discussion

References


Random Walk Formula

Modeling Idea

The random walk on DNA origami can be modeled as one dimensional random walk with a reflecting and an absorbing barrier (Figure 1). Tracks in the same column are grouped into rectangles, and each step is defined as walking from one rectangle to an adjacent one. We are interested in expressing the probability of reaching the walker goal as a function of the number of steps taken.


Figure 1. Modeling the random walk on DNA origami as one dimensional random walk. Cyan, markers. Blue, Track 1. Red, Track 2. White, DNA staples only. Five-pointed star, walker goal. Each step is modeled as walking from one rectangle to an adjacent one. SP 10, 22, 34 indicate different starting positions. Note that in the cases of SP22 and SP34, there are no tracks to the left of starting positions.

Consider a random walk on a line segment with N+1 sites denoted by integers (0,1,2, … , N) (Figure 2). The walker starts random walk at site i, 0 < i ≤ N. Let p be the probability for the walker to move one segment to the left, q be the probability for the walker to move one segment to the right. The probability for the walker to stay at a particular site for the next unit time is thus r = 1 – p – q. When the walker reaches site N, the partially reflecting barrier, it has a probability of β to be reflected back to site N – 1, and a probability of α = 1 – β to stay at site N in the next unit time. When reaching site 0, the absorbing barrier, it stays there for 100% probability and the random walk ends.

Figure 2. A line segment with N+1 distinct sites. The walker starts the random walk at i and is reflected at N with a probability of β. The random walk ends once it reaches site 0.

General Approach

Two assumptions are made in our case. 1) The DNA origami is immune to any free floating walkers in solution, meaning that free floating walkers cannot bind to an origami and starts random walking; 2) walkers are immediately absorbed when reaching the rectangles with WGs, despite the presence of two TR2 in the same rectangle.

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle h(t;i)\!} be the probability that the walker reaches 0 for the first time after Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle t\!} steps given its starting position being Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle i\!} . Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle h(t;i)\!} obeys the following difference equation

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle h(t;i) = q·h(t-1;i-1) + r·h(t-1;i) + p·h(t-1; i + 1)\!}

for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle t = 1,2,3,...\!} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle i = 1,2,3,...,N-1\!} . We define Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle h(t;0)= 1\!} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle if\!} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle t = 0\!} ; Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle h(t;0)= 0\!} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle if\!} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle t > 0\!} . Also, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle h(t;i) = 0\!} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle for\!} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle t < i\!} .

When Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle i = N\!} we have

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle h(t;N) = αh(t-1;N)+ βh(t-1; N-1) \!}

The generating function for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle h(t;i)\!} can be expressed as

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle H_i (s) = \sum_{t=0}^\infty h(t;1)s^t,|s| <1 \!}

Following Netus (1963), the explicit expression of the generating function is

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle H_i (s) =\begin{cases} \frac {q^i s^i T_i (s)} {T_0 (s)}, 0\leqslant i < N\\ \frac {\beta q^{N-1} s^N (\lambda_1 - \lambda_2)} {T_0 (s)},i=N\end{cases}\!}

where

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle T_i (s) = (1-\alpha s)(\lambda_1 ^{N-i}-\lambda_2 ^{N-i})-\beta p s^2 (\lambda_1 ^{N-i-1}-\lambda_2 ^{N-i-1})\!}

and

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \lambda_{1,2} = \frac {1} {2} ( \pm \sqrt{{(1-rs)}^2-4 p q s^2} +1-rs ).\!}

The explicit expression of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle h(t;i)\!} can thus be deduced from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle H_i (s)\!} using partial fraction expansion (Feller, 1971).

Assume that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle T_0 (s)\!} has Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle k\!} distinct roots Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle s_1,s_2,..., s_k . H_i (s)\!} can then be decomposed into partial fractions

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle H_i (s) = \frac {\rho_1} {s-s_1} + \frac{\rho_2}{s-s_2} +...+ \frac {\rho_k}{s-s_k} \!}

where

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \rho_k = \frac {-q^i {s_m}^i T_i (S_m)}{{T_0}^' (s_m)}, m\leqslant k \!}

It follows that

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle h(t;i) = \sum_{m=1}^k \frac {\rho_m}{{s_m}^{t+1}} \!}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle h(t;N)\!} can be similarly deduced from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle H_N (s)\!} using the same method.

Parameter Estimation

Possible positions of walkers on the origami can be grouped into two categories, either in the center of rectangles (Figure 1, Line 2) or at the sides (Figure 1, Lines 1&3), and the values of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle p\!} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle q\!} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle r\!} are different in each category. Hence there is a need to find out the distribution of walkers in these two categories in order to estimate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle p\!} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle q\!} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle r\!} . Assuming no reflecting boundaries, when the walker is in the center (Figure 1, Line 2), the probability of staying in Line 2 after one branch migration is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \frac {1}{2}\!} , while the probability of going to Lines 1 or 3 is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \frac{1}{2}\!} . Similarly, when it is in Lines 1 or 3, the probability of staying in the same line after one branch migration is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \frac{2}{3}\!} while the probability of going to Line 2 is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \frac{1}{3}\!} . Here we assume no reflecting barrier in the system. The distribution of relative positions of walkers can be modeled using Markov chain as follows.

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle v(t) = (a, 1-a)\!} denote the proportion of walkers in Line 2 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle (a)} and Lines 1&3 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle (1-a)} after Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle t\!} branch migrations. Since all the walkers are initially planted in the center, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle v(0) = (1, 0)\!} . Define the transition matrix

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle M = \begin{pmatrix} 1/2 & 1/2 \\ 1/3 & 2/3 \end{pmatrix}. \!}

It follows that

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle v(t)=v(0). \underbrace{M.M.M...M}_{t} \!}

It was found that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \lim_{t \to \infty} v(t)= (0.4,0.6).} Hence at the stable state, 40% of the walkers are in Line 2 while 60% are in Lines 1 or 3. Since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle v(4) = v(4) = (0.40007,0.59993)\!} , the distribution of relative positions of walkers on the origami stabilizes after approximately 4 branch migrations.

The overall probabilities Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle p, q, r, \alpha,\beta\!} can thus be calculated (Table 1).


Table 1. Calculation of overall probabilities used in random walk modeling.
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle p\!}
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle q\!} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle r\!} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \alpha\!} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \beta\!}
Walkers at the center (Line 2) (40%) Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \frac{1}{4}} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \frac{1}{4}} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \frac{1}{2}} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \frac{2}{3}} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \frac{1}{3}}
Walkers at the sides (Lines 1 and 3) (60%) Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \frac{1}{3}} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \frac{1}{3}} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \frac{1}{3}} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \frac{1}{2}} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \frac{1}{2}}
Overall Probability Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \frac{3}{10}} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \frac{3}{10}} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \frac{2}{5}} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \frac{17}{30}} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \frac{13}{30}}


Determination of the overall probabilities allow us to derive the explicit probability distribution functions for SP10, 22 and 34.

Explicit Expression of Formulae

The explicit expression for the probability of reaching the walker goal (h(t;i)) as a function of the number of steps taken (t) can then be deduced using the general approach and the estimated parameters.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle SP10: h(t;12)= \begin{cases} 0, 0\leqslant t < 12\\ \frac{8.4287}{19.6975^{t+1}} - \frac{0.6389}{7.5119^{t+1}} + \frac{0.0938}{5.4569^{t+1}} + \frac{0.0064}{1.0050^{t+1}} - \frac{0.0202}{1.0463^{t+1}} + \frac{0.0378}{1.1365^{t+1}} \\ \quad - \frac{0.0634}{1.2945^{t+1}} + \frac{0.1058}{1.5602^{t+1}} - \frac{0.1876}{2.0242^{t+1}} + \frac{0.3811}{2.9273^{t+1}} - \frac{1.0555}{5.1593^{t+1}} + \frac{8.7388}{16.5916^{t+1}} ,t \geqslant 12\end{cases}}


Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle SP22: h(t;8)= \begin{cases} 0, 0\leqslant t < 8\\ -\frac{7.6854}{16.0673^{t+1}} + \frac{0.3265}{6.0382^{t+1}} +\frac{0.0143}{1.0111^{t+1}} -\frac{0.0484}{1.1067^{t+1}} +\frac{0.1051}{1.3413^{t+1}} -\frac{0.2323}{1.8564^{t+1}} +\frac{0.6577}{3.1862^{t+1}} -\frac{4.7287}{9.6237^{t+1}} ,t \geqslant 8\end{cases}}


Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle SP34: h(t;4)= \begin{cases} 0, 0\leqslant t < 4\\ \frac{5.4999}{11.0280^{t+1}} + \frac{0.05677}{1.0434^{t+1}} - \frac{0.2816}{1.5107^{t+1}} + \frac{2.0738}{4.2196^{t+1}} ,t \geqslant 4\end{cases}}

Cumulative Function

The cumulative density function of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle h(t;i)\!} can be computed and used to fit with SPEX experimental data.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle C(t;i)= \sum_{t=0}^\infty h(t;i)\!}

A plot of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle C(t;i)\!} verses Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle t\!} can be used as a good model to fit the experimental data (Figure 3), where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle C(t;i)} is the proportion of walkers that reach the walker goal and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle t\!} is the number of steps needed. It can be found that the number of steps needed for half of the walkers to reach WG decreases as we move SP nearer to the WG.

Figure 3. A plot of the cumulative proportion of walkers reaching the walker goal versus number of steps. Blue, SP10. Green, SP22. Red, SP34. SP10 is the longest track, followed by SP22, while SP34 is the shortest.

Number of Branch Migrations per Step

To further study the validity of this model, the number of branch migrations per step was calculated in order to obtain the average rate of branch migration. Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle P(x)\!} denote the probability of walking to the adjacent column after Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle x\!} branch migrations.

For walkers at the center line(Line 2),

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle P(x) =\begin{cases} \frac {1} {2} \times ({\frac{2}{3}})^{\frac{x}{2}} \times ({\frac{1}{4}})^{\frac{x-2}{2}}, x=2,4,6,8,...\\ \frac {1}{2} \times ({\frac {2}{3}})^{\frac{x-1}{2}} \times ({\frac{1}{4}})^{\frac {x-1}{2}},x=1,3,5,7,...\end{cases} \!}


For walkers at the sides (Lines 1 or 3),

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle P(x) =\begin{cases} \frac {2} {3} \times ({\frac{1}{4}})^{\frac{x}{2}} \times ({\frac{2}{3}})^{\frac{x-2}{2}}, x=2,4,6,8,...\\ \frac {2}{3} \times ({\frac {1}{4}})^{\frac{x-1}{2}} \times ({\frac{2}{3}})^{\frac {x-1}{2}},x=1,3,5,7,...\end{cases} \!}


The expected number of branch migrations in each case per step can hence be calculated as

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \sum_{x=1}^\infty xP(x),x=1,2,3,4,... \!}

It follows that the expected number of branch migrations per step is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \frac{9}{5}\!} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \frac{8}{5}} for walkers at the center and sides, respectively.

Taking into account that 40% of walkers are in Line 2 while 60% are in Lines 1 and 3, the overall number of branch migrations per step is thus

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle 40% \times \frac{9}{5} + 60% \times \frac{8}{5} = 1.68}

References

  • Ahmed El-Shehawy (1992). On absorption probabilities for a random walk between two different barriers. Annals De La Faculte Des Sciences De Toulouse, 1(1), 95-103.
  • Feller, W. (1971). An introduction to probability theory and its applications.
  • Netus, M. (1963). Absorption probabilities for a random walk between a reflecting and an absorbing barrier. Bull. Soc. Math. Belgique, 15, 253-258.