# Resilience Analysis for Double Spending via Sequential Decision Optimization
## 6 Attack Planning as an Optimal Stopping Problem
### Algorithmic Solution  
Before we present an algorithmic solution, let us show how to calculate the rewards (21). In order to determine the probability \(\mathbb{P}(S(t)|\,Z_{t}=x)\) in the expression (21), we use the time and space homogeneity of the transition kernel to obtain  
\[\mathbb{P}(S(t)|\,Z_{t}=x)=\mathbb{P}(\min_{i=t+1}^{T+1-t}Z_{i} \leq 0\,|\,Z_{0}=x)\] \[= \sum_{x^{\prime}=1}^{x+n+1}\mathbb{P}(\min_{i=t+1}^{T+1-t}Z_{i} \leq 0\,|\,Z_{n+1}=x^{\prime})\mathbb{P}(Z_{n+1}=x^{\prime}\,|\,Z_{0}=x)+ \mathbb{P}(Z_{n+1}\leq 0\,|\,Z_{0}=x)\] \[= \sum_{x^{\prime}=1}^{x+n+1}\mathbb{P}(\min_{i=0}^{T-t-n}Z_{i} \leq 0\,|\,Z_{0}=x^{\prime})\mathbb{P}(Z_{n+1}=x^{\prime}\,|\,Z_{0}=x)+ \mathbb{P}(Z_{n+1}\leq 0\,|\,Z_{0}=x).\]  
To calculate the probabilities in this expression, let us consider a truncation of the dynamics \((Z_{t})_{t=0}^{T}\) by making upper and lower ranges of the state space absorbing. Specifically, given the lower and upper boundaries \(l,u\in\mathbb{Z}\) in the state space, consider an alternative Markovian dynamic \((Z_{t}^{(l,u)})_{t=0}^{T}\) on the truncated state space \(\{l-1,\ldots u+1\}\subset\mathbb{Z}\) whose transition matrix  
\[p^{(l,u)}=(p_{x,x^{\prime}}^{(l,u)}=\mathbb{P}(Z_{t+1}^{(l,u)}=x^{\prime}|\,Z _{t}=x))_{x,x^{\prime}=l-1}^{u+1},\qquad t=0,\ldots,T\]  
is obtained from the transition matrix  
\[p=(p_{x,x^{\prime}}=\mathbb{P}(Z_{t+1}=x^{\prime}|\,Z_{t}=x))_{x,x^{\prime}\in \mathbb{Z}}\qquad t=0,\ldots,T\]  
by the truncation procedure:  
\[p_{i,j}^{(l,u)}=p_{i,j}\,\,\,\text{for}\,\,l\leq i,j\leq u,\quad p _{u-1,u-1}^{(l,u)}=p_{l+1,l+1}^{(l,u)}=1,\] \[p_{i,u+1}^{(l,u)}=\sum_{j>u}p_{i,j},\quad p_{i,l-1}^{(l,u)}=\sum_ {j<l}p_{i,j}\,\,\,\text{for}\,\,l\leq i\leq u.\]  
Please note that the evolution of \((Z_{t}^{(l,u)})_{t=0}^{T}\) coincides with that of \((Z_{t})_{t=0}^{T}\) on all states \(x\) with \(l\leq x\leq u\) but as soon as \((Z_{t})_{t=0}^{T}\) leaves this area, the dynamics becomes trapped in the lower \(l-1\in\mathbb{Z}\) or in the upper \(u+1\in\mathbb{Z}\) state depending on which boundary \(l\) or \(u\) has been crossed. Using this truncation technique, we obtain the required probabilities explicitly.  
which shows that for large \(\tilde{T}=T-n\)  
\[w_{q,n}^{\tilde{T},t}(x)\approx r_{q,n}(x)\quad\text{for $t=0,\ldots,\tilde{T}$ and $x=-n,\ldots,t$.} \tag{36}\]  
Having calculated (30) in this way, the reward (25) is obtained for \(t=0,\ldots,\tilde{T}\) by  
\[\tilde{R}_{t}(x)=(C+c)w_{q,n}^{\tilde{T},t}(t-x)-c\ \ \text{for $x=0,\ldots,t+n$.} \tag{37}\]  
These results can be combined to formulate an algorithm that calculates the optimal stopping time and the optimal value function:  
* **Step 1:** Initialize the backward induction by \[\tilde{V}_{\tilde{T}}^{E}(x)=0\quad\text{for $x=0,\ldots,\tilde{T}+n$, set $t:=\tilde{T}$.}\]
* **Step 2:** Given \(t\in\{0,\ldots,\tilde{T}\}\) 1. For \(x=0,\ldots,t+n\) define \[\tilde{R}_{t}(x)=(C+c)w_{q,n}^{\tilde{T},t}(t-x)-c.\] 2. Define \(\tilde{V}_{t}(x)=\max(\tilde{R}_{t}(x),\tilde{V}_{t}^{E}(x))\) for \(x=0,\ldots,t+n\). 3. Determine the conditional expectation \(V_{t-1}^{E}\) of the value function \(\tilde{V}_{t}\) by \[\tilde{V}_{t-1}^{E}(x)=(1-q)\sum_{j=0}^{t+n-x}\tilde{V}_{t}(x+j)q^{j}+Cq^{n+t- x+1},\] (38) for all \(x=0,\ldots,t+n-1\). If \(t>0\), then repeat the Step 2 with \(t:=t-1\). Otherwise, if \(t=0\), finish. Section 8.1 illustrates this algorithm.