Problem 1.9 - Page 2

RicLouRiv · #11 06-23-2017, 04:42 PM

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?

RicLouRiv · #12 06-24-2017, 09:36 AM

Ah, maybe it's because the inequality holds for any s, it must hold for the min.

htlin · #13 06-29-2017, 10:00 PM

Quote:

Originally Posted by RicLouRiv

Ah, maybe it's because the inequality holds for any s, it must hold for the min.

You got it. :-)

mygame182 · #14 10-22-2017, 04:19 AM

Quote:

Originally Posted by RicLouRiv

Ah, maybe it's because the inequality holds for any s, it must hold for the min.

Excuse me, I can understand your last reply, but confuse in this one.
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].

mygame182 · #15 10-23-2017, 08:23 AM

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)

don slowik · #16 11-14-2017, 03:14 PM

That's correct. But it doesn't get us anywhere.

don slowik · #17 11-14-2017, 03:18 PM

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.

Ulyssesyang · #18 11-09-2018, 07:02 PM

Quote:

Originally Posted by svend

Here's my take on Problem 1.9, part(b), which is following the same lines as the description of MaciekLeks above.

We have:

$\begin{split} P(u \geq \alpha ) & = P(\frac{1}{N}{}\sum_n x_n \geq \alpha) \\ & = P(\sum_n x_n \geq N \alpha) \\ & = P(e^{s \sum_n x_n} \geq e^{s N \alpha}) \end{split}$

Since $e^{s t}$ is monotonically increasing in t.

Also, $e^{s t}$ is non negative for all t, implying Markov inequality holds:

$\begin{split} P(e^{s \sum_n x_n} \geq e^{s N \alpha}) & \leq \frac{E(e^{s \sum_n x_n})}{e^{s N \alpha}} \\ & = \frac{E(\prod_n e^{s x_n})}{e^{s N \alpha}} \\ & = \frac{\prod_n E(e^{s x_n})}{e^{s N \alpha}} \end{split}$

The last line being true since [math]x_n[\math] are independent.

From there it directly follows that

$P(u \geq \alpha ) \leq U(s)^N e^{-s N \alpha}$

I just think you should note that there are two expectations, one is based on e^su_n, while other is based on u_n. Of course, you can refer the law of unconscious statisticians to prove that both are same.

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode