User shiva kaul - MathOverflow

Answer by Shiva Kaul for Concentration of Measure for Power Law

2010-08-01T23:08:28Z

This topic is examined by Olivier Catoni in his recent paper: High confidence estimates of the mean of heavy-tailed real random variables. Denote the mean, variance and kurtosis of your distribution by $m$, $v$ and $\kappa$, respectively. Then, by Catoni's proposition 7.1, the following holds with probability at least $1-2\epsilon$: $$\frac{|(\frac{1}{n}\sum_{i=1}^n X_i) - m|}{\sqrt{v}} \leq \frac{2\log (\frac{3}{2}\epsilon^-1)\sqrt{\kappa}}{5n} + \sqrt{\frac{2\log (\frac{3}{2}\epsilon^-1)}{n}} + \left(\frac{3\kappa}{2\epsilon n^3}\right)^{1/4}\left(1 + \frac{3^5(n-1)\log (\frac{3}{2}\epsilon^-1)^2\kappa}{2500n^2} + \frac{12\sqrt{2}\log(\frac{3}{2}\epsilon^-1)^{3/2}\sqrt{\kappa}}{25n^{3/2}}\right)^{1/4}$$ There is no mention of boundedness but of course you will want to check his proof.

Are you using the empirical average as an estimate of the mean? If so, you may prefer Catoni's estimator, which is conceptually similar to the truncation trick described in Tao's notes. The raw empirical average performs poorly because a single $X_i$ can throw it wildly off course. Instead, blunt the incoming $X_i$'s and use them to update a guess of $m$. Of course, an initial guess is needed, so the scheme is naturally iterative.

Answer by Shiva Kaul for Correlation and Causation. When can we believe correlation (reasonably, at least) imply causation

2010-04-25T08:08:26Z

Learning causal relationships (i.e. a directed acyclic graph where "$A \to B$ means $A$ causes $B$") from observational data is a kind of causal inference. In general, it is not possible. However, the following two conditions, phrased in the terminology of graphical models, are sufficient for models without confounding variables.

Causal Markov assumption: each node is conditionally independent of its non-effects, direct or otherwise, given its direct causes (i.e. parents).
Faithfulness: the only conditional independencies in the true distribution arise from d-separation in the true causal DAG.

Judea Pearl, Clark Glymour, and Peter Spirtes have done excellent work in this area. Since you are asking your question on MO, you are presumably interested in mathematically-oriented discussion, such as the one in Koller and Friedman's Probabilistic Graphical Models.

Answer by Shiva Kaul for Polish spaces in probability

2010-04-10T17:05:42Z

Separability is a key technical property used to avoid measure-theoretic difficulties for processes with uncountable index sets. The general problem is that measures are only countably additive and $\sigma$-algebras are closed under only countably many primitive set operations. In a variety of scenarios, uncountable collections of measure zero events can bite you; separability ensures you can use a countable sequence as a proxy for the entire process without losing probabilistic content. Here are two examples.

Weak convergence: the classical theory of weak convergence utilizes Borel-measurable maps. When dealing with some function-valued random elements, such as cadlag functions endowed with the supremum norm, Borel-measurability fails to hold. See the motivation for Weak Convergence and Empirical Processes. The $J1$ topology is basically a hack which ensures the function space is separable and thereby avoids measurability issues. The parallel theory of weak convergence described in the book embraces non-measurability.
Existence of stochastic processes with nice properties: a key property of Brownian motion is continuity of the sample paths. Continuity, however, is a property involving uncountably many indices. The existence of a continuous version of a process can be ensured with separable modifications. See this lecture and the one that follows.

Metrizability allows us to introduce concepts such as convergence in probability. Completeness (the Cauchy convergence kind, not the null subsets kind) makes it easier to conduct analysis.

Answer by Shiva Kaul for What is the probabilistic counterpart of weighted K-Means

2010-03-24T15:15:26Z

pKNN+AL (Jain and Kapoor, 2009) is a probabilistic modification of the KNN classifier. Given a set of points ${x_1, \ldots, x_n}$ from $\mathbb{R}^d$, labels ${y_1, \ldots, y_n}$ from $[1,C]$, and a Mercer kernel $K$, the probability of $x$ belonging to class $c$ is

$$\frac{\frac{1}{n_c} \sum_{\{i : y_i = c\}} K(x, x_i)}{\sum_{t=1}^C \frac{1}{n_t} \sum_{\{i : y_i = c\}} K(x, x_i)}$$

where $n_c$ is the number of $x_i$ that belong to class $c$. It is also an active learning algorithm and comes with a MATLAB implementation.

Answer by Shiva Kaul for Minimum Hamming Distance Distribution in a Random Subset of Binary Vectors+

2010-03-03T04:33:15Z

Here is a direct application of Theorem 21 from Gabor Lugosi's concentration of measure notes. Your $Y_i$ corresponds to his $X_{i,1}^m$ and your $X_{i,j}$ to his $d(X_{i,1}^m, X_{j,1}^m)$. Take his $A$ to be your $\{X_{i,j}\}_{i \neq j}$. The birthday problem gives the probability that any two of the $Y_i$ are exactly the same. That is: $$\mathbb{P}(0^m \in A) = \mathbb{P}\left(\left\{X_{i,j} = 0^m : i \neq j\right\}\right) = \mathrm{(omitted\ for\ simplicity)} $$ Now your $D_{min}$ corresponds to his $d(0^m,A)$. By the Theorem, for any $t > 0$, $$\mathbb{P}\left(D_{min} \geq t + \sqrt{\frac{m}{2} \mathrm{log}\frac{1}{\mathbb{P}(0^m \in A)}}\right) \leq e^{-2t^2/m}.$$ This bound may be OK for your needs. If it isn't, see Lugosi's discussion of Talagrand's convex distance inequality, which is a big improvement.

Answer by Shiva Kaul for Notions of "independent" and "uncorrelated" for subsets of the natural numbers

2010-02-17T00:04:26Z

Independence has nothing to do with the uniform distribution. It is extremely common to define an infinite sequence of measures whose joint measure is the product measure. It is also common to define finite-dimensional distributions and then use an extension theorem (Daniell-Kolmogorov, Ionescu Tulcea, etc.) to prove the existence of a (unique) measure on the infinite product space.

Comment by Shiva Kaul

2010-08-02T09:45:20Z

That is great for $m \ll n$ since those matrices satisfy the restricted isometry property. I can't see why that would be a good idea for $m \approx n$.

Comment by Shiva Kaul

2010-07-30T00:34:44Z

Hi Mark: if $p=2$ it sounds like this method won't place measure to non-orthogonal matrices. (A density would be nice, too.)

Comment by Shiva Kaul

2010-07-30T00:18:57Z

Yes, that is correct. By 'supported' I mean the set I specified should be a subset of the support, though equality would be nifty. $p=2$ is fine.

Comment by Shiva Kaul

2010-07-29T21:34:49Z

$m \leq n$ but not $m \ll n$.

Comment by Shiva Kaul

2010-07-13T04:53:09Z

There's a reason for that. The basics of statistics don't require measure theory; they're hampered by it. Anyway, Schervish's "Theory of Statistics" may be up your alley.

Comment by Shiva Kaul

2010-04-26T05:27:41Z

Steven Rudich is also a good person to ask. He used to begin his undergraduate discrete math / theoretical computer science course with magic tricks. cs.cmu.edu/~rudich/magic

Comment by Shiva Kaul

2010-04-21T18:55:26Z

This question borders on philosophy. clusteringtheory.org