\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, \y - 0.5) node {$(z_\y',s_\y',r_\y')$};
    }
    \foreach \x in {1,...,8} {
        \draw (\x-0.6, -1.4) node[rotate=70] {$(z_\x,s_\x,r_\x)$};
    }

    %
    % bitstring labels
    %

    \draw(-0.1,-0.4) node {$b_1\land b_2$};
    \draw(8.2,-0.4) node {$\mathbf{1} \land b_2$};
    \draw (-0.2,\height+0.3) node {$b_1\land\mathbf{1}$};
    \draw (8.2,\height+0.3) node {$\mathbf{1}$};


    %
    % -> steps of xi
    %

    \draw (4,-2.5) node {$\to$ steps of $\xi_1$};
    \node[rotate=90,anchor=south,xshift=2cm,yshift=1.9cm] {$\to$ steps of $\xi_2$};

    %
    % (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$};
\end{tikzpicture}
\end{document}