0
$\begingroup$

Let $X_1,X_2, \dots, X_{m_1}$, $Y_1,Y_2, \dots, Y_{m_2}$ be $m_1 + m_2$ independent random variables from a probabilistic space $\mathcal{X}$, let $h: \mathcal{X} \to \{-1,1\}$

I'm interested in point estimation: $\mu = \underset{x,y \sim \mathcal{D}}{\mathbb{E}}[h(x)h(y)]$.

The estimation takes the form $\hat{\mu} = \frac{1}{m_1m_2} \sum_{i=1}^{m_1} \sum_{j=1}^{m_2} h(X_i) h(Y_j)$

Is there a generalized Hoeffding inequality to measure concentration for this (Two-sample U-statistic) setting?

Improve this question
$\endgroup$
2
  • $\begingroup$ Hoeffding just requires bounds on the summands, so couldn't you use the fact that $h(X_i)h(X_j) \in [-1, 1]$ by definition? Or are you looking for something more specific than a bound of the form $P(\hat{\mu} - \mu > \varepsilon)$? $\endgroup$
    – chang_trenton
    Commented Jun 27 at 5:32
  • $\begingroup$ @chang_trenton I'm looking for a tight upper bound for $\mathbb{P}[|\hat{\mu} - \mu| \leq \epsilon ]$ $\endgroup$
    – Saginus
    Commented Jun 27 at 8:48

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.