Mercurial > forge

changeset 9786:a4fc49a6c9d2 octave-forge

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
new example in documentation
author mmarzolla
date Mon, 19 Mar 2012 21:31:47 +0000
parents f83050d0b00d
children 8057449291c7
files main/queueing/doc/markovchains.txi main/queueing/inst/dtmc.m main/queueing/inst/dtmc_fpt.m main/queueing/inst/dtmc_mtta.m
diffstat 4 files changed, 156 insertions(+), 8 deletions(-) [+]
line wrap: on
line diff
--- a/main/queueing/doc/markovchains.txi	Mon Mar 19 16:31:21 2012 +0000
+++ b/main/queueing/doc/markovchains.txi	Mon Mar 19 21:31:47 2012 +0000
@@ -140,10 +140,77 @@
 
 @noindent @strong{EXAMPLE}
 
+This example is from [GrSn97]. Let us consider a maze with nine rooms,
+as shown in the following figure
+
 @example
 @group
++-----+-----+-----+
+|     |     |     |
+|  1     2     3  |
+|     |     |     |
++-   -+-   -+-   -+
+|     |     |     |
+|  4     5     6  |
+|     |     |     |
++-   -+-   -+-   -+
+|     |     |     |
+|  7     8     9  |
+|     |     |     |
++-----+-----+-----+
+@end group
+@end example
+
+A mouse is placed in one of the rooms and can wander around. At each
+step, the mouse moves to one of the neighboring rooms with equal
+probability: if it is in room 1, it van move to room 2 and 4 with
+probability 1/2. If the mouse is in room 8, it can move to either 7, 5
+or 9 with probability 1/3.
+
+The transition probability @math{\bf P} from room @math{i} to room
+@math{j} is the following:
+
+@iftex
+@tex
+$$ {\bf P} = 
+\pmatrix{ 0   & 1/2 & 0   & 1/2 & 0   & 0   & 0   & 0   & 0   \cr
+          1/3 & 0   & 1/3 & 0   & 1/3 & 0   & 0   & 0   & 0   \cr
+          0   & 1/2 & 0   & 0   & 0   & 1/2 & 0   & 0   & 0   \cr
+          1/3 & 0   & 0   & 0   & 1/3 & 0   & 1/3 & 0   & 0   \cr
+          0   & 1/4 & 0   & 1/4 & 0   & 1/4 & 0   & 1/4 & 0   \cr
+          0   & 0   & 1/3 & 0   & 1/3 & 0   & 0   & 0   & 1/3 \cr
+          0   & 0   & 0   & 1/2 & 0   & 0   & 0   & 1/2 & 0   \cr
+          0   & 0   & 0   & 0   & 1/3 & 0   & 1/3 & 0   & 1/3 \cr
+          0   & 0   & 0   & 0   & 0   & 1/2 & 0   & 1/2 & 0   }
+$$
+@end tex
+@end iftex
+@ifnottex
+@example
+@group
+        / 0     1/2   0     1/2   0     0     0     0     0   \
+        | 1/3   0     1/3   0     1/3   0     0     0     0   |
+        | 0     1/2   0     0     0     1/2   0     0     0   |
+        | 1/3   0     0     0     1/3   0     1/3   0     0   |
+    P = | 0     1/4   0     1/4   0     1/4   0     1/4   0   |
+        | 0     0     1/3   0     1/3   0     0     0     1/3 |
+        | 0     0     0     1/2   0     0     0     1/2   0   |
+        | 0     0     0     0     1/3   0     1/3   0     1/3 |
+        \ 0     0     0     0     0     1/2   0     1/2   0   /
+@end group
+@end example
+@end ifnottex
+
+The stationary state occupancy probability vector can be computed
+using the following code:
+
+@example
+@c @group
 @verbatiminclude @value{top_srcdir}/examples/demo_1_dtmc.m
-@end group
+@c @end group
+    @result{} 0.083333   0.125000   0.083333   0.125000   
+       0.166667   0.125000   0.083333   0.125000   
+       0.083333
 @end example
 
 @c
@@ -325,6 +392,30 @@
 @end example
 @end ifnottex
 
+According to the definition above, @math{M_{i,i} = 0}. We arbitrarily
+redefine @math{M_{i,i}} to be the @emph{mean recurrence time}
+@math{r_i} for state @math{i}, that is the average number of
+transitions needed to return to state @math{i} starting from
+it. @math{r_i} is defined as:
+
+@iftex
+@tex
+$$ r_i = {1 \over \pi_i} $$
+@end tex
+@end iftex
+@ifnottex
+@example
+@group
+        1
+r_i = -----
+      \pi_i
+@end group
+@end example
+@end ifnottex
+
+@noindent where @math{\pi_i} is the stationary probability of visiting state
+@math{i}.
+
 @DOCSTRING(dtmc_fpt)
 
 @c
--- a/main/queueing/inst/dtmc.m	Mon Mar 19 16:31:21 2012 +0000
+++ b/main/queueing/inst/dtmc.m	Mon Mar 19 21:31:47 2012 +0000
@@ -156,6 +156,35 @@
 %! p = dtmc(P);
 %! assert( p, [.0625 .25 .375 .25 .0625], 10*eps );
 
+## "Rat maze" problem (p. 441 of [GrSn97]);
+%!test
+%! P = zeros(9,9);
+%! P(1,[2 4]) = 1/2;
+%! P(2,[1 5 3]) = 1/3;
+%! P(3,[2 6]) = 1/2;
+%! P(4,[1 5 7]) = 1/3;
+%! P(5,[2 4 6 8]) = 1/4;
+%! P(6,[3 5 9]) = 1/3;
+%! P(7,[4 8]) = 1/2;
+%! P(8,[7 5 9]) = 1/3;
+%! P(9,[6 8]) = 1/2;
+%! p = dtmc(P);
+%! assert( p, [1/12 1/8 1/12 1/8 1/6 1/8 1/12 1/8 1/12], 10*eps );
+
+%!demo
+%! P = zeros(9,9);
+%! P(1,[2 4]    ) = 1/2;
+%! P(2,[1 5 3]  ) = 1/3;
+%! P(3,[2 6]    ) = 1/2;
+%! P(4,[1 5 7]  ) = 1/3;
+%! P(5,[2 4 6 8]) = 1/4;
+%! P(6,[3 5 9]  ) = 1/3;
+%! P(7,[4 8]    ) = 1/2;
+%! P(8,[7 5 9]  ) = 1/3;
+%! P(9,[6 8]    ) = 1/2;
+%! p = dtmc(P);
+%! disp(p)
+
 %!demo
 %! a = 0.2;
 %! b = 0.15;
--- a/main/queueing/inst/dtmc_fpt.m	Mon Mar 19 16:31:21 2012 +0000
+++ b/main/queueing/inst/dtmc_fpt.m	Mon Mar 19 21:31:47 2012 +0000
@@ -73,8 +73,7 @@
     error("Cannot compute first passage times for absorbing chains");
   endif
 
-  ## Source:
-  ## http://www.cs.virginia.edu/~gfx/Courses/2006/DataDriven/bib/texsyn/Chapter11.pdf
+  ## Source [GrSn97]
   w = dtmc(P); # steady state probability vector
   W = repmat(w,N,1);
   ## Z = (I - P + W)^-1 where W is the matrix where each row is the
@@ -100,8 +99,7 @@
 %! M = dtmc_fpt(P);
 %! assert( diag(M)', 1./p, 1e-8 );
 
-## Example on p. 461 of
-## http://www.cs.virginia.edu/~gfx/Courses/2006/DataDriven/bib/texsyn/Chapter11.pdf
+## Example on p. 461 of [GrSn97]
 %!test
 %! P = [ 0 1 0 0 0; \
 %!      .25 .0 .75 0 0; \
@@ -127,6 +125,21 @@
 %!   endfor
 %! endfor
 
+## "Rat maze" problem (p. 453 of [GrSn97]);
+%!test
+%! P = zeros(9,9);
+%! P(1,[2 4]) = .5;
+%! P(2,[1 5 3]) = 1/3;
+%! P(3,[2 6]) = .5;
+%! P(4,[1 5 7]) = 1/3;
+%! P(5,[2 4 6 8]) = 1/4;
+%! P(6,[3 5 9]) = 1/3;
+%! P(7,[4 8]) = .5;
+%! P(8,[7 5 9]) = 1/3;
+%! P(9,[6 8]) = .5;
+%! M = dtmc_fpt(P);
+%! assert( M(1:9 != 5,5)', [6 5 6 5 5 6 5 6], 10*eps );
+
 %!demo
 %! P = [ 0.0 0.9 0.1; \
 %!       0.1 0.0 0.9; \
--- a/main/queueing/inst/dtmc_mtta.m	Mon Mar 19 16:31:21 2012 +0000
+++ b/main/queueing/inst/dtmc_mtta.m	Mon Mar 19 21:31:47 2012 +0000
@@ -112,8 +112,8 @@
   ## Source: Grinstead, Charles M.; Snell, J. Laurie (July 1997). "Ch.
   ## 11: Markov Chains". Introduction to Probability. American
   ## Mathematical Society. ISBN 978-0821807491.
+  ## http://www.cs.virginia.edu/~gfx/Courses/2006/DataDriven/bib/texsyn/Chapter11.pdf
 
-  ## http://www.cs.virginia.edu/~gfx/Courses/2006/DataDriven/bib/texsyn/Chapter11.pdf
   tmpN = inv(eye(k) - P(tr,tr)); # matrix N = (I-Q)^-1
   N(tr,tr) = tmpN;
   R = P(tr,ab);
@@ -154,8 +154,7 @@
 %! assert( B(3,1), 0.5, 10*eps );
 %! assert( B(3,5), 0.5, 10*eps );
 
-## Example on p. 422 of
-## http://www.cs.virginia.edu/~gfx/Courses/2006/DataDriven/bib/texsyn/Chapter11.pdf
+## Example on p. 422 of [GrSn97]
 %!test
 %! P = dtmc_bd([0 .5 .5 .5 .5], [.5 .5 .5 .5 0]);
 %! [t N B] = dtmc_mtta(P);
@@ -230,3 +229,19 @@
 %! text(f*1.1,0.2,["Mean Time to Absorption (" num2str(f) ")"]);
 %! xlabel("Step number (n)");
 %! title("Probability of finishing the game before step n");
+
+## "Rat maze" problem (p. 453 of [GrSn97]);
+%!test
+%! P = zeros(9,9);
+%! P(1,[2 4]) = .5;
+%! P(2,[1 5 3]) = 1/3;
+%! P(3,[2 6]) = .5;
+%! P(4,[1 5 7]) = 1/3;
+%! P(5,:) = 0; P(5,5) = 1;
+%! P(6,[3 5 9]) = 1/3;
+%! P(7,[4 8]) = .5;
+%! P(8,[7 5 9]) = 1/3;
+%! P(9,[6 8]) = .5;
+%! t = dtmc_mtta(P);
+%! assert( t, [6 5 6 5 0 5 6 5 6], 10*eps );
+