I am trying to figure out how to answer 1.1.c from here http://www.cc.gatech.edu/sites/default/files/images/200808_cse_qualifier.pdf. The problem setup is as follows enter image description here

We are then asked to show enter image description here

An earlier problem had us show that the maximizing ranking is in descending order of $y$ values. My intuition is that in expectation, if $y_i>y_j$, then in expectation, $p(y_i|x_i)>p(y_i|x_j)$, so that (with a big hand wave) in expectation $R(x_i)>R(x_j)$, but I'm having a hard time formalizing that or saying much about the other terms in the summation.


A friend showed me how to answer this. The expectation, using independence assumptions and marginalization arguments, is given by \begin{align} \sum_{y_1}\sum_{y_2}\cdots\sum_{y_n}(c_1 y_{\sigma_1}+\cdots+c_n y_{\sigma_n})&p(y_1,\cdots,y_n|x_1,\cdots,x_n)\\ &=c_1\sum_{y}y_{\sigma_1}p(y_{\sigma_1}|x_{\sigma_1})+\cdots +c_n\sum_{y}y_{\sigma_n}p(y_{\sigma_n}|x_{\sigma_n})\\ \end{align}

using the descending order of $R(x)$'s will give us the max based on the previous problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.