Comments on: Homework 5: Randomization

By: admin

admin — Mon, 03 Dec 2007 08:55:13 +0000

Part of the problem is to find a reasonable strategy. It doesn’t have to be optimal, as long as you can show the desired bound.

By: Question 5 (13.16)

Question 5 (13.16) — Mon, 03 Dec 2007 08:53:09 +0000

Can we assume any strategy we like(that simplifies the math rather than being optimal) that the receivers use collaboratively to produce $\beta$? If not, is the closed form for $k$ a must?

By: admin

admin — Mon, 03 Dec 2007 01:18:09 +0000

p.s it helps me if you post some identifying marker as your ID, rather than Anonymous. You don’t need to post your name: merely something that allows me to connect the various conversation threads together.

By: admin

admin — Mon, 03 Dec 2007 01:17:22 +0000

Regarding 5.2, as I said earlier, assume that e = 1 (which doesn’t make any sense anyway).

Regarding 5.5, you can solve for any k you want, as long as you get the desired bound. And to answer the second part of the question, the probability of success can be at least 9/10.

By: Anonymous

Anonymous — Mon, 03 Dec 2007 00:15:25 +0000

In problem 5.5 (13.16 in the text) must k be a function of n? Can k be a constant?
Also, does the probability of B being correct have to be 9/10 or can it be greater?

By: Anonymous

Anonymous — Sun, 02 Dec 2007 23:49:51 +0000

Again, for 5.2:
You say it is impossible to assign a constant value to c when e = 0,
well you can assign c to 2*sqrt(n) and this will make the boolean statement always false, correct? however you can also assign anything greater than 2*sqrt(n) and this is why we cannot assign a ‘constant’ value, correct?
Well if this is the case for the ‘upper bound’ for assigning a constant to c (’lower bound’ for e), then the ‘lower bound’ for assigning a constant value to c should also be present (this is an assumption, not a logical connection) Investigating if there is actually a ‘lower bound’ one will find -2*sqrt = c. This is the ‘upper bound’ for e, 1, which means that it is always possible. This makes sense, for if we have any c less than -2*sqrt(n), then the statement is always true. If this is in fact the case, I can’t prove that for any e > 0, there exists a constant c for the provided statement. For there is not a single constant value for c when e >= 1.
Where has my logic been lost?

By: admin

admin — Sun, 02 Dec 2007 23:27:22 +0000

In other words, if we adopt a deterministic approach, then this assignment of k processes to 2 machines would have been determined once at the start only. And then all n jobs would run their 2n processes according to that mapping??

Yes, that’s exactly right. And in the randomized case, all that changes is that the assignment is determined in a randomized machine. It is still determined at the start.

By: Anonymous

Anonymous — Sun, 02 Dec 2007 23:24:04 +0000

Thanks. Hmmm… perhaps I am not able to comprehend the problem well. Suppose, for a moment, we don’t think of randomizing the assignment. Then essentially, this translates to figuring out an assignment of all the ‘k’ basic processes (which is the universal set P, where k>2n) to either M1 or M2. And we’d like to do so in a way which “nearly balances” some n subsets of P (where each subset has size 2n).
In other words, if we adopt a deterministic approach, then this assignment of k processes to 2 machines would have been determined once at the start only. And then all n jobs would run their 2n processes according to that mapping??

By: admin

admin — Sun, 02 Dec 2007 23:17:53 +0000

Well, it’s impossible to assign a constant for the case e = 0, because even a heavily skewed assignment is possible with some nonzero probability. What will happen is that the value of c will grow without bound as e tends to zero.

In general, it does not make sense to set epsilon to be more than 1, yes.

If you’re asking whether there should be a corresponding upper bound for the Pr(Xh - Xt c*sqrt{n})), which requires different kinds of arguments.

By: Anonymous

Anonymous — Sun, 02 Dec 2007 22:57:46 +0000

Did that go through?