Suppose that the running time of a randomized algorithm is modeled by the random

Question

Suppose that the running time of a randomized algorithm is modeled by the random variable X. Suppose that you know the expected running time E[X]. You know that your algorithm has a worst case running time that exceeds E[X] by a significant margin. Therefore, you decide to stop the execution whenever it exceeds (1 + e)E[X] steps, and restart the algorithm. You will repeat the execution of the algorithm at most t times. Denote by X_k the random variable modeling running time of the k-th try. Determine the probability that the randomized algorithm exceeds (1 + e)E[X] steps in all t repetitions. This probability models the failure probability of this algorithm.

Explanation / Answer

here we have to find t variables such that:

Probability of failure = P(X_1 > (1 + e)E(X)) + P(X_2 > (1 + e)E(X)) + .... + P(X_t > (1 + e)E(X))

These are t random variables, and according to central limit theorem, sum of all of them will follow normal distribution. For this distribution, the mean will be = E(P(X_1 > (1 + e)E(X)) + P(X_2 > (1 + e)E(X)) + .... + P(X_t > (1 + e)E(X)))

which is t(1 + e)E(X)

and standard deviation will be = t/2 (1 + e) E(X)

So the probability will be

P(X_t) = (1 / sqrt(2 * pie * t^2 * (1+e)^2 * E(X)^2)) * exp(-(X_t - t*(1 + e)E(X))^2 / 2 * (t/2 (1+e) E(X) )^2)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.