# A Time-Series Model for Varying Worker Ability in Heterogeneous Distributed Computing Systems
## 3 Estimation of Latent Variable and Parameters
### Filtering and Smoothing
```  
**Algorithm 2** The SMC for filtering on workers in group \(i\). We can effectively sample from the proposal distribution \(q(x_{i,t}|\eta_{i,t},x_{i,t-1})\) by the adaptive rejection sampling (ARS) [28] since the proposal distribution is log-concave as shown in Proposition 1. Proposition 1: _The proposal distributions \(q_{0}(x_{i,0}|\eta_{i,0})\) and \(q(x_{i,t}|\eta_{i,t},x_{i,t-1})\) are log-concave functions with respect to \(x_{i,0}\) and \(x_{i,t}\), respectively._  
Proof: By (11), we have  
\[p(x_{i:0:T}|\eta_{i,0:T},l_{i,0:T},\mathbf{\theta}^{(v)})\]1  
The second-order partial derivative of the above function with respect to \(x_{i,0}\) evaluates to  
\[p(x_{i:0:T}|\eta_{i,0:T},l_{i,0:T},\mathbf{\theta}^{(v)})\]2which is negative for all real values \(x_{i,0}\). Since the logarithm of the function is concave, the proposal distribution \(q_{0}(x_{i,0}|\eta_{i,0})\) is log-concave in \(x_{i,0}\). Similarly, (12) implies  
\[p(x_{i:0:T}|\eta_{i,0:T},l_{i,0:T},\mathbf{\theta}^{(v)})\]3  
The second-order partial derivative with respect to \(x_{i,t}\) gives the following negative value for all real \(x_{i,t}\):  
\[p(x_{i:0:T}|\eta_{i,0:T},l_{i,0:T},\mathbf{\theta}^{(v)})\]4  
Therefore, the proposal distribution \(q(x_{i,t}|\eta_{i,t},x_{i,t-1})\) is log-concave in \(x_{i,t}\). We resample at every time step so that the particle sequences have equally weighted samples. In this paper, we use the multinomial resampling [22], which involves sampling from the multinomial distribution. The sampling probabilities are given by the weights of the corresponding original weighted samples. Then, we can calculate  
\[p(x_{i:0:T}|\eta_{i,0:T},l_{i,0:T},\mathbf{\theta}^{(v)})\]5  
the approximation of the desired distribution by employing Algorithm 2. However, note that we cannot directly use the output  
\[p(x_{i:0:T}|\eta_{i,0:T},l_{i,0:T},\mathbf{\theta}^{(v)})\]6  
to the EM algorithm because the particle filtering method often suffers from the sample impoverishment, called the degeneracy problem. When the number of distinct particles  
\[p(x_{i:0:T}|\eta_{i,0:T},l_{i,0:T},\mathbf{\theta}^{(v)})\]7  
is too small for \(t\ll T\), it can lead to  
\[p(x_{i:0:T}|\eta_{i,0:T},l_{i,0:T},\mathbf{\theta}^{(v)})\]8  
is not reliable for \(t\ll T\). Therefore, from Algorithm 2, we can take the filtered marginal distribution  
\[p(x_{i:0:T}|\eta_{i,0:T},l_{i,0:T},\mathbf{\theta}^{(v)})\]9  
of the distribution  
\[q_{0}(x_{i,0}|\eta_{i,0})=p(x_{i,0}|\eta_{i,0})\]0  
at time \(s=0,1,\ldots,T\), when we are interested in the online estimation of state variables. We have  
\[q_{0}(x_{i,0}|\eta_{i,0})=p(x_{i,0}|\eta_{i,0})\]1  
for \(t\in[T]_{0}\), where \(\delta_{x_{0}}(x)\) is the Dirac delta mass located at \(x_{0}\). Note that the weights are the same as \(1/L\) due to resampling at the last step. To obtain the smoothed estimate  
\[q_{0}(x_{i,0}|\eta_{i,0})=p(x_{i,0}|\eta_{i,0})\]2  
for the EM algorithm, we rely on the forward-filtering backward-sampling (FFBSa) algorithm using the filtered particles \(x_{i,t|t}^{(l)}\), \(l\in[L]\), in (13). The detailed process is given in Algorithm 3. ```
Input: \(\eta_{i,0:T}\), \(l_{i,0:T}\), \(\mathbf{\theta}^{(v)}\). Run Algorithm 2 to obtain the filtered distribution \[q_{0}(x_{i,0}|\eta_{i,0})=p(x_{i,0}|\eta_{i,0})\]3  Sample \(x_{i,T}^{(l)}\) from \[q_{0}(x_{i,0}|\eta_{i,0})=p(x_{i,0}|\eta_{i,0})\]4 \[q_{0}(x_{i,0}|\eta_{i,0})=p(x_{i,0}|\eta_{i,0})\]5  For \(t=T-1,T-2,\ldots,1,0\), sample \(x_{i,t|T}^{(l)}\) from \[q_{0}(x_{i,0}|\eta_{i,0})=p(x_{i,0}|\eta_{i,0})\]6 \[q_{0}(x_{i,0}|\eta_{i,0})=p(x_{i,0}|\eta_{i,0})\]7 where \[q_{0}(x_{i,0}|\eta_{i,0})=p(x_{i,0}|\eta_{i,0})\]8 Output: \(\hat{p}(x_{i,t}|\eta_{i,0:T},l_{i,0:T},\mathbf{\theta}^{(v)}),\ t=0,1,\ldots,T\). ```  
**Algorithm 3** FFBSa on workers in group \(i\). By Algorithm 3, an estimate of the smoothed marginal distribution of \(x_{i}^{t}\) is represented as  
\[q_{0}(x_{i,0}|\eta_{i,0})=p(x_{i,0}|\eta_{i,0})\]9  
for \(t=0,1,\ldots,T\).