How can I get a matrix with row and column labels that can also be aligned with a title?

Question

I'm seeking to replicate this image:

Is there a way to get this without using any external packages other than tikz (ideally just some combination of \array and tabular) or wild redefinitions? I prefer not using blkarray because it does bad things when attempting to make it spit out a bracket matrix.

So far I can do

\documentclass[11pt]{amsart}
\begin{document}
\begin{tabular}{c @{\hspace{2\tabcolsep}} *{4}{c}}

&
0 &
1 &
2 &
3
\\[1ex]
0 & 0 & 1/3 & 1/3 & 1/3  \\
1 & 0 & 1/3 & 1/3 & 1/3  \\
2 & 1/3 & 1/3 & 1/3 & 0  \\
3 & 0 & 1/3 & 1/3 & 1/3  \\ 

\end{tabular}
\end{document}

Edit: I like the answer initially given by @Werner, but it seems hard to modify for, say, my use case. Here's what I tried, which fails to align the brackets correctly:

\[
  P =
  \begin{array}{ *{5}{c} }
      \\[3\normalbaselineskip]
      & \multicolumn{4}{c}{\rowind{State}} \\
      & \colind{\$0} & \colind{\$1} & \colind{\$2} & \colind{\$3}  \\
    \rowind{0} &   0 & 1/3 & 1/3 & 1/3 \\
    \rowind{1} & 0 & 1/3 & 1/3 & 1/3 \\
    \rowind{2} \smash{\makebox[0pt][l]{$%
      \hspace{.5\tabcolsep}\left[\begin{array}{@{}c@{}}
        \mathstrut \\ \mathstrut \\ \mathstrut \\ \mathstrut 
      \end{array}\right.
    $}} & 1/3 & 1/3 & 1/3 & 0 \smash{\makebox[0pt][l]{$%
      \hspace{.5\tabcolsep}\left.\begin{array}{@{}c@{}}
        \mathstrut \\ \mathstrut \\ \mathstrut \\ \mathstrut 
      \end{array}\right]
    $}} \\
    \rowind{3} &  0 & 1/3 & 1/3 & 1/3  \\
  \end{array}
\]

Answer 1

Of course! I've made some definitions to avoid repetition of content which also allows for tweaking it if you want:

\documentclass{article}

\newcommand{\indsize}{\scriptsize}
\newcommand{\colind}[2]{\displaystyle\smash{\mathop{#1}^{\raisebox{.5\normalbaselineskip}{\indsize #2}}}}
\newcommand{\rowind}[1]{\mbox{\indsize #1}}

\begin{document}

\[
  P =
  \begin{array}{@{}c@{}}
    \rowind{0} \\ \rowind{1} \\ \rowind{2} \\ \rowind{3} \\ \rowind{4}
  \end{array}
  \mathop{\left[
  \begin{array}{ *{5}{c} }
     \colind{1}{\$0}  &  \colind{0}{\$1}  &  \colind{0}{\$2}  & \colind{0}{\$3} & \colind{0}{\$4} \\
    1-p &  0  &  p  & 0 & 0 \\
     0  & 1-p &  0  & p & 0 \\
     0  &  0  & 1-p & 0 & p \\
     0  &  0  &  0  & 0 & 1
  \end{array}
  \right]}^{
  \begin{array}{@{}c@{}}
    \rowind{State} \\ \mathstrut
  \end{array}
  }
\]

\end{document}