8

For a class in derivatives pricing I would like to find a way to quickly and efficiently draw recombining binomial trees. The class involved quite a few of those trees and it would be immensely helpful to come up with a way that would allow me to semi-automate the process.

Here's an example (excuse the low resolution; it's the best I've been able to find): enter image description here

I want to achieve this look by specifying only the number of periods (i.e. horizontal levels); the probability p of going upwards from any node; and the possible values for all nodes. The probabilities p and 1-p should then automatically be displayed above the connecting lines upwards and downwards respectively (as shown in the example). All values for the nodes themselves should be entered manually and their number of course depends on the number of levels.

I am of aware of the possibility of specifying node locations manually in order to achieve the recombining tree but my experience does not suffice to build something to automate this. My question is not about drawing recombining trees in general; it is about finding a way to do it very quickly, as I use LaTeX for my lecture notes.

  • 1
    The picture presented at wiki looks more accurate in presenting node labels. There is another more readable picture, similar to the OP's request. – Malipivo Apr 8 '15 at 14:02
  • 1
    So what you really need is a way to input the names in a way that makes sense to you and can be scanned by LaTeX. The tabular & and \\ nomenclature comes to mind, perhaps with the parent in the first row, first generation children in the second, etc. – John Kormylo Apr 8 '15 at 14:23
  • @Malipivo, I posted this tree because it includes the p and 1-p labels. I didn't use the one from wiki to make it clear that I don't necessarily need that specific look. Very simple text nodes connected by very simple lines are sufficient. – Constantin Apr 8 '15 at 14:33
  • @JohnKormylo, yes! Something like this. Unfortunately I am not experienced enough to write anything like this myself. – Constantin Apr 8 '15 at 14:33
  • 1
    @Constantin This is an interesting question. Well, could you please tell/show us more about data you wish to enter manually? Is it probability p, horizontal level, that's clear, and S0 next to it? According to notation, after we enter S0 all cells/nodes should be known in value. Or are you really entering different S value per cell (it is known from game theory field)? – Malipivo Apr 9 '15 at 5:42
5

This calculates the probabilities for a given value of p. You just need to put my binomial=<value> at the start of the tree to select the appropriate style with the appropriate value of p. I've used 0.25 as an example. You also specify the content of the nodes manually, as you requested.

\documentclass[tikz,border=10pt]{standalone}
\usepackage{forest}
\tikzset{
  my label/.style={font=\small},
  my edge label/.style={font=\scriptsize, midway, sloped},
}
\forestset{
  my binomial/.style={
    TeX={\def\p{#1}},
    for tree={
      grow'=0,
      parent anchor=east,
      child anchor=west,
      circle,
      fill,
      text width=2.5pt,
      inner sep=0pt,
      outer sep=0pt,
      edge={->},
      s sep+=5pt,
      l sep+=25pt,
      before typesetting nodes={
        if level=0{
          label/.wrap pgfmath arg={[my label]left:##1}{content()},
          content={1},
        }{
          if n children=0{
            label/.wrap pgfmath arg={[my label]right:##1}{content()},
          }{
            if n=1{
              label/.wrap pgfmath arg={[my label]above:##1}{content()},
            }{
              label/.wrap pgfmath arg={[my label]below:##1}{content()},
            },
          },
          if n=1{
            content/.wrap pgfmath arg={##1}{content("!u")*\p},
            edge label/.wrap pgfmath arg={{node [my edge label, above] {##1}}}{content("!u")*\p}
          }{
            content/.wrap pgfmath arg={##1}{content("!u")*(1-\p)},
            edge label/.wrap pgfmath arg={{node [my edge label, below] {##1}}}{content("!u")*(1-\p)}
          },
        },
        delay={
          content={},
        },
      },
    }
  }
}
\begin{document}
  \begin{forest}
    my binomial=.25
    [A
      [B
        [D
          [H]
          [I]
        ]
        [E
          [J]
          [K]
        ]
      ]
      [C
        [F
          [L]
          [M]
        ]
        [G
          [N]
          [O]
        ]
      ]
    ]
  \end{forest}
\end{document}

binomial tree

EDIT

Figured out how to turn this into a proper style thanks to Sašo Živanović.

5

An attempt at this problem with MetaPost. It defines a macro binomial_tree(expr N, p)(text thelabels) where N is the number of periods (horizontal/vertical levels), p is the probability value and (since the OP required manual labelling) thelabels is a list containing all the labels in the right order, the nodes being numbered from left to right and from top to bottom.

Edit I have slightly changed the previous example and introduced a second.

\documentclass[border=2mm, multi=mplibcode]{standalone}
\usepackage{luatex85,luamplib}
  \mplibsetformat{metafun}
  \mplibtextextlabel{enable}
  \everymplib{
    % Horizontal and vertical distance
    % between consecutive nodes
    h := 3.25cm; v := 2.75cm;
    % Arrows a bit thinner and longer
    ahlength := 6bp; ahangle := 30; 

    % The main macro 
    def binomial_tree(expr N, p)(text thelabels) =
      pair pos[]; pos0 = pos1 = origin;
      value1 := 1; pen pendot; pendot = pencircle scaled 5; 
      string name[]; 
      k:= 0; for t = thelabels: k := k+1; name[k] = t; endfor
      k := 1; draw pos1 withpen pendot; label.lft(name1, pos0);

      for i = 2 upto N:
        labeloffset := 5bp;
        K := k-(i-2);
        pos0 := pos0 + (h, .5v);
        for j = 1 upto i:
          k := k+1;
          pos[k] := pos0 + (0, -(j-1)*v);
          value[k] := if j = 1: value[k-i+1]*p else: value[k-i]*(1-p) fi;
          draw pos[k] withpen pendot;
          label.if i=N: rt elseif j<>i:top else: bot fi(name[k], pos[k]);
        endfor

        labeloffset := 3bp;
        for j = 0 upto i-2:
          pair A, B, C; A = pos[K+j]; B = pos[K+j+i-1]; C = pos[K+j+i];
          drawarrow A -- B cutends 2.5bp; 
          label.top(decimal value[K+j+i-1], .5[A,B]) 
            rotatedaround(.5[A,B], angle(B-A));
          drawarrow A -- C cutends 2.5bp;
          label.bot(decimal value[K+j+i], .5[A,C]) 
            rotatedaround(.5[A,C], angle(C-A));
        endfor
      endfor
    enddef;
    beginfig(1);}

  \everyendmplib{endfig;}

\begin{document}
   \begin{mplibcode}
     binomial_tree(4, .65)("O", "I", "II", "$A$", "$B$", "$C$", 
       "$\alpha$", "$\beta$", "$\gamma$", "$\delta$");
   \end{mplibcode}
   \begin{mplibcode}
     binomial_tree(6, .25)("$A$" for i=1 upto 20:, "$" & char(65+i) & "$" endfor); 
   \end{mplibcode}
\end{document}

To be processed with LuaLaTeX. Here is the first example, with p = .65, N = 4, and a not-too-serious labelling :

binomial_tree(4, .65)("O", "I", "II", "$A$", "$B$", "$C$", 
  "$\alpha$", "$\beta$", "$\gamma$", "$\delta$");    

enter image description here

And here is the second example, with N=6, p=0.25 and alphabetical labelling. I have cheated for this one by using a loop, to spare me the pain of entering 20 letters manually. :-)

binomial_tree(6, .25)("$A$" for i=1 upto 20:, "$" & char(65+i) & "$" endfor);

enter image description here

  • I am trying to use your code, but encountered the following error message. Could you please take a look to see what it means and how to fix it? Thank you. /usr/share/texlive/texmf-dist/tex/latex/base/ltluatex.tex:55: Undefined control sequence. l.55 \ifnum\luatexversion <60 % – Hans May 18 '17 at 3:25
  • 1
    Since a recent update of LuaTeX, luamplib works only if the luatex85 package is loaded. Hence insert \usepackage{luatex85} in the preamble. – Franck Pastor May 18 '17 at 7:41
  • I inserted \usepackage{luatex85} on the second line. But I still encounter the same error message. Could you please edit your answer with the correction so I can see if I have done the right thing? Thank you. – Hans May 18 '17 at 23:30
  • It works fine here once luatex85 is loaded (I've edited my program). Maybe you are using PDFLaTeX ? You must use LuaLaTeX to typeset this program. – Franck Pastor May 19 '17 at 4:32
4

This solution uses matrix and is not so automatic as Malipivo's solution. All links could be drawn within some \foreach loop, but I was not enough inspired now.

\documentclass[tikz,border=2mm]{standalone}
\usetikzlibrary{matrix,shapes}

\begin{document}
\begin{tikzpicture}[mynode/.style={draw,ellipse, minimum width=1.5cm, minimum height=.8mm}]
\matrix (A) [matrix of math nodes, nodes={mynode}, column sep=3mm, row sep=1mm]
{
&&&&S_0u\\
&&&S_0u&\\
&&S_0u&&S_0u&\\
&S_0u&&S_0u&\\
S_0&&S_0&&S_0\\
&S_0d&&S_0d&\\
&&S_0d^2&&S_0d^2\\
&&&S_0d^3&\\
&&&&S_0d^4\\
};
\draw[->] (A-5-1)--(A-4-2);
\draw[->] (A-5-1)--(A-6-2);

\draw[->] (A-4-2)--(A-3-3);
\draw[->] (A-4-2)--(A-5-3);

\draw[->] (A-3-3)--(A-2-4);
\draw[->] (A-3-3)--(A-4-4);

\draw[->] (A-2-4)--(A-1-5);
\draw[->] (A-2-4)--(A-3-5);

\draw[->] (A-6-2)--(A-5-3);
\draw[->] (A-6-2)--(A-7-3);

\draw[->] (A-5-3)--(A-4-4);
\draw[->] (A-5-3)--(A-6-4);

\draw[->] (A-4-4)--(A-3-5);
\draw[->] (A-4-4)--(A-5-5);

\draw[->] (A-7-3)--(A-6-4);
\draw[->] (A-7-3)--(A-8-4);

\draw[->] (A-6-4)--(A-5-5);
\draw[->] (A-6-4)--(A-7-5);

\draw[->] (A-8-4)--(A-7-5);
\draw[->] (A-8-4)--(A-9-5);
\end{tikzpicture}
\end{document}

enter image description here

  • I'm sorry I misread the question. It focuses more on entering p probability and node values manually (which are likely multiplied by probability). – Malipivo Apr 8 '15 at 17:52
4

Version 2 (strategy of overwriting the node labels)

I've added probabilities above/below the arrows; p0 can be changed via the \malp command. Next to it, I've written horizontal level plus number of ds (vertical level) information into the nodes. We can turn it off via the \nodeformat command. If we want to add our own node text, it's located in the last block of code and we overwrite the present node labels, e.g.

3/2/G/yellow
  • 3 - is the third horizontal level,
  • 2 - is the number of ds (vertical level, starting from 0),
  • G - is the text we wish to have there,
  • yellow - is the fill color of that particular node.

I'm adding a new version of the source code and a preview of a simple example. Let me hope this will help a bit, because it wasn't easy to understand the requested format of a graph.

% *latex mal-tree.tex
\documentclass[a4paper]{article}
\pagestyle{empty} % no page numbers, please
\usepackage{tikz} % graphics engine
\usetikzlibrary{arrows.meta} % 

\begin{document}
\def\mallevel{5} % a number of levels we wish to get
\def\malp{0.25} % probability p
\def\nodeformat{\x-\numberofd} % text written in the node, {} or {\numberofs-\numberofd}

\def\ratiox{2.5} % longer arrows (horizontal direction)
\def\ratioy{1.5} % longer arrows (vertical direction)

% Defining styles...
\tikzset{
   inner sep=0pt, outer sep=2pt, % some node reserve
   malarrow/.style={->, shorten >=0pt, shorten <=-2pt, -{Stealth[length=5pt, width=3pt, inset=1pt]},
   }, % a style for arrows, -2 is a shift back (an experiment)
   malnode/.style={draw=black, fill=none, minimum width=5mm, circle, inner sep=1pt}, % a style for nodes
   prob/.style={pos=0.3, sloped, font=\footnotesize},
   }

% the picture itself
\begin{tikzpicture}
\foreach \x in {0,...,\mallevel} { % horizontal direction of a tree
\foreach \y in {0,...,\x} { % vertical direction of a tree
\pgfmathparse{-\x/2+\y} % move up by a half of a tree (vertical direction)
\let\movey=\pgfmathresult % save the result
% position of nodes
%\ifnum\y=0 \def\whereto{below} \else \def\whereto{above} \fi
%\ifnum\x=0 \ifnum\y=0 \def\whereto{left} \fi \fi
   % d, number of ds and its output format
   \pgfmathparse{int(\x-\y)} 
   \let\numberofd=\pgfmathresult
   %\ifnum\numberofd=0 \def\mald{} \fi % print nothing if there is no d
   %\ifnum\numberofd=1 \def\mald{d} \fi % print d without superscript
   %\ifnum\numberofd>1 \def\mald{d^{\numberofd}} \fi % regular d with superscript
   % u, number of us and its output format
   \pgfmathparse{int(\y)}
   \let\numberofs=\pgfmathresult
   %\ifnum\y=0 \def\malu{} \fi % print nothing if there is no u
   %\ifnum\y=1 \def\malu{u} \fi % print u without superscript
   %\ifnum\y>1 \def\malu{u^{\y}} \fi % regular u with superscript
\node[malnode, font=\tiny] %label=\whereto:$S_0\mald\malu$
   (\x-\y) at (\ratiox*\x, \ratioy*\movey) {\nodeformat}; % draw a node + its label
   \ifnum\x>0 % draw the arrows
      \pgfmathparse{int(\x-1)}
      \let\previousx=\pgfmathresult % previous level (horizontal direction)
      \pgfmathparse{int(\y-1)}
      \let\previousy=\pgfmathresult % previous level (vertical direction)
            \pgfmathparse{\malp^\y * (1-\malp)^\numberofd}
            \let\maltype=\pgfmathresult      
         \ifnum\y<\x 
            \draw[malarrow] (\previousx-\y)--(\x-\y) node [prob, below] {\maltype}; \fi % arrows from the left top node to the right bottom node, if previous node is defined
         \ifnum\y>0 
            \draw[malarrow] (\previousx-\previousy)--(\x-\y) node [prob, above] {\maltype}; \fi % arrows from the left bottom node to the right top node, if the previous node is defined
    \fi % end of \ifnum\x>0, otherwise we cannot draw an arrow
   } % \y, vertical direction upto \x level
} % \x, horizontal direction upto \mallevel.

% Overwriting mode...
\foreach \bonusx/\bonusy/\maltext/\malcolor in {1/0/A/yellow, 3/2/G/yellow, 4/2/T/yellow, 5/2/E/orange, 5/3/F/orange} {
   \pgfmathparse{-\bonusx/2+(\bonusx-\bonusy)} % move up by a half of a tree (vertical direction)
   \let\movey=\pgfmathresult % save the result
\node[malnode, font=\footnotesize, fill=\malcolor]
   (\bonusx-\bonusy) at (\ratiox*\bonusx, \ratioy*\movey) {\maltext};
   }   
\end{tikzpicture}
\end{document}

Example 2: overwriting node labels strategy


Version 1 (old version)

This might be a starting point for you done in TikZ. I used notation from this question. I've added some comments to the source code. We can run any LaTeX engine.

% *latex mal-a-tree.tex
\documentclass[a4paper]{article}
\pagestyle{empty} % no page numbers, please
\usepackage{tikz} % graphics engine
\usetikzlibrary{arrows.meta} % 

\begin{document}
\def\mallevel{7} % a number of levels we wish to get
\def\ratiox{1.7} % longer arrows (horizontal direction)
\def\ratioy{0.9} % longer arrows (vertical direction)

% Defining styles...
\tikzset{
   inner sep=0pt, outer sep=2pt, % some node reserve
   malarrow/.style={->, shorten >=0pt, shorten <=-2pt, -{Stealth[length=5pt, width=3pt, inset=1pt]}}, % a style for arrows, -2 is a shift back (an experiment)
   malnode/.style={draw=none, fill=black, minimum width=5pt, circle}, % a style for nodes
   }

% the picture itself
\begin{tikzpicture}
\foreach \x in {0,...,\mallevel} { % horizontal direction of a tree
\foreach \y in {0,...,\x} { % vertical direction of a tree
\pgfmathparse{-\x/2+\y} % move up by a half of a tree (vertical direction)
\let\movey=\pgfmathresult % save the result
% position of nodes
\ifnum\y=0 \def\whereto{below} \else \def\whereto{above} \fi
\ifnum\x=0 \ifnum\y=0 \def\whereto{left} \fi \fi
   % d, number of ds and its output format
   \pgfmathparse{int(\x-\y)} 
   \let\numberofd=\pgfmathresult
   \ifnum\numberofd=0 \def\mald{} \fi % print nothing if there is no d
   \ifnum\numberofd=1 \def\mald{d} \fi % print d without superscript
   \ifnum\numberofd>1 \def\mald{d^{\numberofd}} \fi % regular d with superscript
   % u, number of us and its output format
   \ifnum\y=0 \def\malu{} \fi % print nothing if there is no u
   \ifnum\y=1 \def\malu{u} \fi % print u without superscript
   \ifnum\y>1 \def\malu{u^{\y}} \fi % regular u with superscript
\node[malnode, label=\whereto:$S_0\mald\malu$] (\x-\y) at (\ratiox*\x, \ratioy*\movey) {}; % draw a node + its label
   \ifnum\x>0 % draw the arrows
      \pgfmathparse{int(\x-1)}
      \let\previousx=\pgfmathresult % previous level (horizontal direction)
      \pgfmathparse{int(\y-1)}
      \let\previousy=\pgfmathresult % previous level (vertical direction)
         \ifnum\y<\x \draw[malarrow] (\previousx-\y)--(\x-\y); \fi % arrows from the left top node to the right bottom node, if previous node is defined
         \ifnum\y>0 \draw[malarrow] (\previousx-\previousy)--(\x-\y); \fi % arrows from the left bottom node to the right top node, if the previous node is defined
      \fi % end of \ifnum\x>0, otherwise we cannot draw an arrow
   } % \y, vertical direction upto \x level
} % \x, horizontal direction upto \mallevel.
\end{tikzpicture}
\end{document}

An example with 7 levels

  • Is there a way to stack symbols in the nodes, one atop the other? I tried, for example, \def\nodeformat{{\x-\numberofd}\atop{a}}. It did not work. – Hans May 19 '17 at 3:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.