![]() |
Re: Problem 1.9
Quote:
How do you know that ![]() To proof (b) I went this way: 1. I used Markov Inequality ![]() 2. Problem 1.9(a) gave me this: ![]() ![]() Using this the rest of the proof is quite nice to carry out. |
Re: Problem 1.9
Quote:
|
Re: Problem 1.9
Here's my take on Problem 1.9, part(b), which is following the same lines as the description of MaciekLeks above.
We have: ![]() Since ![]() Also, ![]() ![]() The last line being true since [math]x_n[\math] are independent. From there it directly follows that ![]() |
Re: Problem 1.9
Quote:
Actually I don't even know how to tackle it. I think I'll need a lot of hand-holding through this one because my math got really rusty since I left school (I'm 34). |
Re: Problem 1.9
Quote:
|
Re: Problem 1.9
Quote:
|
Re: Problem 1.9
Quote:
![]() But now I'm stuck at (d). Directly substituting ![]() ![]() |
Re: Problem 1.9
Quote:
I did end up getting ![]() ![]() ![]() ![]() ![]() ![]() So now the remaining hurdle is to prove that ![]() Yay |
Re: Problem 1.9
Quote:
![]() |
Re: Problem 1.9
Quick question on Part D...
I agree that s = ln(a / (1-a)) is the value of s that minimizes e^(-sa)U(s), where I'm using "a" to represent "alpha." I think that, if you plug this value of s in, you get 2^(-b), where I'm using "b" to represent "beta." So, 2^(-b) < e^(-sa)U(s), by definition of minimization. Then, raising to the power of N, we get: 2^(-bN) < (e^(-sa)U(s))^N, but this inequality is the wrong way. Any tips? |
Re: Problem 1.9
Ah, maybe it's because the inequality holds for any s, it must hold for the min.
|
Re: Problem 1.9
Quote:
|
Re: Problem 1.9
Quote:
More tips please. When 2^(-b) is the minimize of e^(-sa)U(s), i find that 1-a = 1/2 + e (e means epsilon), so P[u>=a] = P[u>= 1/2 - e] , but not P[u>=1/2+e]. |
Re: Problem 1.9
When 2^(-b) equal to the minimize of e^(-sa)U(s), i try to assume that 1-a=1/2-e, so that a = 1/2 + e, P[u>=a]=P[u>=1/2+e]
According to (b), P[u>=1/2+e] = P[u>=a] <= (e^(-sa)U(s))^N for any s , even if the minimize of e^(-sa)U(s) when s = ln(a / (1-a)). Hence P[u>=1/2+e] <= 2^(-bN) |
Re: Problem 1.9
That's correct. But it doesn't get us anywhere.
|
Re: Problem 1.9
Ahhhm, That was a reply to kongweihan's OP.
It is correct as shown by the first line: Since... But ends up barking up the wrong tree. There is a nice description on wikipedia of Chernoff bound. It is similar to maciekleks path. |
Re: Problem 1.9
Quote:
|
All times are GMT -7. The time now is 10:18 AM. |
Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. Abu-Mostafa, Malik Magdon-Ismail, and Hsuan-Tien Lin, and participants in the Learning From Data MOOC by Yaser S. Abu-Mostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.