The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
94 views

Strong Dependence

I asked this question on MO, but no answer. I don't know if this definition has been already given. Suppose $X$ and $Y$ are two random variables over finite alphabets $\mathcal{X}$ and ...
7
votes
2answers
223 views

Maximizing the number of heads in $N$ tosses by choosing which coin to toss

Assume you have two coins $A,B$ with biases $P_A,P_B$ respectively. We would like to make $N$ coin tosses and get the maximal number of heads possible. Unfortunately, we know $P_B$, but $P_A$ is ...
0
votes
0answers
27 views

What's the meaning of the class indicator matrix when transforming the class label matrix into it in canonical correlation analysis?

When using canonical correlation analysis (CCA), we can integrate the dataset and label information via transforming the class label matrix Y into the class indicator matrix T. Such as: $T = ...
6
votes
1answer
202 views

Proof Haar matrices satisfy JL lemma

The Johnson-Lindenstrauss lemma says roughly that for any collection $S$ of $n$ points in $\mathbb{R}^d$, there exists a linear map $f:\mathbb{R}^d \rightarrow \mathbb{R}^k$ where $k = O(\log ...
3
votes
0answers
110 views

Practical Implications of Kolmogorov's Result on the Universal Approximation Theorem with Neural Networks

After having read matus's beautiful answer in this thread explaining (among other things) Kolmogorov's result regarding the Universal Approximation Theorem with Neural Networks, I wonder: if just ...
2
votes
0answers
141 views

Expected probability of error in Vapnik's book

In Vapnik's book "Statistical Learning Theory", Theorem 10.5 states that - for a Support Vector Machine - the expected probability of error (of the optimal hyperplane) is upper bounded by $1/(l+1)$ ...
14
votes
2answers
229 views

Theoretical guarantees for running times of belief propagation methods?

Belief propagation has been shown to be a very powerful method through research in probabilistic graphical models. However, I don't know anything about BP that's comparable to MCMC methods where we ...
8
votes
4answers
434 views

Lower bound for testing closeness in $L_2$ norm?

I was wondering if there was any lower bound (in terms of sample complexity) known for the following problem: Given sample oracle access to two unknown distributions $D_1$, $D_2$ on $\{1,\dots,n\}$, ...
4
votes
1answer
350 views

What happens if you minimize $D_{KL}(P_{parameters} || P_{data})$ under the Kullback-Leibler divergence?

If $D_{KL}$ is the Kullback-Leibler divergence, minimizing $D_{KL}(P_{data}||P_{parameters})$ performs maximum likelihood estimation of the parameters. What happens if you minimize ...
1
vote
1answer
187 views

How to choose a correct prior

Consider a Bernoulli experiment, such as flipping a not necessarily fair coin, which results in a positive outcome (heads) with probability $p$ and with a negative outcome (tails) with probability ...
0
votes
3answers
285 views

Algorithm Suggestion for Scoring System - weighted solution

I'm trying to validate a series of words that are provided by users. I'm trying to come up with a scoring system that will determine the likelihood that the series of words are indeed valid words. ...
4
votes
1answer
322 views

Streaming Algorithms: Motivations for estimating frequency moments

The celebrated AMS paper "The space complexity of approximating the frequency moments" defines the problem as following: Let $a_1, a_2,\dotsc, a_m$ be a sequence of integers where each $a_j \in ...
1
vote
0answers
37 views

Lower bounds for minimum variance estimators in limited space

Cramer-Rao, Rao-Blackwell and Lehmann-Scheffé, all give you ways to prove that a statistical estimator has the lowest variance possible. Is there any CS related work on the minimum variance ...
3
votes
1answer
270 views

Estimator for sum of independent and identically distributed (iid) variables

This is a repost of a question at math.stackexchange, but I was told by a reliable source that people around here might be able to help me, so I thought I'd give it a shot. Consider the Chernoff ...
1
vote
0answers
118 views

Distribution of number of unique items in a sample

Suppose we're sampling a discrete random variable from a distribution f, n times. Is there a simple analytical formulation for the expected number of unique items we obtain, or for the distribution of ...
10
votes
1answer
330 views

Distinguishing between $N$ quantum states

Given a quantum state $\rho_A$ chosen uniformly at random from a set of $N$ mixed states $\rho_1 ... \rho_N$, what is the maximum average probability of correctly identifying $A$? This problem can be ...
4
votes
2answers
439 views

Is analogy between database and probability concepts legitimate?

In Relational Databases: Tutorial for Statisticians Joe R. Hill casts probability view onto database theory. In Table 1 the author summarized the parallels between the two disciplines, describing ...
1
vote
0answers
102 views

High Dimensional Volume (HDV) estimator for Entropy estimation

I am writing a program using high-dimensional volume (HDV) estimator to estimate entropy and mutual information for variable selection. Let $ D = (x^i_1, x^i_2, ..., x^i_M)$, N is the number of data ...
4
votes
2answers
1k views

Multiplication of normal distributions

Suppose X_1, ..., X_k are iid standard Gaussian variables, for some k > 1. Then, what is the distribution of X := X_1 * ... * X_k ? Can it be approximated by a Gaussian, maybe for large k ?
-2
votes
1answer
345 views

Distributing items randomly into groups of equal size

Given n items (20% type A, 80% type B), I'm looking for a way to distribute them randomly into g groups of equal size. It must be possible for one group to end up with As in the majority but it must ...
23
votes
1answer
642 views

Estimating a percentile among distributed nodes without revealing values

I have a fairly unique problem to solve and I am hoping somebody here can give me some insight into how to best tackle it. Problem: Suppose a list of N numbers is shared among a set of participants ...
4
votes
1answer
125 views

Measures of “correlation” between two orderings

An easy question perhaps? Taking a (fictional) concrete example, let's say I have two ranking methods for HTML documents: PageRank and HITS. I derive an ordered list over the same set of documents ...
2
votes
2answers
316 views

Generate a sequence of numbers

I want to generate an infinite sequence of numbers between $0$ and $9$ such that the percentage of number $i$ appearing in the sequence is $p_i$. Let $p=\lbrace p_0,...,p_9\rbrace$. Another agent $B$ ...
0
votes
1answer
132 views

Analysis of variables of varying numbers

i work with amino acid sequences and i want to use a selfmade model to tell me something about it, lets call it f(seq). Now i want to know the contribution of every position in the sequence onto the ...
7
votes
2answers
477 views

What subjects, topics does a computer science graduate need to learn to apply available machine learning frameworks, esp. SVMs

I want to teach myself enough machine learning so that I can, to begin with, understand enough to put to use available open source ML frameworks that will allow me to do things like: Go through the ...
8
votes
1answer
214 views

Circuit complexity and statistical tests

A few years ago, I took a class on complexity theory from Steven Rudich, and I remember him giving an interesting lecture connecting statistical tests (as found in statistics departments!) with ...
1
vote
1answer
234 views

Constraint Satisfaction Problem: Choosing real numbers with certain characteristics

I have a set of n real numbers. I also have a set of functions, f_1, f_2, ..., f_m. Each of these functions takes a list of numbers as its argument. I also have ...
6
votes
0answers
140 views

Constraint Satisfaction Problem: Choosing real numbers with variance in a certain range

I have a set of n real numbers. I want to repeatedly choose subsets of k elements such that the variance of these k numbers falls within some specified range, r = [l, u]. Moreover I want to do this ...
8
votes
2answers
312 views

complexity of fitting models to data

Suppose $f:\mathbf{R}\times \mathbf{R} \to \mathbf{R}$ is some some continuous function $x_1 \ldots x_n$ is a set of real values, and we'd like to compute $\text{argmin}_a \sum_i f(a,x_i)$ to ...