Menu
▾
▴
[Octave-cvsupdate] SF.net SVN: octave:[10178] trunk/octave-forge/main/queueing/doc
|
From: <mma...@us...> - 2012-04-09 12:55:47
|
Revision: 10178
http://octave.svn.sourceforge.net/octave/?rev=10178&view=rev
Author: mmarzolla
Date: 2012-04-09 12:55:37 +0000 (Mon, 09 Apr 2012)
Log Message:
-----------
modifications
Removed Paths:
-------------
trunk/octave-forge/main/queueing/doc/queueing.html
trunk/octave-forge/main/queueing/doc/queueing.pdf
Deleted: trunk/octave-forge/main/queueing/doc/queueing.html
===================================================================
--- trunk/octave-forge/main/queueing/doc/queueing.html 2012-04-09 12:50:58 UTC (rev 10177)
+++ trunk/octave-forge/main/queueing/doc/queueing.html 2012-04-09 12:55:37 UTC (rev 10178)
@@ -1,6038 +0,0 @@
-<html lang="en">
-<head>
-<title>queueing</title>
-<meta http-equiv="Content-Type" content="text/html">
-<meta name="description" content="User manual for the queueing toolbox, a GNU Octave package for queueing networks and Markov chains analysis. This package supports single-station queueing systems, queueing networks and Markov chains. The queueing toolbox implements, among others, the Mean Value Analysis (MVA) and convolution algorithms for product-form queueing networks. Transient and steady-state analysis of Markov chains is also implemented.">
-<meta name="generator" content="makeinfo 4.13">
-<link title="Top" rel="top" href="#Top">
-<link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
-<meta http-equiv="Content-Style-Type" content="text/css">
-<style type="text/css"><!--
- pre.display { font-family:inherit }
- pre.format { font-family:inherit }
- pre.smalldisplay { font-family:inherit; font-size:smaller }
- pre.smallformat { font-family:inherit; font-size:smaller }
- pre.smallexample { font-size:smaller }
- pre.smalllisp { font-size:smaller }
- span.sc { font-variant:small-caps }
- span.roman { font-family:serif; font-weight:normal; }
- span.sansserif { font-family:sans-serif; font-weight:normal; }
---></style>
-</head>
-<body>
-Copyright © 2008, 2009, 2010, 2011, 2012 Moreno Marzolla.
-
- <p>Permission is granted to make and distribute verbatim copies of
-this manual provided the copyright notice and this permission notice
-are preserved on all copies.
-
- <p>Permission is granted to copy and distribute modified versions of
-this manual under the conditions for verbatim copying, provided that
-the entire resulting derived work is distributed under the terms of
-a permission notice identical to this one.
-
- <p>Permission is granted to copy and distribute translations of this
-manual into another language, under the above conditions for
-modified versions.
-
-<div class="contents">
-<h2>Table of Contents</h2>
-<ul>
-<li><a name="toc_Top" href="#Top">queueing</a>
-<li><a name="toc_Summary" href="#Summary">1 Summary</a>
-<ul>
-<li><a href="#About-the-Queueing-Toolbox">1.1 About the Queueing Toolbox</a>
-<li><a href="#Contributing-Guidelines">1.2 Contributing Guidelines</a>
-<li><a href="#Acknowledgements">1.3 Acknowledgements</a>
-</li></ul>
-<li><a name="toc_Installation" href="#Installation">2 Installing the queueing toolbox</a>
-<ul>
-<li><a href="#Installation-through-Octave-package-management-system">2.1 Installation through Octave package management system</a>
-<li><a href="#Manual-installation">2.2 Manual installation</a>
-<li><a href="#Development-sources">2.3 Development sources</a>
-<li><a href="#Using-the-queueing-toolbox">2.4 Using the queueing toolbox</a>
-</li></ul>
-<li><a name="toc_Markov-Chains" href="#Markov-Chains">3 Markov Chains</a>
-<ul>
-<li><a href="#Discrete_002dTime-Markov-Chains">3.1 Discrete-Time Markov Chains</a>
-<ul>
-<li><a href="#State-occupancy-probabilities-_0028DTMC_0029">3.1.1 State occupancy probabilities</a>
-<li><a href="#Birth_002ddeath-process-_0028DTMC_0029">3.1.2 Birth-death process</a>
-<li><a href="#Expected-number-of-visits-_0028DTMC_0029">3.1.3 Expected Number of Visits</a>
-<li><a href="#Time_002daveraged-expected-sojourn-times-_0028DTMC_0029">3.1.4 Time-averaged expected sojourn times</a>
-<li><a href="#Mean-time-to-absorption-_0028DTMC_0029">3.1.5 Mean Time to Absorption</a>
-<li><a href="#First-passage-times-_0028DTMC_0029">3.1.6 First Passage Times</a>
-</li></ul>
-<li><a href="#Continuous_002dTime-Markov-Chains">3.2 Continuous-Time Markov Chains</a>
-<ul>
-<li><a href="#State-occupancy-probabilities-_0028CTMC_0029">3.2.1 State occupancy probabilities</a>
-<li><a href="#Birth_002ddeath-process-_0028CTMC_0029">3.2.2 Birth-Death Process</a>
-<li><a href="#Expected-sojourn-times-_0028CTMC_0029">3.2.3 Expected Sojourn Times</a>
-<li><a href="#Time_002daveraged-expected-sojourn-times-_0028CTMC_0029">3.2.4 Time-Averaged Expected Sojourn Times</a>
-<li><a href="#Mean-time-to-absorption-_0028CTMC_0029">3.2.5 Mean Time to Absorption</a>
-<li><a href="#First-passage-times-_0028CTMC_0029">3.2.6 First Passage Times</a>
-</li></ul>
-</li></ul>
-<li><a name="toc_Single-Station-Queueing-Systems" href="#Single-Station-Queueing-Systems">4 Single Station Queueing Systems</a>
-<ul>
-<li><a href="#The-M_002fM_002f1-System">4.1 The M/M/1 System</a>
-<li><a href="#The-M_002fM_002fm-System">4.2 The M/M/m System</a>
-<li><a href="#The-M_002fM_002finf-System">4.3 The M/M/inf System</a>
-<li><a href="#The-M_002fM_002f1_002fK-System">4.4 The M/M/1/K System</a>
-<li><a href="#The-M_002fM_002fm_002fK-System">4.5 The M/M/m/K System</a>
-<li><a href="#The-Asymmetric-M_002fM_002fm-System">4.6 The Asymmetric M/M/m System</a>
-<li><a href="#The-M_002fG_002f1-System">4.7 The M/G/1 System</a>
-<li><a href="#The-M_002fHm_002f1-System">4.8 The M/H_m/1 System</a>
-</li></ul>
-<li><a name="toc_Queueing-Networks" href="#Queueing-Networks">5 Queueing Networks</a>
-<ul>
-<li><a href="#Introduction-to-QNs">5.1 Introduction to QNs</a>
-<ul>
-<li><a href="#Introduction-to-QNs">5.1.1 Single class models</a>
-<li><a href="#Introduction-to-QNs">5.1.2 Multiple class models</a>
-<li><a href="#Introduction-to-QNs">5.1.3 Closed Network Example</a>
-<li><a href="#Introduction-to-QNs">5.1.4 Open Network Example</a>
-</li></ul>
-<li><a href="#Algorithms-for-Product_002dForm-QNs">5.2 Algorithms for Product-Form QNs</a>
-<ul>
-<li><a href="#Algorithms-for-Product_002dForm-QNs">5.2.1 Jackson Networks</a>
-<li><a href="#Algorithms-for-Product_002dForm-QNs">5.2.2 The Convolution Algorithm</a>
-<li><a href="#Algorithms-for-Product_002dForm-QNs">5.2.3 Open networks</a>
-<li><a href="#Algorithms-for-Product_002dForm-QNs">5.2.4 Closed Networks</a>
-<li><a href="#Algorithms-for-Product_002dForm-QNs">5.2.5 Mixed Networks</a>
-</li></ul>
-<li><a href="#Algorithms-for-non-Product_002dForm-QNs">5.3 Algorithms for non Product-Form QNs</a>
-<li><a href="#Generic-Algorithms">5.4 Generic Algorithms</a>
-<li><a href="#Bounds-on-performance">5.5 Bounds on performance</a>
-<li><a href="#Utility-functions">5.6 Utility functions</a>
-<ul>
-<li><a href="#Utility-functions">5.6.1 Open or closed networks</a>
-<li><a href="#Utility-functions">5.6.2 Computation of the visit counts</a>
-<li><a href="#Utility-functions">5.6.3 Other utility functions</a>
-</li></ul>
-</li></ul>
-<li><a name="toc_References" href="#References">6 References</a>
-<li><a name="toc_Copying" href="#Copying">Appendix A GNU GENERAL PUBLIC LICENSE</a>
-<li><a name="toc_Concept-Index" href="#Concept-Index">Concept Index</a>
-<li><a name="toc_Function-Index" href="#Function-Index">Function Index</a>
-<li><a name="toc_Author-Index" href="#Author-Index">Author Index</a>
-</li></ul>
-</div>
-
-<div class="node">
-<a name="Top"></a>
-<p><hr>
-Next: <a rel="next" accesskey="n" href="#Summary">Summary</a>,
-Up: <a rel="up" accesskey="u" href="#dir">(dir)</a>
-
-</div>
-
-<h2 class="unnumbered">queueing</h2>
-
-<p>This manual documents how to install and run the Queueing Toolbox.
-It corresponds to version 1.1.0 of the package.
-
-<!-- -->
-<ul class="menu">
-<li><a accesskey="1" href="#Summary">Summary</a>
-<li><a accesskey="2" href="#Installation">Installation</a>: Installation of the queueing toolbox.
-<li><a accesskey="3" href="#Markov-Chains">Markov Chains</a>: Functions for Markov Chains.
-<li><a accesskey="4" href="#Single-Station-Queueing-Systems">Single Station Queueing Systems</a>: Functions for single-station queueing systems.
-<li><a accesskey="5" href="#Queueing-Networks">Queueing Networks</a>: Functions for queueing networks.
-<li><a accesskey="6" href="#References">References</a>: References
-<li><a accesskey="7" href="#Copying">Copying</a>: The GNU General Public License.
-<li><a accesskey="8" href="#Concept-Index">Concept Index</a>: An item for each concept.
-<li><a accesskey="9" href="#Function-Index">Function Index</a>: An item for each function.
-<li><a href="#Author-Index">Author Index</a>: An item for each author.
-</ul>
-
-<!-- -->
-<!-- This file has been automatically generated from summary.txi -->
-<!-- by proc.m. Do not edit this file, all changes will be lost -->
-<!-- *- texinfo -*- -->
-<!-- Copyright (C) 2008, 2009, 2010, 2011, 2012 Moreno Marzolla -->
-<!-- This file is part of the queueing toolbox, a Queueing Networks -->
-<!-- analysis package for GNU Octave. -->
-<!-- The queueing toolbox is free software; you can redistribute it -->
-<!-- and/or modify it under the terms of the GNU General Public License -->
-<!-- as published by the Free Software Foundation; either version 3 of -->
-<!-- the License, or (at your option) any later version. -->
-<!-- The queueing toolbox is distributed in the hope that it will be -->
-<!-- useful, but WITHOUT ANY WARRANTY; without even the implied warranty -->
-<!-- of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -->
-<!-- GNU General Public License for more details. -->
-<!-- You should have received a copy of the GNU General Public License -->
-<!-- along with the queueing toolbox; see the file COPYING. If not, see -->
-<!-- <http://www.gnu.org/licenses/>. -->
-<div class="node">
-<a name="Summary"></a>
-<p><hr>
-Next: <a rel="next" accesskey="n" href="#Installation">Installation</a>,
-Previous: <a rel="previous" accesskey="p" href="#Top">Top</a>,
-Up: <a rel="up" accesskey="u" href="#Top">Top</a>
-
-</div>
-
-<h2 class="chapter">1 Summary</h2>
-
-<ul class="menu">
-<li><a accesskey="1" href="#About-the-Queueing-Toolbox">About the Queueing Toolbox</a>: What is the Queueing Toolbox
-<li><a accesskey="2" href="#Contributing-Guidelines">Contributing Guidelines</a>: How to contribute
-<li><a accesskey="3" href="#Acknowledgements">Acknowledgements</a>
-</ul>
-
-<div class="node">
-<a name="About-the-Queueing-Toolbox"></a>
-<p><hr>
-Next: <a rel="next" accesskey="n" href="#Contributing-Guidelines">Contributing Guidelines</a>,
-Up: <a rel="up" accesskey="u" href="#Summary">Summary</a>
-
-</div>
-
-<h3 class="section">1.1 About the Queueing Toolbox</h3>
-
-<p>This document describes the <code>queueing</code> toolbox for GNU Octave
-(<code>queueing</code> in short). The <code>queueing</code> toolbox, previously
-known as <code>qnetworks</code>, is a collection of functions written in GNU
-Octave for analyzing queueing networks and Markov
-chains. Specifically, <code>queueing</code> contains functions for analyzing
-Jackson networks, open, closed or mixed product-form BCMP networks,
-and computation of performance bounds. The following algorithms have
-been implemented
-
- <ul>
-<li>Convolution for closed, single-class product-form networks
-with load-dependent service centers;
-
- <li>Exact and approximate Mean Value Analysis (MVA) for single and
-multiple class product-form closed networks;
-
- <li>MVA for mixed, multiple class product-form networks
-with load-independent service centers;
-
- <li>Approximate MVA for closed, single-class networks with blocking
-(MVABLO algorithm by F. Akyildiz);
-
- <li>Asymptotic Bounds, Balanced System Bounds and Geometric Bounds;
-
- </ul>
-
-<p class="noindent"><code>queueing</code>
-provides functions for analyzing the following kind of single-station
-queueing systems:
-
- <ul>
-<li>M/M/1
-<li>M/M/m
-<li>M/M/\infty
-<li>M/M/1/k single-server, finite capacity system
-<li>M/M/m/k multiple-server, finite capacity system
-<li>Asymmetric M/M/m
-<li>M/G/1 (general service time distribution)
-<li>M/H_m/1 (Hyperexponential service time distribution)
-</ul>
-
- <p>Functions for Markov chain analysis are also provided:
-
- <ul>
-<li>Birth-death process;
-<li>Transient and steady-state occupancy probabilities;
-<li>Mean times to absorption;
-<li>Expected sojourn times and time-averaged sojourn times;
-<li>Mean first passage times;
-
- </ul>
-
- <p>The <code>queueing</code> toolbox is distributed under the terms of the GNU
-General Public License (GPL), version 3 or later
-(see <a href="#Copying">Copying</a>). You are encouraged to share this software with
-others, and make this package more useful by contributing additional
-functions and reporting problems. See <a href="#Contributing-Guidelines">Contributing Guidelines</a>.
-
- <p>If you use the <code>queueing</code> toolbox in a technical paper, please
-cite it as:
-
- <blockquote>
-Moreno Marzolla, <em>The qnetworks Toolbox: A Software Package for
-Queueing Networks Analysis</em>. Khalid Al-Begain, Dieter Fiems and
-William J. Knottenbelt, Editors, Proceedings 17th International
-Conference on Analytical and Stochastic Modeling Techniques and
-Applications (ASMTA 2010) Cardiff, UK, June 14–16, 2010, volume 6148
-of Lecture Notes in Computer Science, Springer, pp. 102–116, ISBN
-978-3-642-13567-5
-</blockquote>
-
- <p>If you use BibTeX, this is the citation block:
-
-<pre class="verbatim">@inproceedings{queueing,
- author = {Moreno Marzolla},
- title = {The qnetworks Toolbox: A Software Package for Queueing
- Networks Analysis},
- booktitle = {Analytical and Stochastic Modeling Techniques and
- Applications, 17th International Conference,
- ASMTA 2010, Cardiff, UK, June 14-16, 2010. Proceedings},
- editor = {Khalid Al-Begain and Dieter Fiems and William J. Knottenbelt},
- year = {2010},
- publisher = {Springer},
- series = {Lecture Notes in Computer Science},
- volume = {6148},
- pages = {102--116},
- ee = {http://dx.doi.org/10.1007/978-3-642-13568-2_8},
- isbn = {978-3-642-13567-5}
-}
-</pre>
-
- <p>An early draft of the paper above is available as Technical Report
-<a href="http://www.informatica.unibo.it/ricerca/ublcs/2010/UBLCS-2010-04">UBLCS-2010-04</a>, February 2010, Department of Computer Science,
-University of Bologna, Italy.
-
-<div class="node">
-<a name="Contributing-Guidelines"></a>
-<p><hr>
-Next: <a rel="next" accesskey="n" href="#Acknowledgements">Acknowledgements</a>,
-Previous: <a rel="previous" accesskey="p" href="#About-the-Queueing-Toolbox">About the Queueing Toolbox</a>,
-Up: <a rel="up" accesskey="u" href="#Summary">Summary</a>
-
-</div>
-
-<h3 class="section">1.2 Contributing Guidelines</h3>
-
-<p>Contributions and bug reports are <em>always</em> welcome. If you want
-to contribute to the <code>queueing</code> package, here are some
-guidelines:
-
- <ul>
-<li>If you are contributing a new function, please embed proper
-documentation within the function itself. The documentation must be in
-<code>texinfo</code> format, so that it can be extracted and formatted into
-the printable manual. See the existing functions of the
-<code>queueing</code> package for the documentation style.
-
- <li>Make sure that each new function
-properly checks the validity of its input parameters. For example,
-each function accepting vectors should check whether the dimensions
-match.
-
- <li>Provide bibliographic references for each new algorithm you
-contribute. If your implementation differs in some way from the
-reference you give, please describe how and why your implementation
-differs. Add references to the <samp><span class="file">doc/references.txi</span></samp> file.
-
- <li>Include test and demo blocks with your code.
-Test blocks are particularly important, since most algorithms tend to
-be quite tricky to implement correctly. If appropriate, test blocks
-should also verify that the function fails on incorrect input
-parameters.
-
- </ul>
-
- <p>Send your contribution to Moreno Marzolla
-(<a href="mailto:mar...@cs...">mar...@cs...</a>). If you are just a user of this
-package and find it useful, let me know by dropping me a line. Thanks.
-
-<div class="node">
-<a name="Acknowledgements"></a>
-<p><hr>
-Previous: <a rel="previous" accesskey="p" href="#Contributing-Guidelines">Contributing Guidelines</a>,
-Up: <a rel="up" accesskey="u" href="#Summary">Summary</a>
-
-</div>
-
-<h3 class="section">1.3 Acknowledgements</h3>
-
-<p>The following people (listed in alphabetical order) contributed to the
-<code>queueing</code> package, either by providing feedback, reporting bugs
-or contributing code: Philip Carinhas, Phil Colbourn, Yves Durand,
-Marco Guazzone, Dmitry Kolesnikov.
-
-<!-- This file has been automatically generated from installation.txi -->
-<!-- by proc.m. Do not edit this file, all changes will be lost -->
-<!-- *- texinfo -*- -->
-<!-- Copyright (C) 2008, 2009, 2010, 2011, 2012 Moreno Marzolla -->
-<!-- This file is part of the queueing toolbox, a Queueing Networks -->
-<!-- analysis package for GNU Octave. -->
-<!-- The queueing toolbox is free software; you can redistribute it -->
-<!-- and/or modify it under the terms of the GNU General Public License -->
-<!-- as published by the Free Software Foundation; either version 3 of -->
-<!-- the License, or (at your option) any later version. -->
-<!-- The queueing toolbox is distributed in the hope that it will be -->
-<!-- useful, but WITHOUT ANY WARRANTY; without even the implied warranty -->
-<!-- of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -->
-<!-- GNU General Public License for more details. -->
-<!-- You should have received a copy of the GNU General Public License -->
-<!-- along with the queueing toolbox; see the file COPYING. If not, see -->
-<!-- <http://www.gnu.org/licenses/>. -->
-<div class="node">
-<a name="Installation"></a>
-<p><hr>
-Next: <a rel="next" accesskey="n" href="#Markov-Chains">Markov Chains</a>,
-Previous: <a rel="previous" accesskey="p" href="#Summary">Summary</a>,
-Up: <a rel="up" accesskey="u" href="#Top">Top</a>
-
-</div>
-
-<h2 class="chapter">2 Installing the queueing toolbox</h2>
-
-<ul class="menu">
-<li><a accesskey="1" href="#Installation-through-Octave-package-management-system">Installation through Octave package management system</a>
-<li><a accesskey="2" href="#Manual-installation">Manual installation</a>
-<li><a accesskey="3" href="#Development-sources">Development sources</a>
-<li><a accesskey="4" href="#Using-the-queueing-toolbox">Using the queueing toolbox</a>
-</ul>
-
-<div class="node">
-<a name="Installation-through-Octave-package-management-system"></a>
-<p><hr>
-Next: <a rel="next" accesskey="n" href="#Manual-installation">Manual installation</a>,
-Up: <a rel="up" accesskey="u" href="#Installation">Installation</a>
-
-</div>
-
-<h3 class="section">2.1 Installation through Octave package management system</h3>
-
-<p>The most recent version of <code>queueing</code> is 1.1.0 and can
-be downloaded from Octave-Forge
-
- <p><a href="http://octave.sourceforge.net/queueing/">http://octave.sourceforge.net/queueing/</a>
-
- <p>Additional information can be found at
-
- <p><a href="http://www.moreno.marzolla.name/software/queueing/">http://www.moreno.marzolla.name/software/queueing/</a>
-
- <p>If you have a recent version of GNU Octave and a network connection,
-you can install <code>queueing</code> directly from Octave command prompt
-using this command:
-
-<pre class="example"> octave:1> <kbd>pkg install -forge queueing</kbd>
-</pre>
- <p>The command above will automaticall download and install the latest
-version of the queueing toolbox from Octave Forge, and install it on
-your machine. You can verify that the package is indeed installed:
-
-<pre class="example"> octave:1><kbd>pkg list queueing</kbd>
- Package Name | Version | Installation directory
- --------------+---------+-----------------------
- queueing *| 1.1.0 | /home/moreno/octave/queueing-1.1.0
-</pre>
- <p>Alternatively, you can first download <code>queueing</code> from
-Octave-Forge; then, to install the package in the system-wide
-location issue this command at the Octave prompt:
-
-<pre class="example"> octave:1> <kbd>pkg install </kbd><em>queueing-1.1.0.tar.gz</em>
-</pre>
- <p class="noindent">(you may need to start Octave as root in order to allow the
-installation to copy the files to the target locations). After this,
-all functions will be readily available each time Octave starts,
-without the need to tweak the search path.
-
- <p>If you do not have root access, you can do a local install using:
-
-<pre class="example"> octave:1> <kbd>pkg install -local queueing-1.1.0.tar.gz</kbd>
-</pre>
- <p>This will install <code>queueing</code> within your home directory, and the
-package will be available to your user only.
-
- <blockquote>
-<b>Note:</b> Octave version 3.2.3 as shipped with Ubuntu 10.04 seems to ignore
-<code>-local</code> and always tries to install the package on the system
-directory.
-</blockquote>
-
- <p>To remove <code>queueing</code> simply use
-
-<pre class="example"> octave:1> <kbd>pkg uninstall queueing</kbd>
-</pre>
- <div class="node">
-<a name="Manual-installation"></a>
-<p><hr>
-Next: <a rel="next" accesskey="n" href="#Development-sources">Development sources</a>,
-Previous: <a rel="previous" accesskey="p" href="#Installation-through-Octave-package-management-system">Installation through Octave package management system</a>,
-Up: <a rel="up" accesskey="u" href="#Installation">Installation</a>
-
-</div>
-
-<h3 class="section">2.2 Manual installation</h3>
-
-<p>If you want to manually install <code>queueing</code> in a custom location,
-you can download the tarball and unpack it somewhere:
-
-<pre class="example"> <kbd>tar xvfz queueing-1.1.0.tar.gz</kbd>
- <kbd>cd queueing-1.1.0/queueing/</kbd>
-</pre>
- <p>Copy all <code>.m</code> files from the <samp><span class="file">inst/</span></samp> directory to some
-target location. Then, start Octave with the <samp><span class="option">-p</span></samp> option to add
-the target location to the search path, so that Octave will find all
-<code>queueing</code> functions automatically:
-
-<pre class="example"> <kbd>octave -p </kbd><em>/path/to/queueing</em>
-</pre>
- <p>For example, if all <code>queueing</code> m-files are in
-<samp><span class="file">/usr/local/queueing</span></samp>, you can start Octave as follows:
-
-<pre class="example"> <kbd>octave -p </kbd><em>/usr/local/queueing</em>
-</pre>
- <p>If you want, you can add the following line to <samp><span class="file">~/.octaverc</span></samp>:
-
-<pre class="example"> <kbd>addpath("</kbd><em>/path/to/queueing</em><kbd>");</kbd>
-</pre>
- <p class="noindent">so that the path <samp><span class="file">/usr/local/queueing</span></samp> is automatically
-added to the search path each time Octave is started, and you no
-longer need to specify the <samp><span class="option">-p</span></samp> option on the command line.
-
-<div class="node">
-<a name="Development-sources"></a>
-<p><hr>
-Next: <a rel="next" accesskey="n" href="#Using-the-queueing-toolbox">Using the queueing toolbox</a>,
-Previous: <a rel="previous" accesskey="p" href="#Manual-installation">Manual installation</a>,
-Up: <a rel="up" accesskey="u" href="#Installation">Installation</a>
-
-</div>
-
-<h3 class="section">2.3 Development sources</h3>
-
-<p>The source code of the <code>queueing</code> package can be found in the
-Subversion repository at the URL:
-
- <p><a href="http://octave.svn.sourceforge.net/viewvc/octave/trunk/octave-forge/main/queueing/">http://octave.svn.sourceforge.net/viewvc/octave/trunk/octave-forge/main/queueing/</a>
-
- <p>The source distribution contains additional development files which
-are not present in the installation tarball. This section briefly
-describes the content of the source tree. This is only relevant for
-developers who want to modify the code or documentation; normal users
-of the <code>queueing</code> package don't need
-
- <p>The source distribution contains the following directories:
-
- <dl>
-<dt><samp><span class="file">doc/</span></samp><dd>Documentation source. Most of the documentation is extracted from the
-comment blocks of individual function files from the <samp><span class="file">inst/</span></samp>
-directory.
-
- <br><dt><samp><span class="file">inst/</span></samp><dd>This directory contains the <tt>m</tt>-files which implement the
-various Queueing Network algorithms provided by <code>queueing</code>. As a
-notational convention, the names of source files containing functions
-for Queueing Networks start with the ‘<samp><span class="samp">qn</span></samp>’ prefix; the name of
-source files containing functions for Continuous-Time Markov Chains
-(CTMSs) start with the ‘<samp><span class="samp">ctmc</span></samp>’ prefix, and the names of files
-containing functions for Discrete-Time Markov Chains (DTMCs) start
-with the ‘<samp><span class="samp">dtmc</span></samp>’ prefix.
-
- <br><dt><samp><span class="file">test/</span></samp><dd>This directory contains the test functions used to invoke all tests on
-all function files.
-
- <br><dt><samp><span class="file">scripts/</span></samp><dd>This directory contains some utility scripts mostly from GNU Octave,
-which extract the documentation from the specially-formatted comments
-in the <tt>m</tt>-files.
-
- <br><dt><samp><span class="file">examples/</span></samp><dd>This directory contains examples which are automatically extracted
-from the ‘<samp><span class="samp">demo</span></samp>’ blocks of the function files.
-
- <br><dt><samp><span class="file">devel/</span></samp><dd>This directory contains function files which are either not working
-properly, or need additional testing before they are moved to the
-<samp><span class="file">inst/</span></samp> directory.
-
- </dl>
-
- <p>The <code>queueing</code> package ships with a Makefile which can be used
-to produce the documentation (in PDF and HTML format), and
-automatically execute all function tests. Specifically, the following
-targets are defined:
-
- <dl>
-<dt><code>all</code><dd>Running ‘<samp><span class="samp">make</span></samp>’ (or ‘<samp><span class="samp">make all</span></samp>’) on the top-level directory
-builds the programs used to extract the documentation from the
-comments embedded in the <tt>m</tt>-files, and then produce the
-documentation in PDF and HTML format (<samp><span class="file">doc/queueing.pdf</span></samp> and
-<samp><span class="file">doc/queueing.html</span></samp>, respectively).
-
- <br><dt><code>check</code><dd>Running ‘<samp><span class="samp">make check</span></samp>’ will execute all tests contained in the
-<tt>m</tt>-files. If you modify the code of any function in the
-<samp><span class="file">inst/</span></samp> directory, you should run the tests to ensure that no
-errors have been introduced. You are also encouraged to contribute new
-tests, especially for functions which are not adequately validated.
-
- <br><dt><code>clean</code><dt><code>distclean</code><dt><code>dist</code><dd>The ‘<samp><span class="samp">make clean</span></samp>’, ‘<samp><span class="samp">make distclean</span></samp>’ and ‘<samp><span class="samp">make dist</span></samp>’
-commands are used to clean up the source directory and prepare the
-distribution archive in compressed tar format.
-
- </dl>
-
-<div class="node">
-<a name="Using-the-queueing-toolbox"></a>
-<p><hr>
-Previous: <a rel="previous" accesskey="p" href="#Development-sources">Development sources</a>,
-Up: <a rel="up" accesskey="u" href="#Installation">Installation</a>
-
-</div>
-
-<h3 class="section">2.4 Using the queueing toolbox</h3>
-
-<p>You can use all functions by simply invoking their name with the
-appropriate parameters; the <code>queueing</code> package should display an
-error message in case of missing/wrong parameters. You can display the
-help text for any function using the <samp><span class="command">help</span></samp> command. For
-example:
-
-<pre class="example"> octave:2> <kbd>help qnmvablo</kbd>
-</pre>
- <p>prints the documentation for the <samp><span class="command">qnmvablo</span></samp> function.
-Additional information can be found in the <code>queueing</code> manual,
-which is available in PDF format in <samp><span class="file">doc/queueing.pdf</span></samp> and in
-HTML format in <samp><span class="file">doc/queueing.html</span></samp>.
-
- <p>Within GNU Octave, you can also run the test and demo blocks
-associated to the functions, using the <samp><span class="command">test</span></samp> and
-<samp><span class="command">demo</span></samp> commands respectively. To run all the tests of, say,
-the <samp><span class="command">qnmvablo</span></samp> function:
-
-<pre class="example"> octave:3> <kbd>test qnmvablo</kbd>
- -| PASSES 4 out of 4 tests
-</pre>
- <p>To execute the demos of the <samp><span class="command">qnclosed</span></samp> function, use the
-following:
-
-<pre class="example"> octave:4> <kbd>demo qnclosed</kbd>
-</pre>
- <!-- This file has been automatically generated from markovchains.txi -->
-<!-- by proc.m. Do not edit this file, all changes will be lost -->
-<!-- *- texinfo -*- -->
-<!-- Copyright (C) 2008, 2009, 2010, 2011, 2012 Moreno Marzolla -->
-<!-- This file is part of the queueing toolbox, a Queueing Networks -->
-<!-- analysis package for GNU Octave. -->
-<!-- The queueing toolbox is free software; you can redistribute it -->
-<!-- and/or modify it under the terms of the GNU General Public License -->
-<!-- as published by the Free Software Foundation; either version 3 of -->
-<!-- the License, or (at your option) any later version. -->
-<!-- The queueing toolbox is distributed in the hope that it will be -->
-<!-- useful, but WITHOUT ANY WARRANTY; without even the implied warranty -->
-<!-- of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -->
-<!-- GNU General Public License for more details. -->
-<!-- You should have received a copy of the GNU General Public License -->
-<!-- along with the queueing toolbox; see the file COPYING. If not, see -->
-<!-- <http://www.gnu.org/licenses/>. -->
-<div class="node">
-<a name="Markov-Chains"></a>
-<p><hr>
-Next: <a rel="next" accesskey="n" href="#Single-Station-Queueing-Systems">Single Station Queueing Systems</a>,
-Previous: <a rel="previous" accesskey="p" href="#Installation">Installation</a>,
-Up: <a rel="up" accesskey="u" href="#Top">Top</a>
-
-</div>
-
-<h2 class="chapter">3 Markov Chains</h2>
-
-<ul class="menu">
-<li><a accesskey="1" href="#Discrete_002dTime-Markov-Chains">Discrete-Time Markov Chains</a>
-<li><a accesskey="2" href="#Continuous_002dTime-Markov-Chains">Continuous-Time Markov Chains</a>
-</ul>
-
-<div class="node">
-<a name="Discrete-Time-Markov-Chains"></a>
-<a name="Discrete_002dTime-Markov-Chains"></a>
-<p><hr>
-Next: <a rel="next" accesskey="n" href="#Continuous_002dTime-Markov-Chains">Continuous-Time Markov Chains</a>,
-Up: <a rel="up" accesskey="u" href="#Markov-Chains">Markov Chains</a>
-
-</div>
-
-<h3 class="section">3.1 Discrete-Time Markov Chains</h3>
-
-<p>Let X_0, X_1, <small class="dots">...</small>, X_n, <small class="dots">...</small> be a sequence of random
-variables defined over a discete state space 0, 1, 2,
-<small class="dots">...</small>. The sequence X_0, X_1, <small class="dots">...</small>, X_n, <small class="dots">...</small> is a
-<em>stochastic process</em> with discrete time 0, 1, 2,
-<small class="dots">...</small>. A <em>Markov chain</em> is a stochastic process {X_n,
-n=0, 1, 2, <small class="dots">...</small>} which satisfies the following Markov property:
-
- <p>P(X_n+1 = x_n+1 | X_n = x_n, X_n-1 = x_n-1, ..., X_0 = x_0) = P(X_n+1 = x_n+1 | X_n = x_n)
-
-<p class="noindent">which basically means that the probability that the system is in
-a particular state at time n+1 only depends on the state the
-system was at time n.
-
- <p>The evolution of a Markov chain with finite state space {1, 2,
-<small class="dots">...</small>, N} can be fully described by a stochastic matrix \bf
-P(n) = [ P_i,j(n) ] such that P_i, j(n) = P( X_n+1 = j\
-|\ X_n = i ). If the Markov chain is homogeneous (that is, the
-transition probability matrix \bf P(n) is time-independent),
-we can write \bf P = [P_i, j], where P_i, j = P(
-X_n+1 = j\ |\ X_n = i ) for all n=0, 1, <small class="dots">...</small>.
-
- <p>The transition probability matrix \bf P must satisfy the
-following two properties: (1) P_i, j ≥ 0 for all
-i, j, and (2) \sum_j=1^N P_i,j = 1 for all i
-
- <p><a name="doc_002ddtmc_005fcheck_005fP"></a>
-
-<div class="defun">
-— Function File: [<var>r</var> <var>err</var>] = <b>dtmc_check_P</b> (<var>P</var>)<var><a name="index-dtmc_005fcheck_005fP-1"></a></var><br>
-<blockquote>
- <p><a name="index-Markov-chain_002c-discrete-time-2"></a>
-Check if <var>P</var> is a valid transition probability matrix. If <var>P</var>
-is valid, <var>r</var> is the size (number of rows or columns) of <var>P</var>.
-If <var>P</var> is not a transition probability matrix, <var>r</var> is set to
-zero, and <var>err</var> to an appropriate error string.
-
- </blockquote></div>
-
-<ul class="menu">
-<li><a accesskey="1" href="#State-occupancy-probabilities-_0028DTMC_0029">State occupancy probabilities (DTMC)</a>
-<li><a accesskey="2" href="#Birth_002ddeath-process-_0028DTMC_0029">Birth-death process (DTMC)</a>
-<li><a accesskey="3" href="#Expected-number-of-visits-_0028DTMC_0029">Expected number of visits (DTMC)</a>
-<li><a accesskey="4" href="#Time_002daveraged-expected-sojourn-times-_0028DTMC_0029">Time-averaged expected sojourn times (DTMC)</a>
-<li><a accesskey="5" href="#Mean-time-to-absorption-_0028DTMC_0029">Mean time to absorption (DTMC)</a>
-<li><a accesskey="6" href="#First-passage-times-_0028DTMC_0029">First passage times (DTMC)</a>
-</ul>
-
-<div class="node">
-<a name="State-occupancy-probabilities-(DTMC)"></a>
-<a name="State-occupancy-probabilities-_0028DTMC_0029"></a>
-<p><hr>
-Next: <a rel="next" accesskey="n" href="#Birth_002ddeath-process-_0028DTMC_0029">Birth-death process (DTMC)</a>,
-Up: <a rel="up" accesskey="u" href="#Discrete_002dTime-Markov-Chains">Discrete-Time Markov Chains</a>
-
-</div>
-
-<h4 class="subsection">3.1.1 State occupancy probabilities</h4>
-
-<p>We denote with \bf \pi(n) = \left(\pi_1(n), \pi_2(n), <small class="dots">...</small>,
-\pi_N(n) \right) the <em>state occupancy probability vector</em> at
-step n. \pi_i(n) denotes the probability that the system
-is in state i after n transitions.
-
- <p>Given the transition probability matrix \bf P and the initial
-state occupancy probability vector \bf \pi(0) =
-\left(\pi_1(0), \pi_2(0), <small class="dots">...</small>, \pi_N(0)\right), \bf
-\pi(n) can be computed as:
-
-<pre class="example"> \pi(n) = \pi(0) P^n
-</pre>
- <p>Under certain conditions, there exists a <em>stationary state
-occupancy probability</em> \bf \pi = \lim_n \rightarrow +\infty
-\bf \pi(n), which is independent from \bf \pi(0). The
-stationary vector \bf \pi is the solution of the following
-linear system:
-
-<pre class="example"> /
- | \pi P = \pi
- | \pi 1^T = 1
- \
-</pre>
- <p class="noindent">where \bf 1 is the row vector of ones, and ( \cdot )^T
-the transpose operator.
-
- <p><a name="doc_002ddtmc"></a>
-
-<div class="defun">
-— Function File: <var>p</var> = <b>dtmc</b> (<var>P</var>)<var><a name="index-dtmc-3"></a></var><br>
-— Function File: <var>p</var> = <b>dtmc</b> (<var>P, n, p0</var>)<var><a name="index-dtmc-4"></a></var><br>
-<blockquote>
- <p><a name="index-Markov-chain_002c-discrete-time-5"></a><a name="index-Discrete-time-Markov-chain-6"></a><a name="index-Markov-chain_002c-stationary-probabilities-7"></a><a name="index-Stationary-probabilities-8"></a><a name="index-Markov-chain_002c-transient-probabilities-9"></a><a name="index-Transient-probabilities-10"></a>
-Compute steady-state or transient state occupancy probabilities for a
-Discrete-Time Markov Chain. With a single argument, compute the
-steady-state occupancy probability vector <var>p</var><code>(1), ...,
-</code><var>p</var><code>(N)</code> given the N \times N transition probability matrix
-<var>P</var>. With three arguments, compute the state occupancy
-probabilities <var>p</var><code>(1), ..., </code><var>p</var><code>(N)</code> after <var>n</var>
-steps, given initial occupancy probability vector <var>p0</var>.
-
- <p><strong>INPUTS</strong>
-
- <dl>
-<dt><var>P</var><dd><var>P</var><code>(i,j)</code> is the transition probability from state i
-to state j. <var>P</var> must be an irreducible stochastic matrix,
-which means that the sum of each row must be 1 (\sum_j=1^N P_i, j = 1), and the rank of
-<var>P</var> must be equal to its dimension.
-
- <br><dt><var>n</var><dd>Number of transitions after which compute the state occupancy probabilities
-(n=0, 1, <small class="enddots">...</small>)
-
- <br><dt><var>p0</var><dd><var>p0</var><code>(i)</code> is the probability that at step 0 the system
-is in state i.
-
- </dl>
-
- <p><strong>OUTPUTS</strong>
-
- <dl>
-<dt><var>p</var><dd>If this function is invoked with a single argument,
-<var>p</var><code>(i)</code> is the steady-state probability that the system is
-in state i. <var>p</var> satisfies the equations p = p\bf P and \sum_i=1^N p_i = 1. If this function is invoked
-with three arguments, <var>p</var><code>(i)</code> is the marginal probability
-that the system is in state i after <var>n</var> transitions,
-given the initial probabilities <var>p0</var><code>(i)</code> that the initial state is
-i.
-
- </dl>
-
- </blockquote></div>
-
-<p class="noindent"><strong>EXAMPLE</strong>
-
- <p>This example is from <a href="#GrSn97">GrSn97</a>. Let us consider a maze with nine
-rooms, as shown in the following figure
-
-<pre class="example"> +-----+-----+-----+
- | | | |
- | 1 2 3 |
- | | | |
- +- -+- -+- -+
- | | | |
- | 4 5 6 |
- | | | |
- +- -+- -+- -+
- | | | |
- | 7 8 9 |
- | | | |
- +-----+-----+-----+
-</pre>
- <p>A mouse is placed in one of the rooms and can wander around. At each
-step, the mouse moves from the current room to a neighboring one with
-equal probability: if it is in room 1, it can move to room 2 and 4
-with probability 1/2, respectively. If the mouse is in room 8, it can
-move to either 7, 5 or 9 with probability 1/3.
-
- <p>The transition probability \bf P from room i to room
-j is the following:
-
-<pre class="example"> / 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 /
-</pre>
- <p>The stationary state occupancy probability vector can be computed
-using the following code:
-
-<pre class="example"><pre class="verbatim"> 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)
-</pre>
- ⇒ 0.083333 0.125000 0.083333 0.125000
- 0.166667 0.125000 0.083333 0.125000
- 0.083333
-</pre>
- <div class="node">
-<a name="Birth-death-process-(DTMC)"></a>
-<a name="Birth_002ddeath-process-_0028DTMC_0029"></a>
-<p><hr>
-Next: <a rel="next" accesskey="n" href="#Expected-number-of-visits-_0028DTMC_0029">Expected number of visits (DTMC)</a>,
-Previous: <a rel="previous" accesskey="p" href="#State-occupancy-probabilities-_0028DTMC_0029">State occupancy probabilities (DTMC)</a>,
-Up: <a rel="up" accesskey="u" href="#Discrete_002dTime-Markov-Chains">Discrete-Time Markov Chains</a>
-
-</div>
-
-<h4 class="subsection">3.1.2 Birth-death process</h4>
-
-<p><a name="doc_002ddtmc_005fbd"></a>
-
-<div class="defun">
-— Function File: <var>P</var> = <b>dtmc_bd</b> (<var>b, d</var>)<var><a name="index-dtmc_005fbd-11"></a></var><br>
-<blockquote>
- <p><a name="index-Markov-chain_002c-discrete-time-12"></a><a name="index-Birth_002ddeath-process-13"></a>
-Returns the transition probability matrix P for a discrete
-birth-death process over state space 1, 2, <small class="dots">...</small>, N.
-<var>b</var><code>(i)</code> is the transition probability from state
-i to i+1, and <var>d</var><code>(i)</code> is the transition
-probability from state i+1 to state i, i=1, 2,
-<small class="dots">...</small>, N-1.
-
- <p>Matrix \bf P is therefore defined as:
-
- <pre class="example"> / \
- | 1-b(1) b(1) |
- | d(1) (1-d(1)-b(2)) b(2) |
- | d(2) (1-d(2)-b(3)) b(3) |
- | |
- | ... ... ... |
- | |
- | d(N-2) (1-d(N-2)-b(N-1)) b(N-1) |
- | d(N-1) 1-d(N-1) |
- \ /
-</pre>
- </blockquote></div>
-
-<div class="node">
-<a name="Expected-number-of-visits-(DTMC)"></a>
-<a name="Expected-number-of-visits-_0028DTMC_0029"></a>
-<p><hr>
-Next: <a rel="next" accesskey="n" href="#Time_002daveraged-expected-sojourn-times-_0028DTMC_0029">Time-averaged expected sojourn times (DTMC)</a>,
-Previous: <a rel="previous" accesskey="p" href="#Birth_002ddeath-process-_0028DTMC_0029">Birth-death process (DTMC)</a>,
-Up: <a rel="up" accesskey="u" href="#Discrete_002dTime-Markov-Chains">Discrete-Time Markov Chains</a>
-
-</div>
-
-<h4 class="subsection">3.1.3 Expected Number of Visits</h4>
-
-<p>Given a N state discrete-time Markov chain with transition
-matrix \bf P and an integer n ≥ 0, we let
-L_i(n) be the the expected number of visits to state i
-during the first n transitions. The vector \bf L(n) =
-( L_1(n), L_2(n), <small class="dots">...</small>, L_N(n) ) is defined as
-
-<pre class="example"> n n
- ___ ___
- \ \ i
- L(n) = > pi(i) = > pi(0) P
- /___ /___
- i=0 i=0
-</pre>
- <p class="noindent">where \bf \pi(i) = \bf \pi(0)\bf P^i is the state
-occupancy probability after i transitions.
-
- <p>If \bf P is absorbing, i.e., the stochastic process eventually
-reaches a state with no outgoing transitions with probability 1, then
-we can compute the expected number of visits until absorption
-\bf L. To do so, we first rearrange the states to rewrite
-matrix \bf P as:
-
-<pre class="example"> / Q | R \
- P = |---+---|
- \ 0 | I /
-</pre>
- <p class="noindent">where the first t states are transient
-and the last r states are absorbing (t+r = N). The
-matrix \bf N = (\bf I - \bf Q)^-1 is called the
-<em>fundamental matrix</em>; N_i,j is the expected number of
-times that the process is in the j-th transient state if it
-started in the i-th transient state. If we reshape \bf N
-to the size of \bf P (filling missing entries with zeros), we
-have that, for absorbing chains \bf L = \bf \pi(0)\bf N.
-
- <p><a name="doc_002ddtmc_005fexps"></a>
-
-<div class="defun">
-— Function File: <var>L</var> = <b>dtmc_exps</b> (<var>P, n, p0</var>)<var><a name="index-dtmc_005fexps-14"></a></var><br>
-— Function File: <var>L</var> = <b>dtmc_exps</b> (<var>P, p0</var>)<var><a name="index-dtmc_005fexps-15"></a></var><br>
-<blockquote>
- <p><a name="index-Expected-sojourn-times-16"></a>
-Compute the expected number of visits to each state during the first
-<var>n</var> transitions, or until abrosption.
-
- <p><strong>INPUTS</strong>
-
- <dl>
-<dt><var>P</var><dd>N \times N transition probability matrix.
-
- <br><dt><var>n</var><dd>Number of steps during which the expected number of visits are
-computed (<var>n</var> ≥ 0). If <var>n</var><code>=0</code>, returns
-<var>p0</var>. If <var>n</var><code> > 0</code>, returns the expected number of
-visits after exactly <var>n</var> transitions.
-
- <br><dt><var>p0</var><dd>Initial state occupancy probability.
-
- </dl>
-
- <p><strong>OUTPUTS</strong>
-
- <dl>
-<dt><var>L</var><dd>When called with two arguments, <var>L</var><code>(i)</code> is the expected
-number of visits to transient state i before absorption. When
-called with three arguments, <var>L</var><code>(i)</code> is the expected number
-of visits to state i during the first <var>n</var> transitions,
-given initial occupancy probability <var>p0</var>.
-
- </dl>
-
- <pre class="sp">
-
- </pre>
- <strong>See also:</strong> ctmc_exps.
-
- </blockquote></div>
-
-<div class="node">
-<a name="Time-averaged-expected-sojourn-times-(DTMC)"></a>
-<a name="Time_002daveraged-expected-sojourn-times-_0028DTMC_0029"></a>
-<p><hr>
-Next: <a rel="next" accesskey="n" href="#Mean-time-to-absorption-_0028DTMC_0029">Mean time to absorption (DTMC)</a>,
-Previous: <a rel="previous" accesskey="p" href="#Expected-number-of-visits-_0028DTMC_0029">Expected number of visits (DTMC)</a>,
-Up: <a rel="up" accesskey="u" href="#Discrete_002dTime-Markov-Chains">Discrete-Time Markov Chains</a>
-
-</div>
-
-<h4 class="subsection">3.1.4 Time-averaged expected sojourn times</h4>
-
-<p><a name="doc_002ddtmc_005ftaexps"></a>
-
-<div class="defun">
-— Function File: <var>L</var> = <b>dtmc_exps</b> (<var>P, n, p0</var>)<var><a name="index-dtmc_005fexps-17"></a></var><br>
-— Function File: <var>L</var> = <b>dtmc_exps</b> (<var>P, p0</var>)<var><a name="index-dtmc_005fexps-18"></a></var><br>
-<blockquote>
- <p><a name="index-Time_002dalveraged-sojourn-time-19"></a>
-Compute the <em>time-averaged sojourn time</em> <var>M</var><code>(i)</code>,
-defined as the fraction of time steps {0, 1, <small class="dots">...</small>, n} (or
-until absorption) spent in state i, assuming that the state
-occupancy probabilities at time 0 are <var>p0</var>.
-
- <p><strong>INPUTS</strong>
-
- <dl>
-<dt><var>Q</var><dd>Infinitesimal generator matrix. <var>Q</var><code>(i,j)</code> is the transition
-rate from state i to state j,
-1 ≤ i \neq j ≤ N. The
-matrix <var>Q</var> must also satisfy the condition \sum_j=1^N Q_i, j = 0
-
- <br><dt><var>t</var><dd>Time. If omitted, the results are computed until absorption.
-
- <br><dt><var>p</var><dd><var>p</var><code>(i)</code> is the probability that, at time 0, the system was in
-state i, for all i = 1, <small class="dots">...</small>, N
-
- </dl>
-
- <p><strong>OUTPUTS</strong>
-
- <dl>
-<dt><var>M</var><dd>If this function is called with three arguments, <var>M</var><code>(i)</code>
-is the expected fraction of the interval [0,t] spent in state
-i assuming that the state occupancy probability at time zero
-is <var>p</var>. If this function is called with two arguments,
-<var>M</var><code>(i)</code> is the expected fraction of time until absorption
-spent in state i.
-
- </dl>
-
- </blockquote></div>
-
-<div class="node">
-<a name="Mean-time-to-absorption-(DTMC)"></a>
-<a name="Mean-time-to-absorption-_0028DTMC_0029"></a>
-<p><hr>
-Next: <a rel="next" accesskey="n" href="#First-passage-times-_0028DTMC_0029">First passage times (DTMC)</a>,
-Previous: <a rel="previous" accesskey="p" href="#Time_002daveraged-expected-sojourn-times-_0028DTMC_0029">Time-averaged expected sojourn times (DTMC)</a>,
-Up: <a rel="up" accesskey="u" href="#Discrete_002dTime-Markov-Chains">Discrete-Time Markov Chains</a>
-
-</div>
-
-<h4 class="subsection">3.1.5 Mean Time to Absorption</h4>
-
-<p>The <em>mean time to absorption</em> is defined as the average number of
-transitions which are required to reach an absorbing state, starting
-from a transient state (or given an initial state occupancy
-probability vector \bf \pi(0)).
-
- <p>Let \bf t_i be the expected number of transitions before
-being absorbed in any absorbing state, starting from state i.
-Vector \bf t can be computed from the fundamental matrix
-\bf N (see <a href="#Expected-number-of-visits-_0028DTMC_0029">Expected number of visits (DTMC)</a>) as
-
-<pre class="example"> t = 1 N
-</pre>
- <p>Let \bf B = [ B_i, j ] be a matrix where B_i, j is
-the probability of being absorbed in state j, starting from
-transient state i. Again, using matrices \bf N and
-\bf R (see <a href="#Expected-number-of-visits-_0028DTMC_0029">Expected number of visits (DTMC)</a>) we can write
-
-<pre class="example"> B = N R
-</pre>
- <p><a name="doc_002ddtmc_005fmtta"></a>
-
-<div class="defun">
-— Function File: [<var>t</var> <var>N</var> <var>B</var>] = <b>dtmc_mtta</b> (<var>P</var>)<var><a name="index-dtmc_005fmtta-20"></a></var><br>
-— Function File: [<var>t</var> <var>N</var> <var>B</var>] = <b>dtmc_mtta</b> (<var>P, p0</var>)<var><a name="index-dtmc_005fmtta-21"></a></var><br>
-<blockquote>
- <p><a name="index-Mean-time-to-absorption-22"></a><a name="index-Absorption-probabilities-23"></a><a name="index-Fundamental-matrix-24"></a>
-Compute the expected number of steps before absorption for a
-DTMC with N \times N transition probability matrix <var>P</var>;
-compute also the fundamental matrix <var>N</var> for <var>P</var>.
-
- <p><strong>INPUTS</strong>
-
- <dl>
-<dt><var>P</var><dd>N \times N transition probability matrix.
-
- </dl>
-
- <p><strong>OUTPUTS</strong>
-
- <dl>
-<dt><var>t</var><dd>When called with a single argument, <var>t</var> is a vector of size
-N such that <var>t</var><code>(i)</code> is the expected number of steps
-before being absorbed in any absorbing state, starting from state
-i; if i is absorbing, <var>t</var><code>(i) = 0</code>. When
-called with two arguments, <var>t</var> is a scalar, and represents the
-expected number of steps before absorption, starting from the initial
-state occupancy probability <var>p0</var>.
-
- <br><dt><var>N</var><dd>When called with a single argument, <var>N</var> is the N \times N
-fundamental matrix for <var>P</var>. <var>N</var><code>(i,j)</code> is the expected
-number of visits to transient state <var>j</var> before absorption, if it
-is started in transient state <var>i</var>. The initial state is counted
-if i = j. When called with two arguments, <var>N</var> is a vector
-of size N such that <var>N</var><code>(j)</code> is the expected number
-of visits to transient state <var>j</var> before absorption, given initial
-state occupancy probability <var>P0</var>.
-
- <br><dt><var>B</var><dd>When called with a single argument, <var>B</var> is a N \times N
-matrix where <var>B</var><code>(i,j)</code> is the probability of being absorbed
-in state j, starting from transient state i; if
-j is not absorbing, <var>B</var><code>(i,j) = 0</code>; if i
-is absorbing, <var>B</var><code>(i,i) = 1</code> and
-<var>B</var><code>(i,j) = 0</code> for all j \neq j. When called with
-two arguments, <var>B</var> is a vector of size N where
-<var>B</var><code>(j)</code> is the probability of being absorbed in state
-<var>j</var>, given initial state occupancy probabilities <var>p0</var>.
-
- </dl>
-
- <pre class="sp">
-
- </pre>
- <strong>See also:</strong> ctmc_mtta.
-
- </blockquote></div>
-
-<div class="node">
-<a name="First-passage-times-(DTMC)"></a>
-<a name="First-passage-times-_0028DTMC_0029"></a>
-<p><hr>
-Previous: <a rel="previous" accesskey="p" href="#Mean-time-to-absorption-_0028DTMC_0029">Mean time to absorption (DTMC)</a>,
-Up: <a rel="up" accesskey="u" href="#Discrete_002dTime-Markov-Chains">Discrete-Time Markov Chains</a>
-
-</div>
-
-<h4 class="subsection">3.1.6 First Passage Times</h4>
-
-<p>The First Passage Time M_i, j is the average number of
-transitions needed to visit state j for the first time,
-starting from state i. Matrix \bf M satisfies the
-property that
-
-<pre class="example"> ___
- \
- M_ij = 1 + > P_ij * M_kj
- /___
- k!=j
-</pre>
- <p>To compute \bf M = [ M_i, j] a different formulation is
-used. Let \bf W be the N \times N matrix having each
-row equal to the steady-state probability vector \bf \pi for
-\bf P; let \bf I be the N \times N identity
-matrix. Define \bf Z as follows:
-
-<pre class="example"> -1
- Z = (I - P + W)
-</pre>
- <p class="noindent">Then, we have that
-
-<pre class="example"> Z_jj - Z_ij
- M_ij = -----------
- \pi_j
-</pre>
- <p>According to the definition above, M_i,i = 0. We arbitrarily
-let M_i,i to be the <em>mean recurrence time</em> r_i
-for state i, that is the average number of transitions needed
-to return to state i starting from it. r_i is:
-
-<pre class="example"> 1
- r_i = -----
- \pi_i
-</pre>
- <p><a name="doc_002ddtmc_005ffpt"></a>
-
-<div class="defun">
-— Function File: <var>M</var> = <b>dtmc_fpt</b> (<var>P</var>)<var><a name="index-dtmc_005ffpt-25"></a></var><br>
-<blockquote>
- <p><a name="index-First-passage-times-26"></a><a name="index-Mean-recurrence-times-27"></a>
-Compute mean first passage times and mean recurrence times
-for an irreducible discrete-time Markov chain.
-
- <p><strong>INPUTS</strong>
-
- <dl>
-<dt><var>P</var><dd><var>P</var><code>(i,j)</code> is the transition probability from state i
-to state j. <var>P</var> must be an irreducible stochastic matrix,
-which means that the sum of each row must be 1 (\sum_j=1^N
-P_i j = 1), and the rank of <var>P</var> must be equal to its
-dimension.
-
- </dl>
-
- <p><strong>OUTPUTS</strong>
-
- <dl>
-<dt><var>M</var><dd>For all i \neq j, <var>M</var><code>(i,j)</code> is the average number of
-transitions before state <var>j</var> is reached for the first time,
-starting from state <var>i</var>. <var>M</var><code>(i,i)</code> is the <em>mean
-recurrence time</em> of state i, and represents the average time
-needed to return to state <var>i</var>.
-
- </dl>
-
- <pre class="sp">
-
- </pre>
- <strong>See also:</strong> ctmc_fpt.
-
- </blockquote></div>
-
-<div class="node">
-<a name="Continuous-Time-Markov-Chains"></a>
-<a name="Continuous_002dTime-Markov-Chains"></a>
-<p><hr>
-Previous: <a rel="previous" accesskey="p" href="#Discrete_002dTime-Markov-Chains">Discrete-Time Markov Chains</a>,
-Up: <a rel="up" accesskey="u" href="#Markov-Chains">Markov Chains</a>
-
-</div>
-
-<h3 class="section">3.2 Continuous-Time Markov Chains</h3>
-
-<p>A stochastic process {X(t), t ≥ 0} is a continuous-time
-Markov chain if, for all integers n, and for any sequence
-t_0, t_1 , \ldots, t_n, t_n+1 such that t_0 < t_1 <
-\ldots < t_n < t_n+1, we have
-
- <p>P(X_n+1 = x_n+1 | X_n = x_n, X_n-1 = x_n-1, ..., X_0 = x_0) = P(X_n+1 = x_n+1 | X_n = x_n)
-
- <p>A continuous-time Markov chain is defined according to an
-<em>infinitesimal generator matrix</em> \bf Q = [Q_i,j],
-where for each i \neq j, Q_i, j is the transition rate
-from state i to state j. The matrix \bf Q must
-satisfy the property that, for all i, \sum_j=1^N Q_i,
-j = 0.
-
- <p><a name="doc_002dctmc_005fcheck_005fQ"></a>
-
-<div class="defun">
-— Function File: [<var>result</var> <var>err</var>] = <b>ctmc_check_Q</b> (<var>Q</var>)<var><a name="index-ctmc_005fcheck_005fQ-28"></a></var><br>
-<blockquote>
- <p><a name="index-Markov-chain_002c-continuous-time-29"></a>
-If <var>Q</var> is a valid infinitesimal generator matrix, return
-the size (number of rows or columns) of <var>Q</var>. If <var>Q</var> is not
-an infinitesimal generator matrix, set <var>result</var> to zero, and
-<var>err</var> to an appropriate error string.
-
- </blockquote></div>
-
-<ul class="menu">
-<li><a accesskey="1" href="#State-occupancy-probabilities-_0028CTMC_0029">State occupancy probabilities (CTMC)</a>
-<li><a accesskey="2" href="#Birth_002ddeath-process-_0028CTMC_0029">Birth-death process (CTMC)</a>
-<li><a accesskey="3" href="#Expected-sojourn-times-_0028CTMC_0029">Expected sojourn times (CTMC)</a>
-<li><a accesskey="4" href="#Time_002daveraged-expected-sojourn-times-_0028CTMC_0029">Time-averaged expected sojourn times (CTMC)</a>
-<li><a accesskey="5" href="#Mean-time-to-absorption-_0028CTMC_0029">Mean time to absorption (CTMC)</a>
-<li><a accesskey="6" href="#First-passage-times-_0028CTMC_0029">First passage times (CTMC)</a>
-</ul>
-
-<div class="node">
-<a name="State-occupancy-probabilities-(CTMC)"></a>
-<a name="State-occupancy-probabilities-_0028CTMC_0029"></a>
-<p><hr>
-Next: <a rel="next" accesskey="n" href="#Birth_002ddeath-process-_0028CTMC_0029">Birth-death process (CTMC)</a>,
-Up: <a rel="up" accesskey="u" href="#Continuous_002dTime-Markov-Chains">Continuous-Time Markov Chains</a>
-
-</div>
-
-<h4 class="subsection">3.2.1 State occupancy probabilities</h4>
-
-<p>Similarly to the discrete case, we denote with \bf \pi(t) =
-(\pi_1(t), \pi_2(t), <small class="dots">...</small>, \pi_N(t) ) the <em>state occupancy
-probability vector</em> at time t. \pi_i(t) is the
-probability that the system is in state i at time t
-≥ 0.
-
- <p>Given the infinitesimal generator matrix \bf Q and the initial
-state occupancy probabilities \bf \pi(0) = (\pi_1(0),
-\pi_2(0), <small class="dots">...</small>, \pi_N(0)), the state occupancy probabilities
-\bf \pi(t) at time t can be computed as:
-
-<pre class="example"> \pi(t) = \pi(0) exp(Qt)
-</pre>
- <p class="noindent">where \exp( \bf Q t ) is the matrix exponential
-of \bf Q t. Under certain conditions, there exists a
-<em>stationary state occupancy probability</em> \bf \pi =
-\lim_t \rightarrow +\infty \bf \pi(t), which is independent from
-\bf \pi(0). \bf \pi is the solution of the following
-linear system:
-
-<pre class="example"> /
- | \pi Q = 0
- | \pi 1^T = 1
- \
-</pre>
- <p><a name="doc_002dctmc"></a>
-
-<div class="defun">
-— Function File: <var>p</var> = <b>ctmc</b> (<var>Q</var>)<var><a name="index-ctmc-30"></a></var><br>
-— Function File: <var>p</var> = <b>ctmc</b> (<var>Q, t. p0</var>)<var><a name="index-ctmc-31"></a></var><br>
-<blockquote>
- <p><a name="index-Markov-chain_002c-continuous-time-32"></a><a name="index-Continuous-time-Markov-chain-33"></a><a name="index-Markov-chain_002c-state-occupancy-probabilities-34"></a><a name="index-Stationary-probabilities-35"></a>
-Compute stationary or transient state occupancy probabilities
-for a continuous-time Markov chain.
-
- <p>With a single argument, compute the stat...
[truncated message content] |
