\documentclass{standalone}

\usepackage[T1]{fontenc}

\usepackage{amsmath}

\usepackage{amsfonts}

\usepackage{parskip}

\usepackage{marvosym} %Lightning symbol

\usepackage[usenames,dvipsnames]{color}

\usepackage[hidelinks]{hyperref}

\renewcommand*{\familydefault}{\sfdefault}

\usepackage{bbm} %For \mathbbm{1}

%\usepackage{bbold}

\usepackage{tikz}

\begin{document}

\begin{tikzpicture}

    \def\height{4};

    \draw[step=1cm,gray,dotted] (-0.9,-0.9) grid (8.9,\height+0.9);

    %

    % Red line through grid

    %

    \draw [line width=3.0,red] (0,0) -- (0,1) -- (1,1) -- (2,1) -- (2,2);

    %

    % Arrows of the grid

    %

    \foreach \x in {0,...,7} {

        \foreach \y in {1,...,\height} {

            \draw[->] (\x,\y-1) -- (\x+0.9,\y-1);

            \draw[->] (\x,\y-1) -- (\x,\y-1+0.9);

        }

        \draw [->] (\x,\height) -- (\x+0.9,\height);

    }

    \foreach \y in {1,...,\height} %somehow the loop cant go to '\height-1'

        \draw [->] (8,\y-1) -- (8,\y-1+0.9); % so we fix it like this with '\y-1'

    %

    % Move labels

    %

    \foreach \y in {1,...,\height} {

        \draw (-1.2, \y - 0.5) node {$(z^Y_\y,v^Y_\y,r^Y_\y)$};

    }

    \foreach \x in {1,...,8} {

        \draw (\x-0.6, -1.7) node[rotate=70] {$(z^X_\x,v^X_\x,r^X_\x)$};

    }

    %

    % bitstring labels

    %

    \draw(-0.1,-0.4) node {$b^X\;1^S\;b^Y$};

    \draw(8.2,-0.4) node {$1^X\;1^S\;b^Y$};

    \draw (-0.2,\height+0.3) node {$b^X\;1^S\;1^Y$};

    \draw (8.2,\height+0.3) node {$\mathbf{1}$};

    %

    % -> steps of xi

    %

    \draw (4,-3.0) node {$\to$ steps of $\xi^{G\setminus Y}$};

    \node[rotate=90,anchor=south,xshift=2.0cm,yshift=2.3cm] {$\to$ steps of $\xi^{G\setminus X}$};

    %

    % (Red) circles

    %

    \draw[fill,red] (0,0) circle (0.08);

    \draw[fill    ] (8,0) circle (0.05);

    \draw[fill    ] (0,\height) circle (0.05);

    \draw[fill,red] (8,\height) circle (0.08);

    %

    % Probability labels

    %

    \def\x{6};

    \def\y{3};

    \draw[fill,black] (\x,\y) circle (0.07);

    \draw[fill=white,draw=black] (\x+0.23,\y-0.26) rectangle +(0.5,0.5);

    \draw[fill=white,draw=black] (\x-0.55,\y+0.26) rectangle +(1.1,0.5);

    \draw (\x+0.5,\y) node {$p_{ij}$};

    \draw (\x,\y+0.5) node {$1-p_{ij}$};

    \def\x{2};

    \def\y{1};

    \draw[fill,black] (\x,\y) circle (0.07);

    \draw[fill=white,draw=black] (\x+0.12,\y-0.26) rectangle +(0.7,0.5);

    \draw[fill=white,draw=black] (\x-0.75,\y+0.26) rectangle +(1.5,0.5);

    \draw (\x+0.5,\y) node {$p_{3,2}$};

    \draw (\x,\y+0.5) node {$1-p_{3,2}$};

    \def\x{8};

    \def\y{1};

    \draw[fill,black] (\x,\y) circle (0.07);

    \draw[fill=white,draw=black] (\x-0.25,\y+0.26) rectangle +(0.5,0.5);

    \draw (\x,\y+0.5) node {$1$};

    \def\x{3};

    \def\y{\height};

    \draw[fill,black] (\x,\y) circle (0.07);

    \draw[fill=white,draw=black] (\x+0.25,\y-0.25) rectangle +(0.5,0.5);

    \draw (\x+0.5,\y) node {$1$};

    %

    % Probability definition

    %

    \draw (10,2)+(-1,-0.5) rectangle +(1,0.5);

    \draw (10,2) node {$p_{ij} \equiv \frac{z^X_i}{z^X_i + z^Y_j}$};

\end{tikzpicture}

\end{document}

        \includegraphics{diagram_paths3.pdf}