text:
\documentclass[a4paper]{article}
% generated by Docutils <http://docutils.sourceforge.net/>
\usepackage{fixltx2e} % LaTeX patches, \textsubscript
\usepackage{cmap} % fix search and cut-and-paste in Acrobat
\usepackage{ifthen}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{color}
\usepackage{float} % float configuration
\floatplacement{figure}{H} % place figures here definitely
\usepackage{graphicx}
\setcounter{secnumdepth}{0}

%%% Custom LaTeX preamble
% PDF Standard Fonts
\usepackage{mathptmx} % Times
\usepackage[scaled=.90]{helvet}
\usepackage{courier}

%%% User specified packages and stylesheets

%%% Fallback definitions for Docutils-specific commands
% basic code highlight:
\providecommand*\DUrolecomment[1]{\textcolor[rgb]{0.40,0.40,0.40}{#1}}
\providecommand*\DUroledeleted[1]{\textcolor[rgb]{0.40,0.40,0.40}{#1}}
\providecommand*\DUrolekeyword[1]{\textbf{#1}}
\providecommand*\DUrolestring[1]{\textit{#1}}

% fieldlist environment
\ifthenelse{\isundefined{\DUfieldlist}}{
  \newenvironment{DUfieldlist}%
    {\quote\description}
    {\enddescription\endquote}
}{}

% inline markup (custom roles)
% \DUrole{#1}{#2} tries \DUrole#1{#2}
\providecommand*{\DUrole}[2]{%
  \ifcsname DUrole#1\endcsname%
    \csname DUrole#1\endcsname{#2}%
  \else% backwards compatibility: try \docutilsrole#1{#2}
    \ifcsname docutilsrole#1\endcsname%
      \csname docutilsrole#1\endcsname{#2}%
    \else%
      #2%
    \fi%
  \fi%
}

% hyperlinks:
\ifthenelse{\isundefined{\hypersetup}}{
  \usepackage[colorlinks=true,linkcolor=blue,urlcolor=blue]{hyperref}
  \urlstyle{same} % normal text font (alternatives: tt, rm, sf)
}{}
\hypersetup{
  pdftitle={Dungeon on the fly},
}

%%% Title Data
\title{\phantomsection%
  Dungeon on the fly%
  \label{dungeon-on-the-fly}}
\author{}
\date{}

%%% Body
\begin{document}
\maketitle

\section{A project in the course Procedural methods for images, TNM022%
  \label{a-project-in-the-course-procedural-methods-for-images-tnm022}%
}
%
\begin{DUfieldlist}
\item[{Date:}]
2016-12-13

\item[{Author:}]
Morgan Bengtsson

\item[{Contact:}]
\href{mailto:benmo417@student.liu.se}{benmo417@student.liu.se}, \href{mailto:bengtsson.morgan@gmail.com}{bengtsson.morgan@gmail.com}

\item[{Verson:}]
1.0

\item[{Abstract:}]
Methods for procedural modeling are analysed. Mainly by using procedurally adjustable building blocks. Which resulted in an application that generates a complete and versatile dungeon.

\end{DUfieldlist}

\section{Introduction%
  \label{introduction}%
}

This is a report for the final project in the course Procedural methods for images, TNM022 at Linköping university.

Procedural methods for generating content for games is an attractive subject. Done right it can help to give the appearance of very big game world, without to much work regarding modeling and texturing. There are different routes to take when doing things procedurally. Either everything is fully procedural. Within the realm of 3D graphics meaning that, from each vertex in the models to every pixel in the textures are generated from mathematical functions. Another option is to combine procedural methods with manually made building blocks. This is the approach taken in this work, where predefined components are used with adjustable parameters to affect their appearance. Procedural methods can then be used to adjust those parameters. Furthermore also to choose what components are created, where they are placed, how many and so forth. This approach is often called shape algebra or procedural modeling. In this work these ideas are used to generate a dungeon, inspired from old games such as \hyperref[daggerfall]{Daggerfall}.

\begin{figure}
\noindent\makebox[\textwidth][c]{\includegraphics[width=0.700\linewidth]{daggerfall.jpg}}\phantomsection\label{daggerfall}

\caption{A dungeon from the old game Daggerfall.}
\end{figure}

\section{Noise%
  \label{noise}%
}

The mathematical functions used for generating values are arbitrary. Though in this work mainly noise functions are used. An important property of them is that they are deterministic, meaning that the same input values will always generate the same output. Hence with the same input the exact same dungeon will be generated again in the end. This is important for games, since if the player comes back to a location, the same geometry should be present. Noise is also artistically pleasant for creating sense of randomness, while the predefined components gives a sense of structure. The main noise functions used throughout the implementation are described below:

\hyperref[simplex-range]{simplex\_range} is a function that generates deterministic random values within a defined range. Three dimensional inputs are most often used, though others types are supported. The function is available in an integer and a float variant.
%
\begin{quote}{\ttfamily \raggedright \noindent
\DUrole{keyword}{template}\DUrole{operator}{<}\DUrole{keyword}{class}~\DUrole{name}{\DUrole{class}{T}}\DUrole{operator}{>}~\\
\DUrole{keyword}{\DUrole{type}{int}}~\DUrole{name}{simplex\_range}\DUrole{punctuation}{(}\DUrole{keyword}{const}~\DUrole{name}{T}~\DUrole{operator}{\&}\DUrole{name}{seed}\DUrole{punctuation}{,}~\DUrole{keyword}{const}~\DUrole{keyword}{\DUrole{type}{int}}~\DUrole{name}{min}\DUrole{punctuation}{,}~\DUrole{keyword}{const}~\DUrole{keyword}{\DUrole{type}{int}}~\DUrole{name}{max}\DUrole{punctuation}{)}~\DUrole{punctuation}{\{}~\\
~~\DUrole{comment}{\DUrole{single}{//~Noise~value~in~range~-1.0f,~1.0f.\\
}}~~\DUrole{keyword}{auto}~\DUrole{name}{s}~\DUrole{operator}{=}~\DUrole{name}{glm}\DUrole{operator}{::}\DUrole{name}{simplex}\DUrole{punctuation}{(}\DUrole{name}{seed}\DUrole{punctuation}{);}~\\
~\\
~~\DUrole{comment}{\DUrole{single}{//~Scale~it~to~the~min~,~max~range.\\
}}~~\DUrole{keyword}{auto}~\DUrole{name}{n}~\DUrole{operator}{=}~\DUrole{punctuation}{(((}\DUrole{name}{s}~\DUrole{operator}{+}~\DUrole{literal}{\DUrole{number}{\DUrole{float}{1.0f}}}\DUrole{punctuation}{)}~\DUrole{operator}{*}~\DUrole{punctuation}{(}\DUrole{name}{max}~\DUrole{operator}{-}~\DUrole{name}{min}\DUrole{punctuation}{))}~\DUrole{operator}{/}~\DUrole{literal}{\DUrole{number}{\DUrole{float}{2.0f}}}\DUrole{punctuation}{)}~\DUrole{operator}{+}~\DUrole{name}{min}\DUrole{punctuation}{;}~\\
~~\DUrole{keyword}{return}~\DUrole{name}{\DUrole{function}{int}}\DUrole{punctuation}{(}\DUrole{name}{n}\DUrole{punctuation}{);}~\\
\DUrole{punctuation}{\}}~\\
~\\
\DUrole{keyword}{template}\DUrole{operator}{<}\DUrole{keyword}{class}~\DUrole{name}{\DUrole{class}{T}}\DUrole{operator}{>}~\\
\DUrole{keyword}{\DUrole{type}{float}}~\DUrole{name}{simplex\_range}\DUrole{punctuation}{(}\DUrole{keyword}{const}~\DUrole{name}{T}~\DUrole{operator}{\&}\DUrole{name}{seed}\DUrole{punctuation}{,}~\DUrole{keyword}{const}~\DUrole{keyword}{\DUrole{type}{float}}~\DUrole{name}{min}\DUrole{punctuation}{,}~\DUrole{keyword}{const}~\DUrole{keyword}{\DUrole{type}{float}}~\DUrole{name}{max}\DUrole{punctuation}{)\{}~\\
~~\DUrole{comment}{\DUrole{single}{//~Noise~value~in~range~-1.0f,~1.0f.\\
}}~~\DUrole{keyword}{auto}~\DUrole{name}{s}~\DUrole{operator}{=}~\DUrole{name}{glm}\DUrole{operator}{::}\DUrole{name}{simplex}\DUrole{punctuation}{(}\DUrole{name}{seed}\DUrole{punctuation}{);}~\\
~\\
~~\DUrole{comment}{\DUrole{single}{//~Scale~it~to~the~min~,~max~range.\\
}}~~\DUrole{keyword}{auto}~\DUrole{name}{n}~\DUrole{operator}{=}~\DUrole{punctuation}{(((}\DUrole{name}{s}~\DUrole{operator}{+}~\DUrole{literal}{\DUrole{number}{\DUrole{float}{1.0f}}}\DUrole{punctuation}{)}~\DUrole{operator}{*}~\DUrole{punctuation}{(}\DUrole{name}{max}~\DUrole{operator}{-}~\DUrole{name}{min}\DUrole{punctuation}{))}~\DUrole{operator}{/}~\DUrole{literal}{\DUrole{number}{\DUrole{float}{2.0f}}}\DUrole{punctuation}{)}~\DUrole{operator}{+}~\DUrole{name}{min}\DUrole{punctuation}{;}~\\
~~\DUrole{keyword}{return}~\DUrole{name}{n}\DUrole{punctuation}{;}~\\
\DUrole{punctuation}{\}}
}
\end{quote}

\hyperref[simplex-bool]{simplex\_bool} is a convenience method that either gives true or false depending on the input.
%
\begin{quote}{\ttfamily \raggedright \noindent
\DUrole{keyword}{template}\DUrole{operator}{<}\DUrole{keyword}{class}~\DUrole{name}{\DUrole{class}{T}}\DUrole{operator}{>}~\\
\DUrole{keyword}{\DUrole{type}{bool}}~\DUrole{name}{simplex\_bool}\DUrole{punctuation}{(}\DUrole{keyword}{const}~\DUrole{name}{T}~\DUrole{operator}{\&}\DUrole{name}{seed}\DUrole{punctuation}{)}~\DUrole{punctuation}{\{}~\\
~~~\DUrole{keyword}{return}~\DUrole{name}{glm}\DUrole{operator}{::}\DUrole{name}{simplex}\DUrole{punctuation}{(}\DUrole{name}{seed}\DUrole{punctuation}{)}~\DUrole{operator}{>}~\DUrole{literal}{\DUrole{number}{\DUrole{float}{0.0f}}}~\DUrole{operator}{?}~\DUrole{name}{\DUrole{builtin}{true}}~\DUrole{operator}{:}~\DUrole{name}{\DUrole{builtin}{false}}\DUrole{punctuation}{;}~\\
\DUrole{punctuation}{\}}
}
\end{quote}

\section{Components%
  \label{components}%
}

There are two types of components defined to generate the dungeon: doors and entities.

\subsection{Door%
  \label{door}%
}

Doors are small objects that define the connection between two entities. A door consist of a transform matrix, a pointer to the next entity and a \hyperref[door-model]{model for rendering}. The door has two \emph{states}; open and closed, which are set by the \hyperref[simplex-bool]{simplex\_bool} function. Input for that method is the door position.

\begin{figure}
\noindent\makebox[\textwidth][c]{\includegraphics[width=0.700\linewidth]{doors.png}}\phantomsection\label{door-model}

\caption{Door model with two states, open and closed.}
\end{figure}

\subsection{Entity%
  \label{entity}%
}

The entity is a base component that the following components are based from. The
common denominator is that an entity can contain several doors that lead to new entities. An entity takes a transformation matrix that specifies where the entity should be generated. Each entity also contains a bounding box that is used for collision detection in the \hyperref[algorithm]{algorithm}.

\subsubsection{Corridor%
  \label{corridor}%
}

The corridor is a simple entity where the only adjustable parameter is its \emph{length}. The length is defined with the \hyperref[simplex-range]{simplex\_range} function with position as input. At the end of the corridor an exit door is created. Only one \hyperref[corridor-model]{model} is used for rendering and it is repeated until the desired length is reached.

\begin{figure}
\noindent\makebox[\textwidth][c]{\includegraphics[width=0.700\linewidth]{corridor.png}}\phantomsection\label{corridor-model}

\caption{The corridor model.}
\end{figure}

\subsubsection{Elevator%
  \label{elevator}%
}

The elevator is similar to the \hyperref[corridor]{corridor} entity. With the difference that it extends in the vertical direction. Hence the \emph{height} is the only adjustable parameter, populated by the \hyperref[simplex-range]{simplex\_range} function, with position as input. The model for this entity looks a bit different since it also has an animated cart, as shown in the \hyperref[elevator-model]{image}. The model is repeated vertically until the desired height is reached.

\begin{figure}
\noindent\makebox[\textwidth][c]{\includegraphics[width=0.700\linewidth]{elevator.png}}\phantomsection\label{elevator-model}

\caption{The elevator model, with the cart to the left.}
\end{figure}

\subsubsection{Room%
  \label{room}%
}

The room is the most advanced and most configurable entity. Meaning that it can change much in appearance depending on what values are used to create it. The main values are its \emph{size} in two dimensions and the room \emph{type}. The \hyperref[simplex-range]{simplex\_range} function is used to initialize both, with room position as input. The input position is scaled a bit for the second \emph{size} dimension, to not get square rooms.

The \emph{type} value determines which set of models to use when creating the room. There are three sets, one with stone material one with metal material and one with wood material. There are several models that builds a room such as floor, edge models and corners. Some of the variations are shown in the \hyperref[room-edges]{room edges} figure.

\begin{figure}
\noindent\makebox[\textwidth][c]{\includegraphics[width=0.700\linewidth]{room_edges.png}}\phantomsection\label{room-edges}

\caption{Different types of room edges.}
\end{figure}

When the room \emph{type} is determined, the corresponding set of models are used to build the room. A two dimensional loop fills the room with models. Edge models for walls, special models for corners, entries, exits and floor models in the middle. What model variation that is used depends on the \hyperref[simplex-range]{simplex\_range} function with model position as input. As seen in the \hyperref[room-edges]{room edges} figure, the stone material room has many variations. Walls are also varied slightly in height with the \hyperref[simplex-range]{simplex\_range} function.

\subsection{Stairs%
  \label{stairs}%
}

Stairs are similar to the \hyperref[corridor]{corridor} with its only adjustable parameter being its \emph{length}. This variable is again populated by the \hyperref[simplex-range]{simplex\_range} method with position as input. The difference is that the stairs extends both vertically and horizontally. An exit door is added to the end of the model. There two versions of this entity, one that goes up and one that goes down, as shown in the \hyperref[stairs-models]{stairs models} figure.

\begin{figure}
\noindent\makebox[\textwidth][c]{\includegraphics[width=0.700\linewidth]{stairs.png}}\phantomsection\label{stairs-models}

\caption{Stairs up and down.}
\end{figure}

\section{Items%
  \label{items}%
}

To further spice up the environment, some extra items are added to each \hyperref[room]{room}. If they are placed on a floor model in the \hyperref[room]{room} depends on the \hyperref[simplex-bool]{simplex\_bool} function and the model position. Which item is used is determined by \hyperref[simplex-range]{simplex\_range}, and the same position. The \hyperref[item-models]{item models} are shown below:

\begin{figure}
\noindent\makebox[\textwidth][c]{\includegraphics[width=0.700\linewidth]{items.png}}\phantomsection\label{item-models}

\caption{A table, a package and a tree.}
\end{figure}

\section{Algorithm%
  \label{algorithm}%
}

To generate a dungeon the first entity has to be created manually. Then a loop iterates through all the entities, a defined number of times. Each time the loop checks for doors in each entity that has an empty pointer to their next entity. If that is the case a new entity is created and linked to that pointer.

Before the entity is linked to the door. The entity bounding box is checked for collision with all other bounding boxes in the level. If a collision is detected, the entity is discarded and the door hence leads nowhere. The door state is marked as closed in this case.

What type of entity that is generated is decided by a method that takes the door position as input and uses the \hyperref[simplex-range]{simplex\_range} method to get an index value. The index value is used on a container filled with all types of entities described in previous sections. When each entity is created it takes the door transform as input for further processing.

\section{Implementation%
  \label{implementation}%
}

The implementation is done in C++ with a couple of helper libraries. One is \href{https://github.com/morganbengtsson/mos}{Mos}, mainly used for defining models and meshes for rendering. Another important one is \href{http://glm.g-truc.net/0.9.8/index.html}{GLM}, which is used for all the maths. Especially the simplex noise method that is essential for the \hyperref[algorithm]{algorithm} and the procedural nature of all the entities. All models are made with \href{https://www.blender.org/}{Blender}.

The level is generated in its own thread at start up, to show how the dungeon generates and not to stall the rendering.

The code itself is available at \url{https://github.com/morganbengtsson/dungeon} and can be downloaded with the following git command:
%
\begin{quote}{\ttfamily \raggedright \noindent
git~clone~-{}-recursive~https://github.com/morganbengtsson/dungeon.git
}
\end{quote}

\subsection{Build%
  \label{build}%
}

The application uses \href{https://cmake.org/}{CMake} as the build system. To build, create a directory named \emph{build} in the downloaded source  directory. From the \emph{build} directory run the following command:
%
\begin{quote}{\ttfamily \raggedright \noindent
cmake~..
}
\end{quote}

This should generate appropriate Makefiles for the Linux platform, or a Visual Studio project on the Windows platform.

\section{Results and discussion%
  \label{results-and-discussion}%
}

A \href{https://www.youtube.com/watch?v=-ZhnmNAsNJo}{video} of the resulting application is available along with a \hyperref[screenshot]{screenshot} below:

\begin{figure}
\noindent\makebox[\textwidth][c]{\includegraphics[width=0.700\linewidth]{screenshot.png}}\phantomsection\label{screenshot}

\caption{The resulting dungeon after six iterations.}
\end{figure}

The results for generating a dungeon procedurally this way are quite positive. With only a few basic models it is possible to generate a quite versatile dungeon. Many parameters are tweak-able, to quickly get a desired result. In contrast to manual modeling, which would take much longer. Also the numerical representation of a whole dungeon is very compact, only the first entity and a position.

Improvements that could be done are optimizations to the rendering. Even more variations in the different entities. The \hyperref[room]{room} could be customized even further for example. With more floors, different shapes and materials. Procedural methods could have been used even further, to place or randomize vertex positions in the models. That would be at the cost of performance though.

\end{document}

max_stars_repo_name: morganbengtsson/dungeon

max_issues_repo_name: morganbengtsson/dungeon

max_forks_repo_name: morganbengtsson/dungeon


text:
\documentclass[a4paper,onepage]{memoir}

\setulmarginsandblock{4cm}{*}{1}
\setlrmarginsandblock{2cm}{*}{1}
\checkandfixthelayout

\usepackage{tikz}
\usetikzlibrary{shapes}
\usepackage{gurps}
\usepackage{xparse}
\usepackage{multicol}

% Typographical nicities
\usepackage{microtype}
\usepackage{lettrine}
\usepackage{ragged2e}

\usepackage{gurps-npccard}

\usepackage{hyperref}

\setlength{\RaggedRightParindent}{\parindent}
\RaggedRight

\setsecnumdepth{chapter}

\setsechook{\clearpage}
\setsecheadstyle{\bfseries\Huge\centering}

\setsubsecheadstyle{\bfseries\Large\raggedright}

\setsubsubsecheadstyle{\scshape\normalsize\raggedright}
\setaftersubsubsecskip{-1em}

\NewDocumentCommand{\from}{mm}{\mbox{#1 from \emph{#2}}}
\NewDocumentCommand{\cardandstuff}{m}{
\hfill
\begin{minipage}[c]{1in}
  \centering
  % hex
  \begin{tikzpicture}
    \node[regular polygon,regular polygon sides=6,draw,inner sep=0.31in] at (0,0) {};
  \end{tikzpicture}\\[2em]
  % cardboard hero
  \begin{tikzpicture}[x=1in, y=1in]
    \draw (0,0) rectangle (0.5, -0.325); \draw (0.25,-0.325) -- (0.25,-0.1625);

    \draw (0,0) rectangle (0.5,2); \draw (0,1) -- (0.5,1);

    \draw (0,2) rectangle (0.5, 2.325); \draw (0.25,2.325) -- (0.25,2.1625);
  \end{tikzpicture}
\end{minipage}
\hfill
\begin{minipage}[c]{5.1in}
  \printcharactercard{#1}
\end{minipage}
\hfill
}

\NewDocumentEnvironment{npcdescription}{}{
  \subsection{Description}%
  \begin{multicols}{3}}{\raisebox{0.1ex}{\tikz\node[draw,fill=black,inner
  sep=0.7ex] {};}\end{multicols}}
\begin{document}

\title{Portfolio of proposed \gurps NPCs}
\author{Nathanael Farley\thanks{\SJGamesOnlinePolicyGameAid{Nathanael Farley}}}
\maketitle

\tableofcontents

\section{Debbie Dyers}
\label{sec:debbie-dyers}

\begin{character*}[Debbie Dyers]
  \characterpicture{default.png}
  \ST{11} \DX{13} \IQ{12} \HT{12}
  \Will{15}

  \DR{15}

  \levelledadvantage{Hard to Kill}{2}
  \advantage{360\textsuperscript{o} Vision (Infrared only)}
  \advantage{Extra Attack}[25]
  \advantage{Signature Gear (Infrared sensor body suit)}

  \disadvantage{Vow (never return home)}[-5]

  \skill{Guns (cordite pistol)}{16}
  \skill{Karate}{18}
\end{character*}

\hfill
\begin{minipage}[c]{1in}
  \centering
  % hex
  \begin{tikzpicture}
    \node[regular polygon,regular polygon sides=6,draw,inner sep=0.31in] at (0,0) {};
  \end{tikzpicture}\\[2em]
  % cardboard hero
  \begin{tikzpicture}[x=1in, y=1in]
    \draw (0,0) rectangle (0.5, -0.325); \draw (0.25,-0.325) -- (0.25,-0.1625);

    \draw (0,0) rectangle (0.5,2); \draw (0,1) -- (0.5,1);

    \draw (0,2) rectangle (0.5, 2.325); \draw (0.25,2.325) -- (0.25,2.1625);
  \end{tikzpicture}
\end{minipage}
\hfill
\begin{minipage}[c]{5.1in}
  \printcharactercard{Debbie Dyers}
\end{minipage}
\hfill

\subsection{Meta stats}
\subsubsection{Character inspirations:} \from{The prodigal son}{New Testament};
\from{Trinity}{The Matrix}.

\begin{npcdescription}
  \lettrine{D}{ebbie} Dyers is an independent bounty hunter who is legendary in
  the right circles. She comes from a long line of hunters, the first of which
  was recorded on earth who was allgegedly a `monster hunter' according to
  family folklore

  An imposing figure at 6'2" with fiery red hair which extends to her shoulders.
  She is usually sporting a trenchcoat which hides her extensive weaponry and
  equipment.

  Markedly against bio-enhancements, she has a special vest which gives her
  360\textsuperscript{o} heat vision allowing her to aim at two (heat based)
  targets at once.
\end{npcdescription}

\section{Leslie ``Trunchball'' Dyers}
\label{sec:lesl-trunchb-dyers}

\begin{character*}[Leslie Dyers]
  \characterpicture{default.png}
  \ST{15} \DX{11} \IQ{11} \HT{12}

  \skill{Brawling}{16}
\end{character*}

\cardandstuff{Leslie Dyers}

\subsection{Meta stats}
\subsubsection{Character inspirations:} \from{Trunchball}{Matilda};
\from{Kingpin}{Spiderman}; \from{Tahani}{The Good Place}.

\begin{npcdescription}
  \lettrine{L}{eslie} ``Trunchball'' Dyers is a strong woman, \emph{literally!}
  The kingpin of her own empire, Trunchball has built her bounty hunter company
  from the ground up into one of the premier bounty hunter the local area. A
  formidable force herself once, she now sits behind a desk dealing with the day
  to day of the business. She seems to take personal pleasure in chewing out
  bounty hunter employees who mess up.

  However, she is haunted by her inability to get approval from her parents. Her
  sister, the golden child, always seems to get preferential treatment no matter
  what they do despite the fact that she has disavaowed her parents. To this
  day, Trunchball is still highly motivated to gain the approval she percieves
  she has never recieved.

  When called into combat, Trunchball dons elbow length power gloves, amplifying
  her strength to well beyond human limits.
\end{npcdescription}

\section{Crystalline}
\label{sec:Crystalline}

\begin{character*}[Crystalline]
  \characterpicture{default.png}
  \ST{9} \DX{11} \IQ{13} \HT{10}

  \disadvantage{Short lifespan (crystalline disease)}
  \quirk{Socially awkward}

  \skill{Computer Programming}{18}
  \skill{Computer Hacking}{18}
  \skill{Computer Operations}{19}
\end{character*}

\cardandstuff{Crystalline}

\subsection{Meta stats}
\subsubsection{Character inspirations:} \from{Abby Sciuto}{NCIS}.
\subsubsection{Soundtrack:} \href{https://www.youtube.com/watch?v=s4iLX7eWwmE}{Crystalline -- The Midnight}

\begin{npcdescription}
  \lettrine{I}{nfected} with a fatal disease that turns her skin to crystal on
  contact with water during a raid on a government testing facility, Crystalline
  is the archetypal hacker in the basement. Due to her condition, she rarely
  socialises but devotes all her time to hacking into whoever pays her the most.

  She will occasionaly risk outside contact but only for those she \emph{truly}
  trusts.
\end{npcdescription}

\NewDocumentCommand{\shadow}{}{\$hadow}
\section{\$hadow}

\begin{character*}[shadow]
  \characterpicture{default.png}
  \ST{10} \DX{12} \IQ{13} \HT{10}
  \Will{16}

  \skill{Computer Hacking}[IQ/Hard]{13}
  \skill{Assasin!}[DX/Wildcard]{16} %No point in separating out all the assasiny
                                %things he does

  % Necro-psi
  \advantage{Corpse Sense 1}[26]
  \skill{Corpse Sense}[Per/Hard]{24}
  %TODO replace with technique when GURPS LaTeX package supports it
  \skill{Flashes of Insight}{24}

  \advantage{Silhouette 4}[72]
  \skill{Silhouette}[Will/Hard]{16}
\end{character*}

\cardandstuff{shadow}

\subsection{Meta Stats}

\begin{npcdescription}
  \lettrine{N}{ecro-psi} computer hacker, \shadow\ is the man when you want
  information, but you don't want to know where it comes from.

  Presumably from a normal home, very little information is known about \shadow.
  What is known is that he has the ability to slip in and out of facilities by
  turning into a silhouette. He alwasy get sthe information he has been hired to
  get. But there is always a terrible cost, at least one person from the company
  always dies. Some say that it is \shadow\ himself, killing them so he can read
  the mind of the dead. But surely such a thing is not possible...

  % He becomes a silhouette by rotating in a curled dimension. Since light goes
  % through all dimensions, he becomes a 3D silhouette and easily blends into the
  % background.

  Abilities include:
  \begin{description}
  \item[Silhouette] Shift into pure shadow, allowing access to areas usually
    forbidden. See \#3/99 for more details.
  \item[Garotte] Literally, a garotte
  \item[Flashes of Insight] Signature move: read the mind of a recently deceased
    sysadmin (who may or may not have come in contact with a garotte) and get
    the admin password direct from their memory. Will prefer the snapshot
    version of this ability with the penalties listed in \#3/99.
  \end{description}

  Suffice to say, you probably don't want to meet \shadow\ in a dark alley. Or
  at all. He takes payment by wire transfer and secure email.
\end{npcdescription}

\begin{multicols}{2}
  \SetCharacterKey{shadow}
  \GCPrintCharacter
  \ResetCharacterKey
\end{multicols}
\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:

ext: tex


text:
\chapter{Conclusion}
\label{sec:conclusion}

max_stars_repo_name: Estevo-Aleixo/dynamicstructures

max_issues_repo_name: Estevo-Aleixo/dynamicstructures

max_forks_repo_name: Estevo-Aleixo/dynamicstructures


text:
\chapter{PAWS - Towards PIPS as Web Service}

This first chapter introduces the idea of creating PaWS framework. It
answers two questions: why it is needed? and on what it is based? Design
constraints and functional requirements also are presented here. They
resulted in the emergence of three main modes for PaWS. They are
described in the next section (?). The last part of this chapter presents
the creation process of PaWS.

\input{reportCh1/paws}
\input{reportCh1/constraints}
\input{reportCh1/requirements}
\input{reportCh1/goals}
\input{reportCh1/process}

\section{Conclusion}

PaWS is a lightweight and easy to use application, although it lies on
top of a very complex toolkit, which is PIPS. The design contraints
and requirements were evolving over time, using feedback from the
previous iteration. Different user modes, with a significant amount of
examples, were added.  It was necessary to provide flexibility in
configuring and maintaining PaWS. It required using good architectural
solution and proven tools or libraries. These issues are described in
the subsequent chapters.


text:
\documentclass{article}
\usepackage[minionint,mathlf,textlf]{MinionPro} % To gussy up a bit
\usepackage[margin=1in]{geometry}
\usepackage{graphicx} % For .eps inclusion
%\usepackage{indentfirst} % Controls indentation
\usepackage[compact]{titlesec} % For regulating spacing before section titles
\usepackage{adjustbox} % For vertically-aligned side-by-side minipages
\usepackage{array, mathrsfs, mhchem, amsmath} % For centering of tabulars with text-wrapping columns
\usepackage{hyper ref}
\usepackage[autolinebreaks,framed,numbered]{mcode}
\pagenumbering{gobble}
\setlength\parindent{0 cm}
\begin{document}
\large

\section*{Introduction to stochastic differential equations}
An alternative approach to studying stochastic systems uses stochastic differential equations. You may have seen one written in the Langevin notation, e.g.:
\[ \frac{dx}{dt} = \mu(x,t) + \sigma (x,t) \eta (t) \]
where $\eta(t)$ represents ``random fluctuations." For such equations, we must specify characteristics of the deviations $\eta$, e.g., the type of distribution they are drawn from, its parameters, and their time correlation:
\[ C(\tau) = \left< \eta(0) \eta(\tau) \right> = \lim_{T \to \infty} \frac{1}{T} \int_0^{T} \eta(t)\eta(t+\tau)\, dt \]
$C$ should be a decreasing function of $\tau$\footnote{Note that time correlations for variables in a system may have very different shapes: consider, for example, the correlation function for an oscillator.}: a fast fall-off tells us that the fluctuations change quickly. For example, fluctuations in temperature might occur on the timescale of hours (illumination), months (seasons), and eons (ice ages). If the fluctuations are occurring much faster than our timescale of interest, we might make the simplifying assumption that they are not correlated at all in time:
\[ \left< \eta(0) \eta(\tau) \right> = c \delta(\tau) \]
Here $\delta$ represents the Kronecker delta and $c$ is the second moment of $\eta$, which will depend on the distribution of $\eta$\footnote{If $\eta \sim \mathcal{N}(0,1)$, $c=1$.}. Fluctuations with zero time correlation are often called \textit{white noise}. The term \textit{noise} comes by analogy to measurement noise: a major difference is that noise in measurement does not affect the future evolution of the system. When $\sigma(x,t)$ is a constant, we say that the noise is additive (just ``tacked on" to the deterministic solution); otherwise, we say that the noise is multiplicative.\\

White noise can be approximated in an otherwise deterministic simulation by taking small time steps and drawing a random variable to plug in for $\eta$ at each time step. We can use this to simulate sample realizations of an SDE, but maybe not in the way you'd expect na\"{i}vely. For example, you might suspect that the analog of Euler's method for a stochastic differential equation with (normal) Gaussian white noise is:
\[ x(t+\Delta t) = x(t) + \left[ \mu(x,t) + \sigma(x,t) \eta\right] \, \Delta t,   \hspace{3 cm} \eta \sim \mathcal{N}(0,1) \]
This is close, but not quite right. The actual equivalent, given by the Euler-Maruyama method, is:
\[ x(t+\Delta t) = x(t) + \mu(x,t) \, \Delta t + \sigma(x,t) \eta \, \sqrt{\Delta t},   \hspace{3 cm} \eta \sim \mathcal{N}(0,1) \]
Later in this lecture we will discuss why this is so; however, I emphasize that there is a very rich literature on analysis of SDEs and that if this topic interests you, a proper course on stochastic processes or stochastic calculus (e.g. Stats 171) would be an appropriate next direction.\\

Our prior discussions of stochastic modeling have been motivated by the common-sense notion that molecule numbers in real biological systems are discrete and sometimes too low to legitimize continuous approximations. By contrast this \textit{Langevin approach} restores us to the realm of continuity and imposes a distribution on noise which may be patently unrealizable. Motivating this treatment of noise requires context-dependent explanation, and for both historical and epistemic reasons there is no better place to start than with Brownian motion. What we learn about diffusion will be helpful later in our study of development and Turing patterns. We will begin by studying Brownian motion with more familiar approaches and eventually formulate it in terms of a Wiener process.

\section*{Brownian motion}

Robert Brown, observing pollen grains (and inorganic material) suspended in water in the mid 1820s, noticed that they appeared to move erratically and without proximate cause. Einstein correctly asserted that individual water molecules imparted momentum on colliding with the pollen granule: many such collisions might sum to give a net momentum in a random direction, in which the pollen granule would briefly travel before additional collisions changed its trajectory once again. The fluctuations in position under \textit{Brownian motion} occur on such short time scales relative to what we are able to observe physically that we can think of them as white noise. By symmetry, the distribution of fluctuations should be even, that is, $f(x)=f(-x)$ and therefore have an average value of zero.\\

During Einstein's miracle year (1905), he published a paper establishing a formula for the mean square displacement of a particle undergoing Brownian motion via a derivation of Fick's second law and a description of the diffusion coefficient $D$. He started from nothing but the assumption that the probability distribution for a displacement $y$ in a small time period $\tau$ would be given by some $p(y)$, with $p$ even and normalized. His method assumes a large ensemble of $n$ particles: the number changing position by a distance between $y$ and $y + dy$ units in a time $\tau$ would therefore be:
\[ dn = n p(y) dy \]
Denoting the particle concentrations at a time $t$ by $c(x,t)$, we can calculate the concentrations a short while later by:
\begin{eqnarray}
 c(x,t+\tau) = \int_{-\infty}^{\infty} c(x-y,t) \, p(y) \, dy \label{eqn:conv}
 \end{eqnarray}
Particles can move to point $x$ from any other position (though the probability of moving there from far away is lower): this convolution integral sums all of those contributions to the concentration at point $x$ after a time $\tau$ has passed. This general concept should be reminiscent of the master equation and the convolution integrals you have studied in this course. To get somewhere interesting, we perform some Taylor expansions and plug in to Equation \ref{eqn:conv}:
\begin{eqnarray*}
c(x,t+\tau) & \approx & c(x,t) + \tau \frac{\partial c}{\partial t} \hspace{1 cm} \textrm{($\tau$ small)}\\
c(x-y,t) & = & c(x,t) -y \frac{\partial c}{\partial x} + \frac{y^2}{2} \frac{\partial^2 c}{\partial x^2} - \frac{y^3}{3!} \frac{\partial^3 c}{\partial x^3} + \ldots\\
 c(x,t) + \tau \frac{\partial c}{\partial t} & = & \int_{-\infty}^{\infty}  \left[ c(x,t) -y \frac{\partial c}{\partial x} + \frac{y^2}{2!} \frac{\partial^2 c}{\partial x^2} - \frac{y^3}{3!} \frac{\partial^3 c}{\partial x^3} + \ldots \right] \, p(y) \, dy\\
 & = & c(x,t) \int_{-\infty}^{\infty} p(y) \, dy - \frac{\partial c}{\partial x}  \int_{-\infty}^{\infty} y \, p(y) \, dy + \frac{1}{2!} \frac{\partial^2 c}{\partial x^2} \int_{-\infty}^{\infty} y^2 \, p(y) \, dy + \ldots
\end{eqnarray*}
Since $p(y)$ is normalized, we can cancel $c(x,t)$ from both sides of the equation. Moreover, since $p(y)$ is odd, the value of the integrals will be zero for all odd powers of $y$, so that we are left with:
\begin{eqnarray*}
\tau \frac{\partial c}{\partial t} & = & \frac{1}{2!} \frac{\partial^2 c}{\partial x^2} \int_{-\infty}^{\infty} y^2 \, p(y) \, dy + \frac{1}{4!} \frac{\partial^4 c}{\partial x^4} \int_{-\infty}^{\infty} y^4 \, p(y) \, dy + \ldots
\end{eqnarray*}
Noting that the terms at right are decreasing rapidly in value, and defining $D=\frac{1}{2\tau} \int_{-\infty}^{\infty} y^2 p(y) \, dy$, we arrive at Fick's second law (so named for the person who discovered it empirically half a century prior), otherwise known as the diffusion equation:
\[ \frac{\partial c}{\partial t} = D \frac{\partial^2 c}{\partial x^2} \]
We can now introduce by ansatz\footnote{I have posted a derivation for those interested; it is omitted here for employing the residue theorem and some gnarly Gaussian integrals.} a solution to this equation for the initial condition where the concentration is initially one at the origin:
\[ c(x,t) = \frac{1}{\sqrt{4 \pi D t}} e^{-x^2/4Dt} \]
Although we did not bother to derive it, let's pause to celebrate the existence of this solution, which is diffusion's equivalent of an impulse response function. (In some disciplines, the term ``Green's function" is more common than ``impulse response function." The underlying concepts are equivalent but you are more likely to find examples incorporating spatial dimensions if you look up Green's functions.) Since you know how particles that start diffusing from a certain point at time $0$ will behave, you can use a convolution integral to describe how \textit{any} initial spatial configuration of particles will evole with time. On problem set eight, you'll use this concept to explore how fluorescence recovery after photobleaching (FRAP) can be used to measure the diffusion constant.\\

The mean of this even function is clearly zero; the second moment (and thus the variance) can be found using a simple trick based on the normalization
\begin{eqnarray*}
- \int_{\infty}^{\infty} e^{-x^2/4Dt} \, dx & = & - \sqrt{4\pi D t} \hspace{1 cm} \textrm{ Letting $y=1/4 D t$:}\\
- \frac{\partial}{\partial y} \int_{\infty}^{\infty} e^{-x^2/4Dt} \, dx =
\int_{\infty}^{\infty} x^2 e^{-x^2/4Dt} \, dt & = & - \frac{\partial}{\partial y} \frac{\sqrt{\pi}}{\sqrt{y}} = 2 D t \sqrt{4 \pi D t}\\
\left< x^2 \right> = \int_{\infty}^{\infty} x^2 c(x,t) \, dx  & = & 2 D t\\
\sigma_x^2 = \left< x^2 \right>  - \left< x \right>^2 & = & 2Dt
\end{eqnarray*}
Through an independent derivation of the diffusion coefficient of a hard sphere of radius $r$ in media with viscosity $\eta$, $D=k_B T / 6\pi r \eta$, Perrin was able to use this equation to calculate Boltzmann's constant and thus Avogadro's number. Perrin's experiment was done with small uniform spheres in saline solution on a cover slip: he used a camera lucida to record the position of these spheres at time intervals and thus to calculate $\left< x^2 \right>$. (A 2006 reiteration of this experiment is described in Newburgh et al.'s paper on the course website.)\\

Let's reflect briefly on how we arrived here: Einstein did not make any unjustified assumptions about $p(y)$ -- indeed, never calculated it - but still gave us a deterministic formula for the time evolution of the concentration profile. Focusing on the concentration profile was the key: anything unusual that might befall an individual molecule is ``averaged out" in the ensemble. Intuition and frequent exposure to the ergodic hypothesis accurately suggest that the probability distribution of a single molecule should reflect the normalized concentration profile, we we shall soon see.

\section*{Langevin's derivation}
Langevin's alternative derivation (1908) of the variance in a particle's position was one of the first attempts to employ stochastic differential equations to understand a natural phenomenon: some concerns with the rigor of his approach drove the development of modern stochastic analysis. He envisioned a single pollen granule buffetted by a ``random force" $f_r(t)$ due to impacts with molecules of the fluid and also experiencing the force of viscous (Stokes) drag:
\begin{eqnarray}
 F_{\textrm{net}} = m \frac{d^2x}{dt^2} & = & - b \frac{dx}{dt} + f_r \label{eqn:start}
 \end{eqnarray}
Like Einstein, Langevin makes no assumptions about $f_r(t)$ other than ``that it is indifferently positive and negative and that its magnitude is such that it maintains the agitation of the particle, which the viscous resistance would stop without it." ($b$ is a Stokes drag coefficient with units of kg/s.) In this way he set about proving the single-particle equivalent of Einstein's result concerning the mean square displacement.\\

Starting from equation \ref{eqn:start}, multiply both sides by $x$ and rearrange\footnote{Notice that we are not following Langevin's derivation precisely: Langevin's solution ignores the behavior at short timescales and requires ignoring an exponential term after the first integration. Otherwise all assumptions are Langevin's. } to find:
 \begin{eqnarray*}
m \left( \frac{d}{dt} \left[ x \frac{dx}{dt} \right] - \left[ \frac{dx}{dt} \right]^2 \right) & = & - b x \frac{dx}{dt} + f_r x
\end{eqnarray*}
Take the average of both sides, exploiting the commutativity of derivatives and averages:
 \begin{eqnarray*}
m \frac{d}{dt} \left< x \frac{dx}{dt} \right> - \left< mv^2 \right> & = & - b \left< x \frac{dx}{dt} \right> + \left< f_r x \right>
\end{eqnarray*}
Langevin stipulated that $\left< x f_r \right>$ is zero. The equipartition theorem describes the relationship between the average kinetic energy of a particle and the temperature: $\left< \frac{1}{2} mv^2 \right> = \frac{1}{2}k_b T$. Inserting theese values, we obtain:
 \begin{eqnarray*}
 \frac{d}{dt} \left< x \frac{dx}{dt} \right> + \frac{b}{m} \left< x \frac{dx}{dt} \right>  & = & \frac{k_B T}{m}
\end{eqnarray*}
There is nothing left to do but integrate. We use an integrating factor method, multiplying both sides by $e^{bt/m}$ and rearranging:
 \begin{eqnarray*}
 \frac{d}{dt} \left[ e^{bt/m} \left< x \frac{dx}{dt} \right> \right]  & = & \frac{k_B Te^{bt/m}}{m} \implies  \left< x \frac{dx}{dt} \right> = \frac{k_B T}{b} \left( 1 + e^{-bt/m} \right)
\end{eqnarray*}
assuming the particle is initially at the origin for convenience. Finally, noting that $x \dot{x} =  \frac{1}{2} d(x^2)/dt$:
\[ \frac{d}{dt} \left< x^2 \right> = \frac{2 k_b T}{b} \left( 1 - e^{-bt/m} \right) \implies \left< x^2 \right>  = \frac{2 k_b T }{b} \left(t + \frac{m}{b} \left[  1 - e^{-bt/m} \right] \right)  \]
Compare two limiting cases:
\[ \left< x^2 \right> = \left\{
     \begin{array}{lr}
       k_B T t^2/b & : t \ll m/b \\
       2k_BTt/b & : t \gg m/b
     \end{array}
   \right. \]
In other words, at short times the particle behaves like it's traveling in a straight line: its rms distance from the origin is increasing linearly with time. At longer timescales the particle is properly thought of as diffusing, with $D=k_BT/b$\footnote{The latter relation, $D=k_BT/b$, is an instantiation of the fluctuation-dissipation theorem, developed two decades later by our old friend Nyquist.}. Any assumptions made about the nature of the random force have not deprived us of the expected behavior at long and short timescales. For a sense of proportion, $m/b \approx 10^{8}$ Hz for a pollen granule, so the crossover time is on the order of nanoseconds.\\

While we may be satisfied with the sense these results seem to make, and certainly their consistency with Einstein's result, we should pause to reflect on whether Langevin's treatment of $f_r(t)$ was justified. Is $x(t)$ twice differentiable, and if not, how can we rationalize writing a differential equation in terms of $d^2x/dt^2$? What exactly is $f_r$ and is it fair to assume that it behaves as claimed, e.g. $\left< x f_r \right>=0$? (How do you propose to evaluate the integral of $xf_r$ in order to calculate this average?) What does an integral of such a random function look like? These questions and Langevin's cavalier treatment gave rise to the field of stochastic analysis and to such jabs as:

\begin{quote}
``A stochastic differential equation is introduced in a rigorous fashion to give a precise meaning to the Langevin equation for the velocity function. This will avoid the usually embarrassing situation in which the Langevin equation, involving the second- derivative of $x$, is used to find a solution $x(t)$ not having a second-derivative."\\
-- Doob, 1942.
\end{quote}

\section*{Wiener processes}

The integral of $\eta(t)$ is an unusual construct which we begin by defining as the \textit{Wiener process} $W_t$:
\[ W_t = \int_0^t \eta(s) \, ds, \hspace{2 cm} \eta(s) \sim \mathcal{N}(0,1) \textrm{ and } \left< \eta(0) \eta(\tau) \right> = \delta(\tau) \]
Heuristically, a Wiener process $W_t$ may be envisioned as a random walk where the step at time $t$ is $\eta_t$, a random variable drawn from $\mathcal{N}(0,1)$. The process is named after Norbert Wiener, who described its properties in the 1920s before going on to found cybernetics, the antecedent of systems biology. Norbert contributed to both World Wars, formalizing the notion of feedback in application to the development of anti-aircraft guns. He turned his attention to the frontier of neuroscience and robotics, recruiting Pitts and McCullogh (whose artifical neuron we have already studied) to MIT where they contributed substantially to the fields of computer science and artificial intelligence. (After artificial intelligence split off as its own field, cybernetics was downgraded to a social science and prompty began to circle the drain.)\\

The process is continuous everywhere but differentiable nowhere\footnote{Continuity can be shown using Kolmogorov's continuity theorem; the latter can be shown from the scaling of variance with time for a Wiener process.}. Two defining properties are that $W(0)=0$ and that $W(t+\tau) - W(t)$ is normally distributed with mean zero and variance $\tau$\footnote{To see why, consider the Wiener process's current displacement from the original position to be the limit of the sum $\sum_{i=1}^N \eta_i \, dt$ where $dt = \tau/N$. Then by the Central Limit Theorem, $W(t+\tau) - W(t) \sim \mathcal{N}(0\cdot N \, dt, 1 \cdot N \, dt) = \mathcal{N}(0,\tau)$.}. Notice that this probability distribution has exactly the same form as the Green's function found above for a concentration profile, if we chose $D=1/2$:
\[ P(W(t+\tau)-W(\tau) =x \, | \, t) = \frac{1}{\sqrt{2\pi t}} e^{-x^2/2t} \]
Now that we know these properties we can revisit the Euler-Maruyama method for simulating systems of the form:
\[ \frac{dx}{dt} = \mu(x,t) + \sigma(x,t) \eta(t) \implies dx = \mu(x,t) dt + \sigma(x,t) \, dW_t \hspace{1 cm} \left( \frac{dW_t}{dt} = \eta(t) \right) \]
Since $W(t+\Delta t) - W(t) = \Delta W_t \sim \mathcal{N}(0,\tau) = \sqrt{\tau} \mathcal{N}(0,1)$,
\[ x(t+\Delta t) = x(t) + \mu(x,t) \, \Delta t + \sigma(x,t) \, \Delta W_t =  x(t) + \mu(x,t) \, \Delta t + \sqrt{\Delta t}\,  \sigma(x,t) \,  \eta(t),  \]
just as we claimed earlier in the lecture.\\

\section*{Stochastic integrals}

Now that we have defined the integral of $\eta(t)$ as a Wiener process, consider that for the same system,
\[ x(t) = x(0) + \int_0^t \mu(x,\tau) \, d\tau + \int_0^t \sigma(x,\tau) \, dW_{\tau} \]
If we could take these integrals we'd find a closed form for $x(t)$ in terms of $W_t$, which would be very useful. Consider two different ways of approximating the second integral by sums of $N$ terms with $t_j = j \times \frac{t}{N}$:
\[ \int_0^t \sigma(x,\tau) \, dW_{\tau} \approx \sum_{k=0}^N \sigma(x,t_{j}) \left[ W_{t_{j+1}} - W_{t_j} \right] \textrm{ or } \sum_{k=0}^N \left[ \frac{\sigma(x,t_{j+1}) + \sigma(x,t_{j})}{2} \right] \left[ W_{t_{j+1}} - W_{t_j} \right] \]
The only difference is in whether we choose to evaluate $\sigma$ at the beginning or in the middle of the time step -- a distinction that would not make a lick of difference as $N \to \infty$ with your standard-issue Riemann integral. However, the sum is different for stochastic integrals (try simulating it!). The sum at left is the It\={o} formulation of a stochastic integral; the one at right is the Stratonovich formulation. As to which is more appropriate, van Kampen notes that for radioactive decay\footnote{Note that we have chosen $\sigma(x)=\sqrt{x}$ since we know this is a Poisson process and thus the variance in decays within a time interval is equal to the mean number of decays in that time interval.}:
\[ dx = - k x \, dt + \sqrt{x} \, dW_t \]
and other reactions, it makes sense to evaluate $\sigma$ at the beginning of the interval, and in fact we get an incorrect mean if we use the Stratonovich formulation. In principle the It\={o} formulation is appropriate when the time correlation in noise terms is precisely zero.\\

Why does it matter which formulation is chosen? As the inequality of the sums above suggests, your favorite rules from calculus do not always apply, though they have counterparts. For example, if $Y(W_t)=(W_t)^2$, then is $dY = 2 W_t \, dW_t$? In the Stratonovich formulation, yes; in the It\={o} formulation, $dY = 2 W_t \, dW_t + dt$. This implies another mind-bender in It\={o} calculus:
\[ W_t^2 = Y = Y(0) + 2 \int_0^t W_t \, dW_t + \int_0^t ds \implies \int_0^t W_t \, dW_t  = \frac{1}{2} W_t^2 - \frac{t}{2} \]
In the words of Ramon van Handel:
\begin{quote}
``The reader is probably left wondering at this point whether we did not get a little carried away. We started from the intuitive idea of an ordinary differential equation driven by noise. We then concluded that we can not make sense of this as a true differential equation, but only as an integral equation. Next, we concluded that we didn't really know what this integral is supposed to be, so we proceeded to make one up. Now we have finally reduced the notion of a stochastic differential equation to a mathematically meaningful form, but it is unclear that the objects we have introduced bear any resemblance to the intuitive picture of a noisy differential equation."\\
-- Caltech ACM 217 lecture notes (2007)
\end{quote}
If you begin to question whether we are on to something worthwhile, consider an application of the method to a stock's price, $x$:
\[ dx = \mu x \, dt  + \sigma x \, dW_t = x \left[ \mu \, dt + \sigma \, dW_t \right] \hspace{2 cm} \mu, \sigma \in \mathbb{R} \]
The intuition captured here is that stock prices tend to increase exponentially, but with a variable rate\footnote{For Poisson processes we expect mean and variance to be equal, and thus often choose $\sigma(x,t) \sim \sqrt{x}$. Here we have $\sigma(x)\sim x$ implying that standard deviation and mean are equal: this is a property of the exponential distribution.}. (The formula is only realistic when the stock price stays positive, of course.) The solution to this equation is:
\[ x(t) = x(0) e^{ \left( \mu - \frac{1}{2}\sigma^2 \right)t+\sigma W_t}\]
from which we might find the probability that $x(t)$ is less than some specified value. We can use It\={o} calculus to e.g. construct a ``riskless portfolio" and many other lucrative-sounding things. Of course, analytical solutions to stohastic differential equations are useful in biology as well.\\

On the other hand, much can be learned about the behavior of a stochastic differential equation without having to study stochastic calculus, and this will be our emphasis at the beginning of the next lecture. You have seen, when we studied the discrete case, that the chemical master equation allows us to predict the rate of change in the probability distribution of states: we will present the Fokker-Planck equation, which does the same for SDEs. We will also introduce Wright's formula for calculating stationary solutions to the Fokker-Planck equation. Both methods can be wielded using ordinary calculus.
\end{document}

max_stars_repo_path: lectures/Lecture 23 - Diffusion and Stochastic Differential Equations/lecture 23 notes.tex

max_stars_repo_name: mewahl/intro-systems-biology

max_issues_repo_name: mewahl/intro-systems-biology

max_forks_repo_name: mewahl/intro-systems-biology