How to do basic causal inference for two random variables Suppose that we have two random variables $X$ and $Y$. Is it possible to detect the dependency $Y = f(X)$ for some arbitrary $f$? Is there a way of quantifying if $Y$ is "nearly equal" to $f(X)$?
I think this is to do with mutual information. I'm not quit clear on the exact relationship. It might be the mutual information is this measure I'm after. There's a measure called the rand-index, which seems to measure when it is simultaneously that case that $Y=f(X)$, $X=f(Y)$
Edit: The particular case I'm interested in has $X$ and $Y$ discrete (with a discrete - but large sample space) though I am also interested in infinite countable sample and value spaces (sequences of characters in particular).
 A: 
How to do basic causal inference for two random variables?

If your data is indexed by time, then you might consider Granger causality as has been suggested. Two of the commonly applied statistical frameworks of causal inference today are the Neyman-Rubin causal model and Judea Pearl's causality. There is a less well-known technique called "convergent cross-mapping" that attempts to reconstruct a latent state space assuming an attractor, however I will leave this topic aside.
One thing that both of these frameworks agree upon is the importance of intervention (i.e. performing a manipulation or experiment). They also both retrospectively justify the historical use of controls in experiments.
Very few systems have only two variables to consider, but we can still use the interventionist view. We have three options:

*

*$X$ and $Y$ are causally unrelated

*$X$ causes $Y$

*$X$ is caused by $Y$
When I say "$X$ causes $Y$", what does that mean? It means that if we manipulate a change in $X$, that will result in a change in $Y$. The manipulation part is important because it is what distinguishes associational inferences from causal ones in this context.
So, to learn about causality between two variables, run experiments where you manipulate one and look for a response in the other. This is partly why design of experiments is important.

Is it possible to detect the dependency $Y = f(X)$ for some arbitrary $f$?

Yes, there are many estimators of dependence between two random variables, including functions of random variables. As mentioned above, you could use mutual information. There are other estimators of specific types of dependence such as correlation, but for any estimator you use you must be mindful of its assumptions. Before touching any estimators, I would recommend plotting the scatter plot between the variables to 'see' if there is anything potentially going on.

Is there a way of quantifying if  is "nearly equal" to ()?

Yes, there are many. Some straightforward functions are residual sum of squares, mean squared error, root-mean-square error, and mean absolute error. Somewhat more abstractly, you can consider any loss function to be an estimator of how closely $Y = f(X)$, which can include information-theoretic estimators such as KLD and JSD.

I think this is to do with mutual information. I'm not quit clear on the exact relationship.

The relationship is provable, although it requires some background in probability theory and information theory. Simply put
$$\text{MI}(X,Y) = 0 \iff X \perp \!\!\! \perp Y$$
which is to say that mutual information is always zero whenever the two variables are mutually independent, and vice versa.

There's a measure called the rand-index, which seems to measure when it is simultaneously that case that $Y=f(X)$, $X=f(Y)$

The Rand index is suited to the use case where you can compute either a confusion matrix or a contingency table because it takes in finite count measures. The main area that I've seen the Rand index applied is in assessing the accuracy of clustering algorithms. If there variables you are dealing with are continuous, you can either attempt to bin your variables into histograms (which comes with binning error) or you can use an estimator other than the Rand index.

Footnote: @Alexis provided a citation to an additional framework of causal inference that appears to work outside a counterfactual frame. See Puccia, C. J., & Levins, R. (1986). Qualitative Modeling of Complex Systems: An Introduction to Loop Analysis and Time Averaging (C. J. Puccia & R. Levins, Eds.). Harvard University Press.

