Sorry, I meant $q_{1i}$, the $i$-th entry of the largest eigenvector $q_1$. The question is now edited.

I don't understand your comment very well, but that's probably because my question wasn't clear in the first place. I hope my comments above made it more clear...

@Douglas: I should have given this more thought, but for now I think we can just define $X_t$ to be 0 when $S(t) = 0$.

Also, the $s(t)$ is a mistake, it should be $S(t)$.

And the O(1/S(t)) bound follows immediately from the above definition.

I apologize for the confusion. Let me try to give a more formal definition: suppose the data is a sequence of tuples $(R_1, Y_1), (R_2, Y_2),...,(R_T, Y_T)$, with $Y_t \sim Ber(p)$ (this determines if an $R_t$ is "activated") and the $R_t$ are iid in $[0,1]$ with expectation $E(R)$ (so yes, @Brendan, the $R_t$ are bounded, I should have mentioned that). Let $S(t) = \sum_{i \leq t} Y_i$ and let $X_t = (\sum_{i \leq t : Y_i = 1} R_t) / S(t)$. So I have a sequence of means $X_t$, each with expectation $E(R)$, hence the expectation of the sum is $TE(R)$.

It's not clear to me that $p$ is redundant, because if an $R_t$ is not "activated" with probability $p$, then it is not counted in $X_t$. Also, I don't see how Azuma's inequality would apply, because the $X_t$ are not a martingale (as far as I can tell).

Oh, and by extra linear constraints I mean additional constraints of the form $c_i(x) \geq 0$, $d_i(y) \geq 0$, $e_i(x) = 0$, $f_i(y) = 0$, where $c,d,e,f$ are linear. These are in addition to the bilinear constraints $y^T x = 0$.

Thanks Gilead. Unfortunately I can't just assume that $u_{ij} \geq 0$. There is a way to reformulate this problem so that $u_{ij} \geq 0$, but then the bilinear constraints would become $u_{ij}^T \lambda_i = \alpha_{ij}$ for some $\alpha_{ij} \geq 0$, and this would no longer be a complementarity problem. I'm not sure if that formulation would be easier. Alos, I understand NPC != unsolvable, but I am trying to understand the complexity of the problem these equations encode. So I am looking either for a polytime algorithm or an NPC proof.