Adjusting the space between the caption below a figure

If I've well understood what you want, this is easy with the \ffigbox command from floatrow, which gives full control on the caption width:

\documentclass[11pt, a4paper]{report}
\usepackage{bm}
\usepackage{graphicx, verbatim, amsmath,amssymb, amsthm}
\usepackage{color}
\usepackage{array}
\usepackage{setspace}% if you must (for double spacing thesis)
\usepackage{fancyhdr}
\usepackage{enumitem}
\usepackage{tikz}
\usepackage{parskip}
\usepackage{lipsum}
    \newtheorem{theorem}{Theorem}[section]
\newtheorem{example}[theorem]{Example}
\usepackage{floatrow}

 \begin{document}

    \begin{example}
    Consider a random walk on the $n$-cycle. Let $\Omega = \mathbb{Z}_n = \lbrace 0, 1, 2, \cdots, n-1 \rbrace$ be the set of remainders modulo $n$. Also consider the transition matrix:
    \[
    P(x,y) =
    \begin{cases}
    \frac{1}{2} & \text{if } y=x+1 \pmod n\\
    \frac{1}{2} & \text{if } y=x-1\pmod n\\
    0 & \text{otherwise}
    \end{cases}
    \]

    The associated Markov chain $X_t$ is called a random walk on the $n$-cycle. The states can be visualised as equally spaced nodes arranged in a circle(see figure 1.1)
    \end{example}

 \begin{figure}[htbp]
 \centering
 \ffigbox[1.1\FBwidth]{%
 \caption{Random walk on $\mathbb{Z}_10$ is periodic, since every step
 goes from an even state to an odd state, or vice-versa. Random
 walk on $\mathbb{Z}_9$ is aperiodic.}
 \label{my:figure}}%
 {\begin{tikzpicture}
 \foreach \i in {90,54,...,-234} {
 \draw[ultra thick] (\i:2)--({\i-36}:2);
 }
 \foreach \i in {90,18,...,-198} {
 \draw[fill=black] (\i:2) circle (1.25mm);
 }
 \foreach \i in {54,-18,...,-234} {
 \draw[fill=white] (\i:2) circle (1.25mm);
 }
 \begin{scope}[xshift=5cm]
 \foreach \i in {90,50,...,-230} {
 \draw[ultra thick] (\i:2)--({\i-40}:2);
 \draw[fill=black] (\i:2) circle (1.25mm);
 }
 \end{scope}
 \end{tikzpicture}}%
 \end{figure}

\end{document} 

If I understand you right, you can use the following two lines in your preamble

\usepackage{caption} % <================================================
\captionsetup{width=0.8\textwidth} % <==================================

to let the caption use only 80% of textwidth. See the documentation of package caption for more possibilitys to manipulate the layout of captions with typing texdoc caption on ypur console/terminal.

The complete code

\documentclass[11pt, a4paper]{report}
\usepackage{bm}
\usepackage{amsfonts, graphicx, verbatim, amsmath,amssymb, amsthm}
\usepackage{color}
\usepackage{array}
\usepackage{setspace}% if you must (for double spacing thesis)
\usepackage{fancyhdr}
\usepackage{enumitem}
\usepackage{tikz}
\usepackage{parskip}
\usepackage{lipsum}

\usepackage{caption} % <================================================
\captionsetup{width=0.8\textwidth} % <==================================

\newtheorem{theorem}{Theorem}[section]
\newtheorem{example}[theorem]{Example}   


\begin{document}

\begin{example} 
Consider a random walk on the $n$-cycle. 
Let $\Omega = \mathbb{Z}_n = \lbrace 0, 1, 2, \cdots, n-1 \rbrace$ be 
the set of remainders modulo $n$. Also consider the transition matrix:
\[
  P(x,y) = 
  \begin{cases} 
    \frac{1}{2} & \text{if } y=x+1\;\; (mod\;n)\\
    \frac{1}{2} & \text{if } y=x-1\;\; (mod\;n)\\
    0           & \text{otherwise}
  \end{cases}
\]

The associated Markov chain $X_t$ is called a random walk on the 
$n$-cycle. The sates can be visualised as equally spaced nodes arranged 
in a circle (see figure~\ref{my:figure}). % <==========================
\end{example}

\begin{figure}[htbp]
  \centering
  \begin{tikzpicture}
        \foreach \i in {90,54,...,-234} {
            \draw[ultra thick] (\i:2)--({\i-36}:2);
        }
        \foreach \i in {90,18,...,-198} {
            \draw[fill=black] (\i:2) circle (1.25mm);
        }
        \foreach \i in {54,-18,...,-234} {
            \draw[fill=white] (\i:2) circle (1.25mm);
        }
        \begin{scope}[xshift=5cm]
        \foreach \i in {90,50,...,-230} {
            \draw[ultra thick] (\i:2)--({\i-40}:2);
            \draw[fill=black] (\i:2) circle (1.25mm);
        }
        \end{scope}
  \end{tikzpicture}
  \caption{Random walk on $\mathbb{Z}_10$ is periodic, since every step
    goes from an even state to an odd state, or vice-versa. Random
    walk on $\mathbb{Z}_9$ is aperiodic.}
  \label{my:figure}
\end{figure}
Text after the figure.
\end{document}

gives you the result:

EDIT:

With your second example (after commenting \ffigbox, see markings <====== in code)

\documentclass[11pt, a4paper]{report}
\usepackage{bm}
\usepackage{amsfonts, graphicx, verbatim, amsmath,amssymb, amsthm}
\usepackage{color}
\usepackage{array}
\usepackage{setspace}% if you must (for double spacing thesis)
\usepackage{fancyhdr}
\usepackage{enumitem}
\usepackage{tikz}
\usepackage{parskip}
\usepackage{lipsum}

\usepackage{floatrow}

\usepackage{caption} % <================================================
\captionsetup{width=0.8\textwidth} % <==================================

\newtheorem{theorem}{Theorem}[section]
\newtheorem{example}[theorem]{Example}   


\begin{document}

\begin{example} 
Consider a random walk on the $n$-cycle. 
Let $\Omega = \mathbb{Z}_n = \lbrace 0, 1, 2, \cdots, n-1 \rbrace$ be 
the set of remainders modulo $n$. Also consider the transition matrix:
\[
  P(x,y) = 
  \begin{cases} 
    \frac{1}{2} & \text{if } y=x+1\;\; (mod\;n)\\
    \frac{1}{2} & \text{if } y=x-1\;\; (mod\;n)\\
    0           & \text{otherwise}
  \end{cases}
\]

The associated Markov chain $X_t$ is called a random walk on the 
$n$-cycle. The sates can be visualised as equally spaced nodes arranged 
in a circle (see figure~\ref{my:figure}).
\end{example}

\begin{figure}[htbp]
  \centering
  \begin{tikzpicture}
        \foreach \i in {90,54,...,-234} {
            \draw[ultra thick] (\i:2)--({\i-36}:2);
        }
        \foreach \i in {90,18,...,-198} {
            \draw[fill=black] (\i:2) circle (1.25mm);
        }
        \foreach \i in {54,-18,...,-234} {
            \draw[fill=white] (\i:2) circle (1.25mm);
        }
        \begin{scope}[xshift=5cm]
        \foreach \i in {90,50,...,-230} {
            \draw[ultra thick] (\i:2)--({\i-40}:2);
            \draw[fill=black] (\i:2) circle (1.25mm);
        }
        \end{scope}
  \end{tikzpicture}
  \caption{Random walk on $\mathbb{Z}_10$ is periodic, since every step
    goes from an even state to an odd state, or vice-versa. Random
    walk on $\mathbb{Z}_9$ is aperiodic.}
  \label{my:figure}
\end{figure}
Text after the figure.

\clearpage
\begin{example} Consider the graph $G$ following shown in figure 1.2. The transition matrix of a simple random walk $G$ is 

\begin{equation*}
P =
\begin{bmatrix}[1.25]
    0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 & 0 \\
    \frac{1}{4} & 0 & \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{4} \\
    \frac{1}{4} & \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{4} & 0 \\
    \frac{1}{3} & 0 & \frac{1}{3} & 0 & \frac{1}{3} & 0 \\
    0 & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & 0 & \frac{1}{4} \\
    0 & \frac{1}{2} & 0 & 0 & \frac{1}{2} & 0 \\
\end{bmatrix}
\end{equation*}

\begin{figure}[htbp]
 \centering
%\ffigbox[1.1\FBwidth]{% <==============================================
 \caption{An example of a vertex set $V = \lbrace 1, 2, 3, 4, 5, 6\rbrace$ with $10$ edges.}
 \label{my:figure}%
%}% <===================================================================
 {\begin{tikzpicture}[bn/.style={circle,fill,draw,text=white,font=\sffamily,minimum
size=1mm},every node/.append style={bn}]
 \path node (1) {1} -- ++ (50:2.5) node (2) {2} -- ++(-95:1.75) node (3) {3}
 -- ++(-85:1.75) node (4) {4} -- ++(40:2.75) node (5) {5}
 -- ++ (0,1.75) node (6) {6} ;
 \draw[thick] (1)--(2)--(6)--(5)--(4)--(1)--(3)--(5)--(2)--(3)--(4);
\end{tikzpicture}}%
\end{figure}
\end{example}
\end{document}

you get the resulting second figure/page: