# Expected number of times to get arbitrary arrangement of coins

We consider tossing coins repeatedly. Using $+1$ to denote front and $-1$ back, given a positive interger $m$ and $\sigma=(\sigma_1,\dots,\sigma_m)$ where $\sigma_i\in\{1,-1\}$, we want to know the expected value of times until we get $m$ adjacent tosses represented by $\sigma$.

I have found an algorithm as follows:

We toss time by time. By law of total expectation, if we let $E_1$ be the desired expectation value, then $$E_1=\frac{1}{2}(E_2+1)+\frac{1}{2}(E_1+1),$$ where $E_2$ is defined as the expected times of tosses after we have already got the first toss as $\sigma_1$. Of course if the result of first toss is not $\sigma_1$ then we have another expected $E_1$ times, which is considered in the term $\frac{1}{2}(E_1+1)$.

By the same argument we have $$E_1=\frac{1}{2}(E_3+1)+\frac{1}{2}(E_{j_2}+1),\ \ \ \ j_2\in\{1,2\}$$ where $E_3$ is defined as the expected times of tosses after we have already got the first two tosses as $\sigma_1,\sigma_2$. What does $E_{j_2}$ mean? If the second toss is not $\sigma_2$, then we have come back to earlier cases, and $j_2$ is uniquely determined by the given $\sigma$.

We continue and get $m$ unknown numbers $E_1,\dots,E_m$, which satisfy $$E_k=\frac{1}{2}(E_{k+1}+1)+\frac{1}{2}(E_{j_k}+1),\ \ \ \ j_k\in\{1,\dots,k\}\hbox{ uniquely determined by \sigma}$$ for all $1\leq k\leq m$ (we set $E_{m+1}=0$ when $k=m$).

Thus we find $m$ linear equations which can be written as $A_m\vec{x}=(1,\dots,1)^T$, where $A_m=(a_{i,j})_{1\leq i,j\leq m}\in M_m(\mathbb{R})$ and $\vec{x}=(E_1,\dots,E_m)^T$. $a_{i,j}$ satisfies: \begin{eqnarray*} &&a_{i,i+1}=-\frac{1}{2}\ (1\leq i\leq m-1);\\ &&\hbox{$a_{i,i}=\frac{1}{2}$ if $j_i=i$, and $a_{i,i}=1$ if $j_i<i$ ($1\leq i\leq m$)};\\ &&a_{i,j_i}=-\frac{1}{2}\hbox{ if } j_i<i;\\ &&a_{i,j}=0\hbox{ in other cases.}\\ \end{eqnarray*}

I have computed several examples and I believe that $$\det A_m=\frac{1}{2^m},$$ so that $\vec{x}=A_m^{-1}\cdot(1,\dots,1)^T$ and we can solve out $E_1$. I believe this is a simple but somewhat powerful algorithm.

So my question comes to linear algebra:

$\textbf{Question}$:

how to show $\det A_m=\frac{1}{2^m}$, where $A_m$ is given as above (uniquely determined by the given $\sigma$)?

(Yeah, it seems rather trivial, but I have not found a proof yet $\dots$ Induction seems not to work since we might get submatrix not of the same form in the process. I believe the solution is not difficult, but I'm stuck now.)

$\textbf{Example}:$

$m=4,\ \sigma=(1,1,-1,1),\ (j_2,j_3,j_4)=(1,3,1),\ A=\begin{pmatrix} \frac{1}{2} & -\frac{1}{2} & 0 & 0 \\ -\frac{1}{2} & 1 & -\frac{1}{2} & 0 \\ 0 & 0 & \frac{1}{2} & -\frac{1}{2} \\ -\frac{1}{2} & 0 & 0 & 1 \end{pmatrix},\det A=\frac{1}{2^4}$.

$\det\begin{pmatrix} \frac{1}{2} & -\frac{1}{2} & 0 & 0 & 0 & 0 & 0 \\ 0 & \frac{1}{2} & -\frac{1}{2} & 0 & 0 & 0 & 0 \\ -\frac{1}{2} & 0 & 1 & -\frac{1}{2} & 0 & 0 & 0 \\ -\frac{1}{2} & 0 & 0 & 1 & -\frac{1}{2} & 0 & 0 \\ 0 & 0 & -\frac{1}{2} & 0 & 1 & -\frac{1}{2} & 0 \\ 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & -\frac{1}{2} \\ 0 & -\frac{1}{2} & 0 & 0 & 0 & 0 & 1 \end{pmatrix}$=$\frac{1}{2^7}$.

Fix $m$ and $\sigma$, and write $A$ for $A_m$. To solve your problem, it is not necessary to compute the determinant exactly; it is enough to show that $A$ is invertible, which can be done by showing that the only solution to $Ax=0$ is $x=0$. The equation $Ax=0$ gives $$x_k=\frac12x_{k+1}+\frac12x_{j_k}$$ for $k=1,\dots,m$, where for convenience we set $x_{m+1}=0$. Now a simple induction on $k$ shows that $x_k=x_1$ for all $k=1,\dots,m$, so $x$ must be a multiple of the vector $(1,1,\dots,1)^T$. However, the last equation gives $x_m=\frac12x_{j_m}$, which then implies $x=0$, as required.
EDIT: Your observation about the determinant is also correct. It can be proven by row-reducing the matrix $A$ in a certain way: namely, apply the usual row-reduction algorithm using only Type III operations (which preserve the determinant), but without pivoting on the first column, i.e., treat the first column as if it were the last column. This will result in the matrix $$\begin{pmatrix}\frac12 & -\frac12 & 0 & 0 & \dots & 0\\ \frac12 & 0 & -\frac12 & 0 & \dots & 0 \\ \frac12 & 0 & 0 & -\frac12 & \dots & 0 \\ & & \vdots & & \\ \frac12 & 0 & 0 & 0 & \dots & -\frac12 \\ \frac12 & 0 & 0 & 0 & \dots & 0\end{pmatrix}$$ which is easily seen to have determinant $\frac1{2^m}$.