Week 9 -probabilistic algorithms

Question 1

E(aX + B)

Answer 1

a E(x) + b

Question 2

E(X + Y)

Answer 2

E(X) + E(Y)

Question 3

How to calculate expected termination time

Answer 3

Expectedterminationtime=numberofstepsperpath(weightedbyprobability)×probabilityofreachingthatpath

if you ahve multiple branches you just add the expected termination time of each branch

Question 4

summary of probabilistic turing machine

Answer 4

A probabilistic Turing machine makes choices based on probabilities during computation, which means the same input can produce different outputs when run through the same machine multiple times.

To handle this uncertainty and increase confidence in the result, we typically run the machine many times on the same input to minimize the chance of getting an incorrect answer.

Question 5

markovs inequality

Answer 5

P(X≥t)≤ E(X) / t [ original form of markovs]

sub t = a * E(x) you get :

P(X≥ a⋅E(X))≤ 1 / a
​
.

​
.

Question 6

Var(X)

Answer 6

E(X^2) - [E(x)]^2

Question 7

standard deviation

Answer 7

sqrt(Var(X))

Question 8

What are the 3 properties of a language solvable in bounded-error probabilistic polynomial time (BPP)?

Answer 8

Probabilistically “Sound”
Probabilistically “Complete”
Polynomial-Time

Question 9

Question: Explain the “Probabilistically Sound” property in BPP.

Answer 9

If a word 𝑤 ∉ 𝐿 (not part of the language), the probabilistic machine 𝑀 should rarely accept it.

Formally:

Prob (𝑀(𝑤)=1) ≤ 1 / 3

This means the machine makes errors in rejecting invalid inputs, but the probability of error is bounded by
1/ 3

​
.

Question 10

Explain the “Probabilistically Complete” property in BPP.

Answer 10

If a word 𝑤 ∈ 𝐿 (part of the language), the probabilistic machine 𝑀 should correctly accept it with high probability.
Formally:

Prob (𝑀(𝑤) = 1) ≥ 2 / 3

This ensures the machine reliably accepts valid inputs.

Question 11

Explain the “Polynomial-Time” property in BPP.

Answer 11

The probabilistic machine
𝑀
M must run in polynomial time.
Formally:

𝑇(𝑛) ∈ 𝑂(𝑛^𝑘) forsome 𝑘 > 0.

This guarantees the machine is efficient and its runtime grows polynomially with input size.

Question 12

What are the 3 properties of a language solvable in zero-error probabilistic polynomial time (ZPP)?

Answer 12

Sound
Complete
Expected Polynomial-Time

Question 13

Explain the “Sound” property in ZPP.

Answer 13

If a word 𝑤 ∉ 𝐿 (not part of the language), the probabilistic machine 𝑀 will never accept it.

Formally:
Prob (𝑀(𝑤) = 1) =0.

This ensures that there are no false positives.

Question 14

Explain the “Complete” property in ZPP.

Answer 14

If a word 𝑤 ∈ 𝐿 (part of the language), the probabilistic machine M will always accept it.
Formally: Prob (𝑀(𝑤) =1) =1.

This ensures that there are no false negatives

Question 15

Explain the “Expected Polynomial-Time” property in ZPP.

Answer 15

The probabilistic machine
𝑀
M must run in expected polynomial time.

Formally:
E[T(n)]∈O(n ^k )forsomek>0.

This ensures that the machine’s runtime, on average, grows polynomially with input size.

Question 16

difference between BPP and ZPP

Answer 16

BPP: Efficiency (polynomial time) is prioritized over perfect accuracy (small errors allowed).

ZPP: Accuracy (zero errors) is prioritized over strict efficiency (expected polynomial time, not guaranteed for every case).

Question 17

: What is a Monte Carlo algorithm?

Answer 17

A randomized algorithm with deterministic runtime, meaning it always runs in polynomial time, but may return incorrect answers due to its probabilistic nature. This trade-off allows small probabilities of error.

Question 18

What is a Las Vegas algorithm?

Answer 18

A randomized algorithm that is always sound and complete, meaning it provides zero false answers (no false positives or negatives). However, its runtime may vary probabilistically, though it often has expected polynomial runtime.