# Iterative Learning for K-Approval Votes in Crowdsourcing Systems
## 5 Analysis of Algorithms
### Proof of the Theorem 1  
The proof is roughly composed of three parts. First, the second term at the right-hand side of (6) is proved using its locally tree-like property. Second, the remaining term of the right-hand side of (6) is verified using a _Chernoff bound_ in the assumption that the estimates of the task message follow _sub-Gaussian_ distribution. Lastly, we prove that the assumption of the second part is true within certain parameters. Without a loss of generality, it is possible to assume that the correct answer for each task, for any \(i\in[m]\), is \(t_{i}=\vec{e}_{1}\). Let \(\hat{t}_{i}^{(k)}\) denote the estimated answer of task \(i\) defined in Section 5.2. If we draw a task **I** uniformly at random from the task set, the average probability of error can be denoted as:  
\[\frac{1}{m}\sum_{i\in[m]}\mathbb{P}(t_{i}\
eq\hat{t}_{i}^{(k)})=\mathbb{P}(t_ {\textbf{I}}\
eq\hat{t}_{\textbf{I}}^{(k)}). \tag{8}\]  
Let \(\text{G}_{\textbf{I},k}\) denote a subgraph of the random \((l,r)\)-regular bipartite graph that consists of all of the nodes whose distance from the node \(\textbf{T}\) is at most \(k\). After \(k\) iterations, the local graph with root \(\textbf{T}\) is \(\text{G}_{\textbf{I},2k-1}\), since the update process operates twice for each iteration. To take advantage of _density evolution_, the full independence of each branch is needed. Thus, we bound the probability of error with two terms, one that represents the probability that subgraph \(\text{G}_{\textbf{I},2k-1}\) is not a tree, and the other that represents the probability that \(\text{G}_{\textbf{I},2k-1}\) is a tree with a wrong answer. \[\mathbb{P}(t_{\textbf{I}}\
eq\hat{t}_{\textbf{I}}^{(k)}) \leqslant \mathbb{P}(\text{G}_{\textbf{I},2k-1}\text{ is not a tree })+\mathbb{P}(\text{G}_{\textbf{I},2k-1}\text{ is a tree }\&\ t_{\textbf{I}}\
eq\hat{t}_{\textbf{I}}^{(k)}). \tag{9}\]  
The following lemma bounds the first term and proves that the probability that a local subgraph is not a tree vanishes as \(m\) grows. A proof of Lemma 1 is provided in [38] (cf. _[PERSON], [PERSON] and [PERSON]_ 2011, Section 3.2). Lemma 1: _From a random (\(l\),\(r\))-regular bipartite graph generated according to the pairing model,_  
\[\mathbb{P}(\text{G}_{\textbf{I},2k-1}\text{ is not a tree })\leqslant(\hat{l}\hat{r})^{(2k-2)}\frac{3 lr}{m}.\]  
From the result of Lemma 1, we can concentrate on the second term of (9) and define the pairwise difference of task messages as \(\hat{\textbf{x}}_{d}^{(k)}=\textbf{x}_{1}^{(k)}-\textbf{x}_{d}^{(k)}\) for \({}^{\forall}d\in[2:D]\):  
\[\mathbb{P}(t_{\textbf{I}}\
eq\hat{t}_{\textbf{I}}^{(k)}|\text{G}_ {\textbf{I},k}\text{ is a tree}) \leqslant\mathbb{P}(\cup_{d=2}^{D}\{\hat{\textbf{x}}_{\textbf{I }}^{(k)}\leqslant 0\}|\text{G}_{\textbf{I},k}\text{ is a tree})\] \[\leqslant\mathbb{P}(\cup_{d=2}^{D}\{\hat{\textbf{x}}_{\textbf{I }}\leqslant 0\}).\]  
To obtain a tight upper bound on \(\mathbb{P}(\cup_{d=2}^{D}\{\hat{\textbf{x}}_{d}^{(k)}\leqslant 0\})\) of our iterative algorithm, we assume that \(\hat{\textbf{x}}_{d}^{(k)}\) follows _sub-Gaussian_ distribution for any \(d\in[2:D]\). Then, a _Chernoff bound_ is applied to the independent message branches and this gives us the tight bound of our algorithm. A random variable \(\mathbf{z}\) with mean \(m\) is said to be _sub-Gaussian_ with parameter \(\tilde{\sigma}\) if for any \(\lambda\in\mathbb{R}\) the following inequality holds:  
\[\mathbb{E}[e^{\lambda\mathbf{z}}]\leqslant e^{m\lambda+(1/2)\tilde{\sigma}^{2} \lambda^{2}}. \tag{10}\]  
We show that for \(\lx@math@degree d\in[2:D]\), \(\tilde{\mathbf{x}}_{d}^{(k)}\) is _sub-Gaussian_ with mean \(m_{k}\) and parameter \(\tilde{\sigma}_{k}^{2}\) for a specific region of \(\lambda\), precisely for \(|\lambda|\leqslant 1/(2m_{k-1}\hat{r})\). Its proof is presented in Appendix A.1.