$2$種類の文字「$\mathrm{A}$」，「$\mathrm{B}$」を$1$つずつ左から右に書いていく．書かれる文字が$\mathrm{A}$か$\mathrm{B}$かは確率$\displaystyle \frac{1}{2}$で決まるものとする．しかし，次の$2$つのルールにより文字が消去されることがある：
[$1.$] 右端の$\mathrm{A}$の右隣に$\mathrm{B}$が書かれる場合，その$\mathrm{B}$は確率$\displaystyle \frac{2}{3}$で消去される [$2.$] 右端の$\mathrm{B}$の左側に$\mathrm{A}$が$1$つ以上存在する場合，それらのうちでもっとも右にある$\mathrm{A}$を$\maruA$と呼ぶ．この状況で，右端の$\mathrm{B}$の右隣に$\mathrm{A}$が書かれる場合，確率$\displaystyle \frac{2}{3}$でその$\mathrm{A}$と$\maruA$より右側のすべての文字が消去される（ただし$\maruA$は消去されない）．
上記$2$つのルールにあてはまらない場合は，消去される文字はないものとする．$n$文字を書いたときに，実際に残っている文字数を$a_n$とする．例えば，$3$文字を$\mathrm{A}$，$\mathrm{B}$，$\mathrm{A}$の順に書いた場合の結果は「$\mathrm{ABA}$」，「$\mathrm{AA}$」，「$\mathrm{A}$」のいずれかとなる．
(1) $a_3=2$となる確率を求めよ．
(2) $a_4=1$となる確率を求めよ．
(3) $a_n=n$となる確率を$n$を用いて表せ．