User shiva kaul - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T16:44:07Z http://mathoverflow.net/feeds/user/1656 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/28899/concentration-of-measure-for-power-law/34168#34168 Answer by Shiva Kaul for Concentration of Measure for Power Law Shiva Kaul 2010-08-01T23:08:28Z 2010-08-01T23:08:28Z <p>This topic is examined by Olivier Catoni in his recent paper: <a href="http://arxiv.org/abs/0909.5366v1" rel="nofollow">High confidence estimates of the mean of heavy-tailed real random variables</a>. 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.</p> <p>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.</p> http://mathoverflow.net/questions/22490/correlation-and-causation-when-can-we-believe-correlation-reasonably-at-least/22494#22494 Answer by Shiva Kaul for Correlation and Causation. When can we believe correlation (reasonably, at least) imply causation Shiva Kaul 2010-04-25T08:08:26Z 2010-04-26T05:21:32Z <p>Learning causal relationships (i.e. a directed acyclic graph where "$A \to B$ means $A$ causes $B$") from observational data is a kind of <i>causal inference</i>. In general, it is not possible. However, the following two conditions, phrased in the terminology of <a href="http://en.wikipedia.org/wiki/Bayesian_network" rel="nofollow">graphical models</a>, are sufficient for models without confounding variables.</p> <ul> <li>Causal Markov assumption: each node is conditionally independent of its non-effects, direct or otherwise, given its direct causes (i.e. parents). <li>Faithfulness: the only conditional independencies in the true distribution arise from d-separation in the true causal DAG. </ul> <p>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 <a href="http://books.google.com/books?id=7dzpHCHzNQ4C&amp;lpg=PA2&amp;dq=structured%20probabilistic%20models&amp;pg=PA1009#v=onepage&amp;q=structured%20probabilistic%20models&amp;f=false" rel="nofollow">Probabilistic Graphical Models</a>.</p> http://mathoverflow.net/questions/20919/polish-spaces-in-probability/20937#20937 Answer by Shiva Kaul for Polish spaces in probability Shiva Kaul 2010-04-10T17:05:42Z 2010-04-10T17:05:42Z <p>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.</p> <ol> <li><p>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 <a href="http://books.google.com/books?id=OCenCW9qmp4C&amp;lpg=PP1&amp;dq=weak%20convergence%20empirical%20processes&amp;pg=PA3#v=onepage&amp;q&amp;f=false" rel="nofollow">motivation</a> for <i>Weak Convergence and Empirical Processes</i>. 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.</p></li> <li><p>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 <a href="http://www.stat.cmu.edu/~cshalizi/754/notes/lecture-07.pdf" rel="nofollow">this lecture</a> and the one that follows. </p></li> </ol> <p>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.</p> http://mathoverflow.net/questions/19184/what-is-the-probabilistic-counterpart-of-weighted-k-means/19200#19200 Answer by Shiva Kaul for What is the probabilistic counterpart of weighted K-Means Shiva Kaul 2010-03-24T15:15:26Z 2010-03-24T15:15:26Z <p><a href="http://research.microsoft.com/en-us/um/people/akapoor/papers/cvpr2009_active.pdf" rel="nofollow">pKNN+AL</a> (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 </p> <p>$$\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)}$$</p> <p>where $n_c$ is the number of $x_i$ that belong to class $c$. It is also an <a href="http://en.wikipedia.org/wiki/Supervised_learning#Active_Learning" rel="nofollow">active learning</a> algorithm and comes with a <a href="http://research.microsoft.com/en-us/um/people/akapoor/cvpr2009/" rel="nofollow">MATLAB implementation</a>.</p> http://mathoverflow.net/questions/16359/minimum-hamming-distance-distribution-in-a-random-subset-of-binary-vectors/16955#16955 Answer by Shiva Kaul for Minimum Hamming Distance Distribution in a Random Subset of Binary Vectors+ Shiva Kaul 2010-03-03T04:33:15Z 2010-03-03T04:33:15Z <p>Here is a direct application of Theorem 21 from Gabor Lugosi's <a href="http://www.econ.upf.edu/~lugosi/anu.pdf" rel="nofollow">concentration of measure notes</a>. 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.</p> http://mathoverflow.net/questions/15508/notions-of-independent-and-uncorrelated-for-subsets-of-the-natural-numbers/15513#15513 Answer by Shiva Kaul for Notions of "independent" and "uncorrelated" for subsets of the natural numbers Shiva Kaul 2010-02-17T00:04:26Z 2010-02-17T00:09:59Z <p>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, <a href="http://www.stat.cmu.edu/~cshalizi/754/notes/lecture-03.pdf" rel="nofollow">Ionescu Tulcea</a>, etc.) to prove the existence of a (unique) measure on the infinite product space. </p> http://mathoverflow.net/questions/33742/random-matrix-distribution-preferring-orthogonal-small-norm-rows Comment by Shiva Kaul Shiva Kaul 2010-08-02T09:45:20Z 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$. http://mathoverflow.net/questions/33742/random-matrix-distribution-preferring-orthogonal-small-norm-rows/33871#33871 Comment by Shiva Kaul Shiva Kaul 2010-07-30T00:34:44Z 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.) http://mathoverflow.net/questions/33742/random-matrix-distribution-preferring-orthogonal-small-norm-rows Comment by Shiva Kaul Shiva Kaul 2010-07-30T00:18:57Z 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. http://mathoverflow.net/questions/33742/random-matrix-distribution-preferring-orthogonal-small-norm-rows Comment by Shiva Kaul Shiva Kaul 2010-07-29T21:34:49Z 2010-07-29T21:34:49Z $m \leq n$ but not $m \ll n$. http://mathoverflow.net/questions/31655/statistics-for-mathematicians Comment by Shiva Kaul Shiva Kaul 2010-07-13T04:53:09Z 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 &quot;Theory of Statistics&quot; may be up your alley. http://mathoverflow.net/questions/9754/magic-trick-based-on-deep-mathematics Comment by Shiva Kaul Shiva Kaul 2010-04-26T05:27:41Z 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. <a href="http://www.cs.cmu.edu/~rudich/magic/" rel="nofollow">cs.cmu.edu/~rudich/magic</a> http://mathoverflow.net/questions/22081/how-to-compare-two-cluster-solutions Comment by Shiva Kaul Shiva Kaul 2010-04-21T18:55:26Z 2010-04-21T18:55:26Z This question borders on philosophy. <a href="http://clusteringtheory.org/" rel="nofollow">clusteringtheory.org</a>