### Question 6 Exam 2019

I have a question concerning question 6 exam 2019.

When I try with numerical values (b=3, a=0.5), I find that the upper bounds are equal for a much smaller value than 10b. Indeed, I obtains for the lower bounds of both t the following values :
$$T_C = \frac{\log(\frac{\epsilon}{100b})}{\log(1-\frac{a}{100})}$$ and $$T_D = \frac{\log(\frac{\epsilon - b}{100b})}{\log(1-a)}$$
Which are not equal for $$\epsilon = 10b$$, $$a \in (0,1)$$

Is it the right way to proceed? Does anyone have answered to that question ?

Top comment

Hello,
You're right that the threshold is not exactly at $$\varepsilon = 10b$$, but it is definitely true that Oracle D is better than C in this regime. All other answers are false.
Hope that helps!

@thijs said:
Hello,
You're right that the threshold is not exactly at $$\varepsilon = 10b$$, but it is definitely true that Oracle D is better than C in this regime. All other answers are false.
Hope that helps!

Could you please explain the full procedure on how to find the correct answer on this question? I am pretty lost, some guidance would be much appreciated.

My thought process is like this:

Observation:

• Both rates have a term exponential in $$t$$, which initially is 100b. For oracle D, this decays much faster.
• Oracle D has an additional $$+b$$, which is initially quite small compared to $$100b$$, but it doesn't improve ever. If we want $$\varepsilon < b$$, oracle D is in trouble.

Excluding answers that cannot be correct:

• the algorithms do not converge equally fast
• "oracle D over C if eps < 10b" is false, because we just said that if eps < b, oracle D doesn't work.

We now test whether "oracle D over C if eps > 10b" is correct.

• The ">" looks correct: we know D is bad for small epsilon, and if $$\varepsilon >> b$$, the second term is negligible.
• Now we have to verify if $$(1-a)^t < \frac{9}{100}$$ happens quicker than $$(1-a/100)^t < \frac{10}{100}$$. (edit)
• Intuitively, 1/10 and 9/100 are very close, and the exponential terms make a big difference, so it sounds reasonable.
• If $$a$$ is close to 1, the D is clearly faster (requires only one step).
• If $$a$$ is close to 0, $$\log(1-a)$$ behaves as $$-a$$ (Taylor expansion), and hence $$(1-a)^t$$ like $$\exp(-at)$$ so here it is also faster.
• Now I'm sufficiently confident that everywhere in between it should hold too.

Hi. I am not the OP. Thanks for the explanation! I guess you meant $$(1-a)^t < \frac{9}{100}$$ and vice versa?

Page 1 of 1