First, I was asked about what could be computed if time travel were possible. See this paper for some answers.
We saw a few polynomial-time reductions in class. Here’s a paper which shows that 3SAT reduces to Super Mario Bros.
Posted by James on February 28, 2012
Due, in class: March 7th
For this homework, you will need to turn in your solutions in two parts. This is for ease of grading by the TAs. Problems 1-2 and 3-5 should be turned in on different sheets of paper (there will be two different piles).
In solving the problem sets, you are allowed to collaborate with fellow students taking the class, but remember that you are required to write up the solutions by yourself or with a single partner. If you do collaborate in any way, you must acknowledge, for each problem, the people you worked with on that problem.
The problems have been carefully chosen for their pedagogical value, and hence might be similar to those given in past offerings of this course at UW, or similar to other courses at other schools. Using any pre-existing solutions from these sources, for from the web, constitutes a violation of the academic integrity you are expected to exemplify, and is strictly prohibited.
Most of the problems only require one or two key ideas for their solution. It will help you a lot to spell out these main ideas so that you can get most of the credit for a problem even if you err on the finer details.
A final piece of advice: Start working on the problem sets early! Don’t wait until the day (or few days) before they’re due.
Look at the fair/biased coin example in the hypothesis testing slides.
The Big Boss at Amazoogle.com says that based on long experience, the best model for errors in software is that experienced programmers make errors at a rate of p errors per line of code (say, for p= 0.001), no matter what you do. The salesperson for Ecliptic insists their IDE will save megabucks by reducing the error rate per line to q = p/2 (“… and just for you, this week only, there’s a special sale price, don’t miss it, blah, blah, …”). The Big Boss is a skeptic, but willing to experiment, and arranges for m different programs to be written using the new IDE, with lengths n_{1}, n_{2}, …, n_{m} and the QC department finds, respectively, x_{1}, x_{2}, …, x_{m} errors in them.
The Boss asks you to analyze and present the results to Management. Being a whiz at hypothesis testing, you know just what to do.
Posted in Homework | 29 Comments »
Posted by James on February 26, 2012
Final Exam: Monday, March 12, 2012,230-420 pm
Posted in Announcement | Leave a Comment »
Posted by James on February 24, 2012
Reading: BT, Section 9.1.
Many families of distributions can be specified using a parameter, e.g. (binomial with success proabability p), , , , , etc. We write the parameter(s) as , which could be a vector. E.g. for a normal random variable with distribution , we would have . These are called parametric models, and our general goal is: Given many independent samples from such a model, determine as best we can.
Let be i.i.d. samples from some distribution with mean and variance . Recall the sample mean . We defined the sample variance by:
Now the 100(1-a)% confidence interval is the interval given by
where is such that , where is the CDF of an N(0,1) random variable. (See here for the CDF table.)
Recall that this intuition behind this interval is this: For large n, the probability that the true value of falls in this interval is at least 100(1-a)%. This would be true if our sample mean was truly distributed as an random variable. Here, we make the implicit assumption that for large n, the Central Limit Theorem has kicked in enough to justify a normal approximation.
Recall that the k-th moment of a random variable X is . In this case, the sample moment is the random variable given by , where are i.i.d. samples from the distribution.
For instance, the MOM estimate for the variance would be , following the formula .
If our estimator (which, remember, is a random variable!) is , then the bias of the estimator is defined by , where is true value of the underlying parameter.
An estimator is called unbiased if it has bias = 0. In particular, the sample mean and sample variance are unbiased, while the MOM estimate for the variance is biased (though its bias goes to 0 as ).
We ended by showing how the MOM could be used to estimate parameters for a number of distributions. For instance, if we have i.i.d. samples from a distribution, then the MOM estimate for p would be
For a more interesting example, consider samples from a distribution, i.e. a distribution which is uniform on the interval [a,b]. We know from previous lectures, that this distribution has and . Thus we can use the MOM to find estimates and by solving the system of two questions: and . The result is and , where .
Posted in Lecture | Leave a Comment »
Posted by James on February 23, 2012
Due, in class: February 22nd
For this homework, you will need to turn in your solutions in two parts. This is for ease of grading by the TAs. Problems 1-3 and 4-7 should be turned in on different sheets of paper (there will be two different piles).
In solving the problem sets, you are allowed to collaborate with fellow students taking the class, but remember that you are required to write up the solutions by yourself or with a single partner. If you do collaborate in any way, you must acknowledge, for each problem, the people you worked with on that problem.
The problems have been carefully chosen for their pedagogical value, and hence might be similar to those given in past offerings of this course at UW, or similar to other courses at other schools. Using any pre-existing solutions from these sources, for from the web, constitutes a violation of the academic integrity you are expected to exemplify, and is strictly prohibited.
Most of the problems only require one or two key ideas for their solution. It will help you a lot to spell out these main ideas so that you can get most of the credit for a problem even if you err on the finer details.
A final piece of advice: Start working on the problem sets early! Don’t wait until the day (or few days) before they’re due.
where is some positive parameter.
Verify that f is a proper density function. Evaluate the mean and variance of X in terms of .
For any nonnegative real number x, let Int(x) be the largest integer that is less than or equal to x. Show that if U is a uniform random variable on [0,1], then the variable X = Int(nU)+1 is a discrete uniform random variable on {1,2,…,n}.
Suppose you have 20 independent random variables which are all uniformly distributed on [0,1]. Define:
Use the Central Limit Theorem to estimate the probability that X is NOT in the range [8,14]. Show your calculation!
We know that if are random variables then
But what happens if N is itself a random number?
Give an example which shows that linearity of expectation does not hold.
Now assume that for every n=1,2,3,… whether the event occurs can be determined by looking only at the values . Show that in this case, linearity of expectation once again holds.
Posted in Homework | 25 Comments »