For question 6.2, it says the constant c may be a function of epsilon, is c also a function of n or constant with respect to n?
This questions appears trivial in that if c=2n, the probability Pr(x_H - x_T > 2n*sqrt(n) ) will always be zero, because there are at most 2n tosses. Is this what the question is asking for?
* the number of truly random bits you extract is a random variable. what is the expectation of this random variable
* this question is related to 1(a) yes.
* c is a constant that you need to determine. it is not a function of n
* again: c is a constant, and so it can’t be 2n. You are of course right that if c = 2n, this probability is zero, but that’s not the interesting case, is it ? the interesting case is when c is a constant.
I am not sure if I get the question 4 right. The randomized load balancing says each job j_i has exactly 2n processes. Does the processes have any preference on the machine on which it should be run (p_o has to run on M_1 and so on)? If not, isnt the problem trivial - jus assign the first n jobs of each p_i to M_1 and the next n jobs to M_2. I know I am missing something here.
Think of this example (and btw you’ve flipped jobs and processes).
There’s a fixed set of processes (A, B, C, D) say. Each Job chooses a subset of 2n = 2 (n=1) processes.
So a job sequence could be
J1: A, B
J2: A, C
J3: C, D
J4: B, C
Processes are mapped to machines in advance: say, A, B are on machine 1, and C, D are on machine 2.
By this assignment, J1 and J3 are not balanced, and J2 and J4 are.
To answer your question now, each job doesn’t have the flexibility to decide where its processes go. J1 cannot decide to run B on machine 2, and then J4 can’t run B on machine 1. The processes are assigned to machines independently of the jobs.
In question 6.4(a), what does “arbitrary large value of n” mean? Does it mean that for any value of n, there is a non-balanced sequence; or does it mean when n is large enough there exists such a sequence.
If it’s the latter case, what’s the relation between n and k. Obviously, when n becomes close to k there aren’t n distinct jobs, in which case it’s relatively simple to prove the argument. But I’m not sure if this is what the question is asking for…..
To your previous response, I think k should have a larger lower bound than 2n. If k=2n+1, and each job includes 2n processes, than there are at most 2 distinct jobs, rather than n. We must assume each job is distinct (that is, any two jobs must differ in at least one process), right?
Entries
December 5th, 2008 at 1:54 pm
For problem 6.2, should there be an absolute value around X_H - X_T since X_T could be greater than X_H?
December 5th, 2008 at 2:07 pm
it’s symmetric, so it doesn’t really matter asymptotically. you can do it either way
December 6th, 2008 at 10:32 pm
For question 6.1 b, can you explain what “the expected number of bits” means?
Also, is this question related to 1(a)? That is, shall we simply toss the coin 2n times, or toss 2n times but follow the Neumann method in (a)?
December 6th, 2008 at 10:40 pm
For question 6.2, it says the constant c may be a function of epsilon, is c also a function of n or constant with respect to n?
This questions appears trivial in that if c=2n, the probability Pr(x_H - x_T > 2n*sqrt(n) ) will always be zero, because there are at most 2n tosses. Is this what the question is asking for?
December 6th, 2008 at 10:43 pm
In response to Dafang’s questions:
* the number of truly random bits you extract is a random variable. what is the expectation of this random variable
* this question is related to 1(a) yes.
* c is a constant that you need to determine. it is not a function of n
* again: c is a constant, and so it can’t be 2n. You are of course right that if c = 2n, this probability is zero, but that’s not the interesting case, is it ? the interesting case is when c is a constant.
December 6th, 2008 at 11:36 pm
So 6.2 can be stated as, for any epsilon, there exists a constant c such that for any value of n, that inequation holds, right?
December 6th, 2008 at 11:38 pm
Or rather, for any epsilon, FIND a constant c such that the inequality holds for all n (or all n above a certain n_0, as usual)
December 8th, 2008 at 3:19 pm
I am not sure if I get the question 4 right. The randomized load balancing says each job j_i has exactly 2n processes. Does the processes have any preference on the machine on which it should be run (p_o has to run on M_1 and so on)? If not, isnt the problem trivial - jus assign the first n jobs of each p_i to M_1 and the next n jobs to M_2. I know I am missing something here.
December 8th, 2008 at 4:02 pm
Think of this example (and btw you’ve flipped jobs and processes).
There’s a fixed set of processes (A, B, C, D) say. Each Job chooses a subset of 2n = 2 (n=1) processes.
So a job sequence could be
J1: A, B
J2: A, C
J3: C, D
J4: B, C
Processes are mapped to machines in advance: say, A, B are on machine 1, and C, D are on machine 2.
By this assignment, J1 and J3 are not balanced, and J2 and J4 are.
To answer your question now, each job doesn’t have the flexibility to decide where its processes go. J1 cannot decide to run B on machine 2, and then J4 can’t run B on machine 1. The processes are assigned to machines independently of the jobs.
December 8th, 2008 at 4:30 pm
On problem 4, it says there are n jobs and each job has 2n processes. Are those 2 n’s the same?
December 8th, 2008 at 5:06 pm
yes. both ns are the same
December 8th, 2008 at 11:07 pm
Problem 4 again:
Can a process “stop” and then “start” again? I.e., is your above job sequence a valid sequence?
December 9th, 2008 at 12:27 am
think of these as processes that are applied repeatedly
December 9th, 2008 at 2:56 am
In question 6.4(a), what does “arbitrary large value of n” mean? Does it mean that for any value of n, there is a non-balanced sequence; or does it mean when n is large enough there exists such a sequence.
If it’s the latter case, what’s the relation between n and k. Obviously, when n becomes close to k there aren’t n distinct jobs, in which case it’s relatively simple to prove the argument. But I’m not sure if this is what the question is asking for…..
December 9th, 2008 at 10:12 am
Just show it to be true when n is large enough. The only assumption you need is that k > 2n.
December 9th, 2008 at 1:32 pm
To your previous response, I think k should have a larger lower bound than 2n. If k=2n+1, and each job includes 2n processes, than there are at most 2 distinct jobs, rather than n. We must assume each job is distinct (that is, any two jobs must differ in at least one process), right?