in Math 275 Words

Complexity of the stack algorithm

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

As long as R \leq R_0, we have that

\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

where \rho is the pareto exponent. \rho satisfies the equation

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)

we can find

f_{C_i}(x) = \frac{d}{dx}F_{C_i}(x) = -\rho Ax^{-\rho-1}

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

Hence, we get

\mathbf{E}\left[ C_i \right] = \lim_{x\rightarrow \infty}\frac{A\rho}{1-\rho}(x^{1-\rho}-1)

So given that R \leq R_0, we have that \rho \geq 1 \implies \mathbf{E}\left[ C_i \right] < \infty.

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s