The complexity of the stack algorithm is non-deterministic. As long as the rate of the code is less than the computational cutoff rate, the expected complexity is bounded.
The computational cutoff rate is given by
![R_0 = 1-\log_2\left(\sqrt{\mathbf{Pr}\left[ \textnormal{bit error}\right]}+\sqrt{1-\mathbf{Pr}\left[ \textnormal{bit error}\right]}\right)^2](https://s0.wp.com/latex.php?latex=R_0+%3D+1-%5Clog_2%5Cleft%28%5Csqrt%7B%5Cmathbf%7BPr%7D%5Cleft%5B+%5Ctextnormal%7Bbit+error%7D%5Cright%5D%7D%2B%5Csqrt%7B1-%5Cmathbf%7BPr%7D%5Cleft%5B+%5Ctextnormal%7Bbit+error%7D%5Cright%5D%7D%5Cright%29%5E2&bg=ffffff&fg=000000&s=0 "R_0 = 1-\log_2\left(\sqrt{\mathbf{Pr}\left[ \textnormal{bit error}\right]}+\sqrt{1-\mathbf{Pr}\left[ \textnormal{bit error}\right]}\right)^2")
As long as 
![\mathbf{E}\left[ C_i \right] = \textnormal{\# computations for symbol } i < \infty](https://s0.wp.com/latex.php?latex=%5Cmathbf%7BE%7D%5Cleft%5B+C_i+%5Cright%5D+%3D+%5Ctextnormal%7B%5C%23+computations+for+symbol+%7D+i+%3C+%5Cinfty&bg=ffffff&fg=000000&s=0 "\mathbf{E}\left[ C_i \right] = \textnormal{\# computations for symbol } i < \infty")
The computation time has the distribution
![\mathbf{Pr}\left[ C_i \geq \psi\right] \approx A\psi^{-\rho}, \quad 0 < \rho < \infty, \quad 0 \leq i \leq k](https://s0.wp.com/latex.php?latex=%5Cmathbf%7BPr%7D%5Cleft%5B+C_i+%5Cgeq+%5Cpsi%5Cright%5D+%5Capprox+A%5Cpsi%5E%7B-%5Crho%7D%2C+%5Cquad+0+%3C+%5Crho+%3C+%5Cinfty%2C+%5Cquad+0+%5Cleq+i+%5Cleq+k&bg=ffffff&fg=000000&s=0 "\mathbf{Pr}\left[ C_i \geq \psi\right] \approx A\psi^{-\rho}, \quad 0 < \rho < \infty, \quad 0 \leq i \leq k")
where 
![R = \frac{\rho-\log_2\left( \left( \mathbf{Pr}\left[ \textnormal{bit error}\right]\right)^{1/(1+\rho)}+ \left( 1-\mathbf{Pr}\left[ \textnormal{bit error}\right]\right)^{1/(1+\rho)}\right)^{1+\rho}}{\rho}](https://s0.wp.com/latex.php?latex=R+%3D+%5Cfrac%7B%5Crho-%5Clog_2%5Cleft%28++%5Cleft%28++%5Cmathbf%7BPr%7D%5Cleft%5B+%5Ctextnormal%7Bbit+error%7D%5Cright%5D%5Cright%29%5E%7B1%2F%281%2B%5Crho%29%7D%2B++%5Cleft%28++1-%5Cmathbf%7BPr%7D%5Cleft%5B+%5Ctextnormal%7Bbit+error%7D%5Cright%5D%5Cright%29%5E%7B1%2F%281%2B%5Crho%29%7D%5Cright%29%5E%7B1%2B%5Crho%7D%7D%7B%5Crho%7D&bg=ffffff&fg=000000&s=0 "R = \frac{\rho-\log_2\left( \left( \mathbf{Pr}\left[ \textnormal{bit error}\right]\right)^{1/(1+\rho)}+ \left( 1-\mathbf{Pr}\left[ \textnormal{bit error}\right]\right)^{1/(1+\rho)}\right)^{1+\rho}}{\rho}")
Since
![\mathbf{Pr}\left[ C_i \geq \psi\right] = F_{C_i}(\psi) = \int_\psi^\infty f_{C_i}(x)](https://s0.wp.com/latex.php?latex=%5Cmathbf%7BPr%7D%5Cleft%5B+C_i+%5Cgeq+%5Cpsi%5Cright%5D+%3D+F_%7BC_i%7D%28%5Cpsi%29+%3D+%5Cint_%5Cpsi%5E%5Cinfty+f_%7BC_i%7D%28x%29&bg=ffffff&fg=000000&s=0 "\mathbf{Pr}\left[ C_i \geq \psi\right] = F_{C_i}(\psi) = \int_\psi^\infty f_{C_i}(x)")
we can find
So the expected value
![\mathbf{E}\left[ C_i \right] = \int_0^\infty xf_{C_i}(x) = -\int_0^\infty \rho Ax^{-\rho} = A\rho\left[ \frac{x^{1-\rho}}{1-\rho} \right]_0^\infty](https://s0.wp.com/latex.php?latex=%5Cmathbf%7BE%7D%5Cleft%5B+C_i+%5Cright%5D+%3D+%5Cint_0%5E%5Cinfty+xf_%7BC_i%7D%28x%29+%3D+-%5Cint_0%5E%5Cinfty+%5Crho+Ax%5E%7B-%5Crho%7D+%3D+A%5Crho%5Cleft%5B+%5Cfrac%7Bx%5E%7B1-%5Crho%7D%7D%7B1-%5Crho%7D+%5Cright%5D_0%5E%5Cinfty&bg=ffffff&fg=000000&s=0 "\mathbf{E}\left[ C_i \right] = \int_0^\infty xf_{C_i}(x) = -\int_0^\infty \rho Ax^{-\rho} = A\rho\left[ \frac{x^{1-\rho}}{1-\rho} \right]_0^\infty")
Hence, we get
![\mathbf{E}\left[ C_i \right] = \lim_{x\rightarrow \infty}\frac{A\rho}{1-\rho}(x^{1-\rho}-1)](https://s0.wp.com/latex.php?latex=%5Cmathbf%7BE%7D%5Cleft%5B+C_i+%5Cright%5D+%3D+%5Clim_%7Bx%5Crightarrow+%5Cinfty%7D%5Cfrac%7BA%5Crho%7D%7B1-%5Crho%7D%28x%5E%7B1-%5Crho%7D-1%29&bg=ffffff&fg=000000&s=0 "\mathbf{E}\left[ C_i \right] = \lim_{x\rightarrow \infty}\frac{A\rho}{1-\rho}(x^{1-\rho}-1)")
So given that ![\rho \geq 1 \implies \mathbf{E}\left[ C_i \right] < \infty](https://s0.wp.com/latex.php?latex=%5Crho+%5Cgeq+1+%5Cimplies+%5Cmathbf%7BE%7D%5Cleft%5B+C_i+%5Cright%5D+%3C+%5Cinfty&bg=ffffff&fg=000000&s=0 "\rho \geq 1 \implies \mathbf{E}\left[ C_i \right] < \infty")
Advertisements
