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 ?

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.

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.

## 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 ?

## 2

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!

## 1

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:

Excluding answers that cannot be correct:

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

(edit)## 3

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

## 1

## Add comment