This page is to keep a record of typos in Coursework 2 (5 to date, though mostly minor), and also a record of Questions I've been asked by students trying to understand the work (not giving away any of their individual ideas). And the occasional hint. Here is the updated specification for coursework 2 (refresh the link to make sure you have the updated version).
I have also uploaded the courseork to "nb" and put in the comments "inline" there, as it might be easier to annotate paper copies from that .... Link to "nb" is here (note if you were having problems viewing the page in the past, try a different browser).
In part (b) of Q2, I should have been asking about the probability that all the estimated p_i values satisfy
|p_i - \widehat{p}_i| <= 1/(n^3)
(in other words, I originally had the inequality the wrong way).
Apologies, and thanks to Martynas for spotting that.
Also in part (b) of Q2, I should have asked you to show (conditional of having the result from (a)) to show that the probability that all the estimated \widehat{p}_i values satisfy
|p_i - \widehat{p}_i| <= 1/(n^3) is
approximately e^(-0.1).
(I originally had written "at least", but it's not quite true, though very close). Thanks to Cameron for noticing this one. For more discussion about Q2 see QandA/hints below.
[2/(m(m-1))]*[2/(n(n-1))], multiplied by 1/|\sigma_{a,b}| for the specific a_1, a_2, b_1, b_2 of that particular sub-table.
(I had missed-out the "2" on top of the n(n-1)). Thanks Ross for spotting this.
d(W,Z) ={def} \sum_{i=1}^m\sum_{j=1}^n |W_{ij}-Z_{ij}|
(My hand slipped and there was a X_{ij} written instead of W_{ij} inside the sum). Spotted this one myself....
The definition of a stationary distribution is that we have (for \pi written as a row vector)
\pi . M = \pi
So this is what I want you to show for this chain. Thanks Chris for spotting this.
Hint/Advice: The solutions for Q5 (b) of the first coursework (here) will help with this one. It'll be better if you were actually at the "tutorial" a week ago, but even the solutions will help.
Also, one warning: we are using \ell for "number of samples" because n means something different for us (the number of different estimates we will need to consider in step (b)). That means it is sensible, in doing your workings, to write out Chernoff with \ell in place of n. And then start from there. It'll avoid confusion with "our n".
To get this one to work out, basically you need to express the condition for having the estimate \widehat{p_i} close-enough (1/n^3) to p_i (with high probab.) in terms of the sum of all the \ell individual Bernoulli variables (all with prob. p_i). Then you need to look at the Chernoff bounds (the symmetric bound of 4.6) and work out
QandA over email: There have been a couple of discussion over email about what I *want* here. The change of "at least" to "approximately" makes the question less clear.
One student asked do I want both a Lower bound and an Upper bound. I don't (though it is possible to show both if you take the approach I was hoping), but I would like it to be a good approximation.
I was hoping that in doing the "step" from Q2(a) to Q2(b), that you would not use the "Union Bound". I did use the Union Bound in my solution for Q5(c), so I want you to do something different. The problem is that Union Bound is a weak way of bounding the probability of a "union of events" when those individual events are **independent**. Yes, when you don't have knowledge of independence, Union Bound is often all you can do, but in this case you *do* have knowledge of independence (the bits for position i, with prob p_i, are generated entirely independently of the bits for a different index j). So you can use a better method of combining the probability of the individual "bad events".
"Not using the Union Bound" is a very vague hint I know. here's a bit more info:
I hope the stuff above helps. If not, I will be lenient with my marking, because of my initial mistake, and even if you use the Union Bound you'll get a few marks.
Hint: Haven't really had many questions on this one. But as a hint, the second part requires the use of Chernoff Bounds. And also, the finding "of some tournament" is not as big a deal as you would think.
Hint: Again, not many questions on this one. If you are struggling to understand how the Markov chain changes the "current contingency table", and how we can move between tables, a good idea first step is to look at that example 3x3 table at the end of lecture slides 14 (slides, slides-by-4), and see how you can change the table with steps of the Markov chain.
Informatics Forum, 10 Crichton Street, Edinburgh, EH8 9AB, Scotland, UK
Tel: +44 131 651 5661, Fax: +44 131 651 1426, E-mail: school-office@inf.ed.ac.uk Please contact our webadmin with any comments or corrections. Logging and Cookies Unless explicitly stated otherwise, all material is copyright © The University of Edinburgh |