How do I test that two continuous variables are independent? Suppose I have a sample $(X_n,Y_n), n=1..N$ from the joint distribution of $X$ and $Y$. How do I test the hypothesis that $X$ and $Y$ are independent? 
No assumption is made on the joint or marginal distribution laws of $X$ and $Y$ (least of all joint normality, since in that case independence is identical to correlation being $0$).
No assumption is made on the nature of a possible relationship between $X$ and $Y$; it may be non-linear, so the variables are uncorrelated ($r=0$) but highly co-dependent ($I=H$).
I can see two approaches:


*

*Bin both variables and use Fisher's exact test or G-test.


*

*Pro: use well-established statistical tests

*Con: depends on binning


*Estimate the dependency of $X$ and $Y$: $\frac{I(X;Y)}{H(X,Y)}$ (this is $0$ for independent $X$ and $Y$ and $1$ when they completely determine each other).


*

*Pro: produces a number with a clear theoretical meaning

*Con: depends on the approximate entropy computation (i.e., binning again)



Do these approaches make sense?
What other methods people use?
 A: How about this paper: 
http://arxiv.org/pdf/0803.4101.pdf
"Measuring and testing dependence by correlation of distances". Székely and Bakirov always have interesting stuff. 
There is matlab code for the implementation:
http://www.mathworks.com/matlabcentral/fileexchange/39905-distance-correlation
If you find any other (simple to implement) test for independence let us know. 
A: The link between Distance Covariance and kernel tests (based on the Hilbert-Schmidt independence criterion) is given in the paper:
Sejdinovic, D., Sriperumbudur, B., Gretton, A., and Fukumizu, K., Equivalence of distance-based and RKHS-based statistics in hypothesis testing, Annals of Statistics, 41 (5), pp.2263-2702, 2013
It's shown that distance covariance is a special case of the kernel statistic, for a particular family of kernels.
If you're intent on using mutual information, a test based on a binned estimate of the MI is:
Gretton, A. and Gyorfi, L., Consistent Nonparametric Tests of Independence, Journal of Machine Learning Research, 11 , pp.1391--1423, 2010.
If you're interested in getting the best test power, you're better off using the kernel tests, rather than binning and mutual information.
That said, given your variables are univariate, classical nonparametric independence tests like Hoeffding's are probably fine.
A: Rarely (never?) in statistics can you demonstrate that your sample statistic = a point value. You can test against point values and either exclude them or not exclude them. But the nature of statistics is that it is about examining variable data. Because there is always variance then there will necessarily be no way to know that something is exactly not related, normal, gaussian, etc. You can only know a range of values for it. You could know if a value is excluded from the range of plausible values. For example, it's easy to exclude no relationship and give range of values for how big the relationship is.
Therefore, trying to demonstrate no relationship, essentially the point value of relationship = 0 is not going to meet with success. If you have a range of measures of relationship that are acceptable as approximately 0. Then it would be possible to devise a test.
Assuming that you can accept that limitation it would be helpful to people trying to assist you to provide a scatterplot with a lowess curve. Since you're looking for R solutions try:
scatter.smooth(x, y)

Based on the limited information you've given so far I think a generalized additive model might be the best thing for testing non-independence. If you plot that with CI's around the predicted values you may be able to make statements about a belief of independence. Check out gam in the mgcv package. The help is quite good and there is assistance here regarding the CI.
A: This is a very hard problem in general, though your variables are apparently only 1d so that helps. Of course, the first step (when possible) should be to plot the data and see if anything pops out at you; you're in 2d so this should be easy.
Here are a few approaches that work in $\mathbb{R}^n$ or even more general settings:


*

*As you mentioned, estimate mutual information via entropies. This may be your best option; nearest neighbor-based estimators do okay in low dimensions, and even histograms aren't terrible in 2d. If you're worried about estimation error, this estimator is simple and gives you finite-sample bounds (most others only prove asymptotic properties):

Sricharan, Raich, and Hero. Empirical estimation of entropy functionals with confidence. arXiv:1012.4188 [math.ST]

Alternatively, there are similar direct estimators for mutual information, e.g.

Pál, Póczos, and Svepesári. Estimation of Rényi Entropy and Mutual Information Based on Generalized Nearest-Neighbor Graphs, NIPS 2010.


*The Hilbert-Schmidt independence criterion: a kernel (in the sense of RKHS, not KDE)-based approach.

Gretton, Bousqet, Smola, and Schölkopf, Measuring Statistical Independence with Hilbert-Schmidt Norms, Algorithmic Learning Theory 2005.


*The Schweizer-Wolff approach: based on copula transformations, and so is invariant to monotone increasing transformations. I'm not very familiar with this one, but I think it's computationally simpler but also maybe less powerful.

Schweizer and Wolff, On Nonparametric Measures of Dependence for Random Variables, Annals of Statistics 1981.

A: Hoeffding developed a general nonparametric test for the independence of two continuous variables using joint ranks to test $H_{0}: H(x,y) = F(x)G(y)$.  This 1948 test is implemented in the R Hmisc package's hoeffd function.
A: It may be interesting ...
Garcia, J. E.; Gonzalez-Lopez, V. A. (2014)
Independence tests for continuous random variables based on the longest increasing subsequence. Journal of Multivariate Analysis, v. 127 p. 126-146. 
http://www.sciencedirect.com/science/article/pii/S0047259X14000335
A: Yet another approach is Constrained Covariance: basically, for a "sufficiently rich" function class $G$, Constrained Covariance of two random variables $X$ and $Y$ is
$$ \text{CoCo}(X,Y)=\sup_{g_1,g_2\in G} \text{corr}(g_1(X),g_2(Y)) $$
(possibly related to another answer)
As for the computational aspect, please see Safe, Anytime-Valid Inference (SAVI) and Game-theoretic Statistics
(I am omitting the details because they are being published now)
