Questions tagged [pr.probability]

Questions in probability theory

Filter by
Sorted by
Tagged with
22
votes
3answers
2k views

Number of distinct nodes in a random walk

Commute time in a connected graph $G=(V,E)$ is defined as the expected number of steps in a random walk starting at $i$, before node $j$ is visited and then node $i$ is reached again. It is basically ...
1
vote
2answers
1k views

question about probability ranking principle

I am studying IR and I am not clearly understand "probability ranking principle" ( I tried to google the definition, but i couldn't find clear answer.) I am assuming that it's system which ...
7
votes
1answer
345 views

expected number of sets generated by greedy set cover ?

I see most of the analysis for the greedy set cover analyses the approximation ratio. However, assume that each element in $T$ belong with a constant probability to one of the sets of $S$ (where $S = \...
7
votes
0answers
182 views

Testing the degree of a vertex

Let's say we have a graph $G$ with $n$ vertices. Given $\epsilon>0$ and a specific vertex $v$, consider the problem of deciding whether $\mathrm{deg}(v) < \frac{\epsilon}{3}n$ or $\mathrm{deg}(v)...
9
votes
2answers
626 views

High probability events without low probability coordinates

Let $X$ be a random variable taking values in $\Sigma^n$ (for some large alphabet $\Sigma$), which has very high entropy - say, $H(X) \ge (n- \delta)\cdot\log|\Sigma|$ for an arbitrarily small ...
6
votes
0answers
187 views

Tree search guided by a probabilistic oracle

I'm trying to find a solution for the following problem. I have a tree $T$ of branching factor $b$ and depth $d$. For the moment, I only care about the case where I restrict $b=2$, but I would be ...
12
votes
1answer
1k views

Sampling from Multivariate Gaussian with Graph Laplacian (inverse) Covariance

We know from e.g. Koutis-Miller-Peng (based on work of Spielman & Teng), that we can very quickly solve linear systems $A x = b$ for matrices $A$ that are the graph Laplacian matrix for some ...
11
votes
0answers
391 views

Cheeger's inequality for directed graphs?

Cheeger's inequality can be used to relate the size of the worst cut in the graph to the eigenvalue gap of a simple random walk on that graph. I am wondering if it possible to extend this result to ...
1
vote
0answers
242 views

application for the Kchinchine inequality in Computer Science

The classical Kchinchine inequality states that for vector $a=(a_1, \ldots, a_{2m})\in R^{2m}$, for $p\geq 2$, and for independent Rademacher random variables $r_1, \ldots, r_{2m}$, one has $$ E(|\...
13
votes
2answers
387 views

What's the bias of random polynomials with low degree over GF(2)?

I have a question concerning low-degree polynomials and probability: What is the (assyptotic behavior of the) probability that a random* polynomial, $p$, over GF(2), with degree $\le d$ and n ...
9
votes
1answer
322 views

Cover time and spectral gap for reversible random walks

I am looking for a theorem which say something like this: if the cover time of a reversible Markov chain is small, then the spectral gap is large. Here the spectral gap means $1-|\lambda_2|$, that is, ...
4
votes
0answers
126 views

Problem about machine scheduling [closed]

I am re-posting the problem https://mathoverflow.net/questions/92783/random-task-scheduling-problem here because I think people here are more familiar with this topic. Assume there are $m$ tasks, ...
14
votes
4answers
1k views

Throwing Balls into Bins, estimate a lowerbound of its probability

This is not a homework, though it looks like. Any reference is welcome. :-) Scenario: There are $n$ different balls and $n$ different bins (labled from 1 to $n$, from left to right). Each ball is ...
2
votes
1answer
252 views

Generate random permutation via iid uniforms — is inverse transformation possible?

A very common technique in the analysis of algorithms involving random permutations is to have each element $x$ select a rank $\rho(x)$ uniformly at random from the real interval $[0,1]$. The ...
-1
votes
1answer
86 views

Issue in understanding conditional likelihood for a producton rule

The Equation1 in paper in link explains how to assign probability to a production rule. Fig1 explains with an example. Now, I have a problem in understanding how to work with this formula since it ...
-2
votes
1answer
169 views

Dual of a Reversible Markov Chain [closed]

Let a reversible Markov process $m_{t+1}=m_t P$, where $t$ is time that has a stationary distribution $\pi$. I saw in a paper that the dual system was defined as $x_{t+1}=P x_t$. Can anyone give me ...
12
votes
6answers
747 views

Computing the approximate population of a bloom filter

Given a bloom filter of size N-bits and K hash functions, of which M-bits (where M <= N) of the filter are set. Is it possible to approximate the number of elements inserted into the bloom filter? ...
0
votes
1answer
271 views

is it by Chebychev's inequality? [closed]

Let x be random variables with mean zero and variance 1. Let n be natural number, t>0, C>0. Let also $P(x^2\geq n)\geq C/(n^t)$. Show, if $t\geq4$, then $P(x^2\geq n)\leq C/(n^2)$. I got so fare, ...
7
votes
3answers
1k views

Order of drawing colored balls from a bag

We're looking for an upper bound on (or a method to compute) probabilities of the following type: Suppose I put 12 yellow balls, 18 red balls, 7 white balls, and 2 green balls in a bag. Then I start ...
9
votes
3answers
541 views

Technical question about random walks

(My original question still has not been answered. I have added further clarifications.) When analyzing random walks (on undirected graphs) by viewing the random walk as a Markov chain, we require ...
11
votes
0answers
352 views

Is Bayesian updating computationally unfeasible?

Bayesian theory is a very popular theory of probabilities based upon a subjective framework of beliefs. However, subjects and beliefs have to be embodied, meaning to be feasible, it ought to be ...
6
votes
4answers
566 views

Small $\epsilon$-nets for points and half-planes without VC dimension

I have recently learned the proof of Haussler and Welzl of the following theorem. Theorem. Suppose we have a set system $\mathcal{F} \subseteq 2^X$, where $X$ is a finite set. Suppose $\mathcal{F}$ ...
2
votes
1answer
729 views

Avarage classes for PP (probabilistic polynomial time) and PPT machines running in expected polytime

i have some question concerning the class PP and PPT machines. 1) PP is defined as the class of problems $L$ for wich exist a probabilistic turing machine running in polytime with error probability &...
6
votes
3answers
1k views

Computational complexity of random sampling

I am using some randomized algorithms (particle filters) and I would like to know what is the computational complexity of obtaining one random sample of a continuous distribution (for instance from a ...
30
votes
2answers
1k views

Drunken birds vs drunken ants: random walks between two and three dimensions

It's well known that a random walk in the two dimensional grid will return to the origin with probability 1. It's also known that the same random walk in THREE dimensions has a probability strictly ...
5
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 ?
13
votes
3answers
2k views

An extension of Chernoff bound

I am looking for a reference (not a proof, that I can do) to the following extension of Chernoff. Let $X_1,..,X_n$ be Boolean random variables, not necessarily independent. Instead, it is guaranteed ...
2
votes
2answers
215 views

Reducing $n$ in $(n,k)$ secret sharing while keeping it effective

Assume Bob wants to share a secret with Alice. Assume he can only send messages using a one-sided channel which is insecure and unreliable. Unreliable, meaning: Alice only gets messages sent over this ...
3
votes
0answers
110 views

Sampling from a distribution with a given covariance matrix

Let $\bf X$ be a binary vector of $n$ (non-independent) random variables $X_1,\ldots, X_n$. Covariance of two random variables is defined as follows: $$\mathrm{cov}(X_i, X_j) = \mathrm{E}(X_i - \mu_i)...
-2
votes
1answer
469 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 ...
4
votes
0answers
157 views

Adding noise to an assignment

Suppose I'm given a CNF formula with $m$ clauses (and $k$ literals in each clause), with a total of $n$ variables in the formula, where each variable is in at most $c$ clauses, along with a satisfying ...
17
votes
1answer
577 views

Balls and Bins analysis in the m >> n regime.

It's well known that if you throw n balls into n bins, the most loaded bin is highly likely to have $O(\log n)$ balls in it. In general, one can ask about $m > n$ balls in $n$ bins. A paper from ...
32
votes
14answers
6k views

Book on Probability

While I have passed some courses on probability theory, both in the high school and the university, I have a hard time reading TCS papers when it comes to probability. It seems that the authors of ...
10
votes
4answers
481 views

Constructions better than a random one.

I am interested in examples of constructions in the complexity theory which are better than a random constructions. The only one example of such construction which I know is in the field of error-...
2
votes
1answer
143 views

Scaling procedures to address false 0's after multiplying probabilities

I need to translate a training algorithm that involves sums and multiplications of probabilities to actual code. For that I need some sort of scaling procedure that allows me to avoid underflows, that ...
9
votes
0answers
298 views

Beating Nonuniformity by Oracle Access

Informally, we say that a Turing machine $M(\cdot)$ approximates a function $f(\cdot)$ if their outputs on a series of inputs are indistinguishable. More formally, let $L$ be a language, $M(\cdot)$ ...
6
votes
2answers
514 views

The probability by which Bloom filters preserves the order relation given a similarity measure on sets

A Bloom filter is a data structure for probabilistic set-membership. When adding an item to the set, $k$ bits (whose indices are determined by $k$ different hash functions) are set to 1. To check if ...
11
votes
1answer
452 views

Borel-Cantelli Lemma and Derandomization

I was reading a paper titled Random Oracles with(out) Programmability. The last paragraph of section 2.3 reads: [Using our novel approach] there is no need to apply well-known classical ...
5
votes
0answers
136 views

Sampling small separators

Is there a tractable way to define an approximate distribution over small vertex separators of the graph? I'm looking for something along the lines of [Bayati,2008], a way to turn a single "this is a ...
5
votes
0answers
309 views

Geometric / Visual explanation that the average height of a random binary tree of given size $n$ is asymptotically $2\sqrt{\pi n}$

I just finished reading the proof that the average height of a random binary of given size $n$ is asymptotically $2\sqrt{\pi n}$. I'm now searching for an intuitive, or geometric, or visual proof of ...
2
votes
1answer
684 views

Can the mutual information of a “cell” be negative?

Please forgive me if this is not the right Stack Exchange (I also posted it at Cross Validated). Please also forgive me for inventing terms. For discrete random variables X and Y, the mutual ...
12
votes
2answers
533 views

Pairwise independent gaussians

Given $X_1,\ldots,X_k$ (i.i.d. gaussians with mean $0$ and variance $1$), is it possible (how?) to sample (for $m=k^2$) $Y_1, \ldots, Y_m$ such that $Y_i$'s are pairwise independent gaussians with ...
16
votes
2answers
530 views

Avalanche like stochastic process

Consider the following process: There are $n$ bins arranged from top to bottom. Initially, each bin contains one ball. In every step, we pick a ball $b$ uniformly at random and move all ...
20
votes
1answer
477 views

Are there efficient general Bonferroni-style bounds known?

A classic problem in probability theory is to express the probability of an event in terms of more specific events. In the simplest case, one can say $P[A \cup B] = P[A] + P[B] - P[A \cap B]$. Let's ...
9
votes
2answers
564 views

Chernoff-type inequality for random variable with 3 outcomes

Suppose we have a random variable which takes non-numeric values a,b,c and want to quantify how empirical distribution of $n$ samples of this variable deviates from true distribution. The following ...
4
votes
1answer
274 views

Expected Halt Time

I'm sorry if the following question seems too obvious. In fact, I oversimplified a much harder problem to this one. Consider the following algorithm, where $0 < p \le 1$ is a constant: ...
21
votes
6answers
1k views

What is the best way to get a close-to-fair coin toss from identical biased coins?

(Von Neumann gave an algorithm that simulates a fair coin given access to identical biased coins. The algorithm potentially requires an infinite number of coins (although in expectation, finitely many ...
29
votes
3answers
1k views

What does one mean by heuristic statistical physics arguments?

I have heard that there are heuristic arguments in statistical physics that yield results in probability theory for which rigorous proofs are either unknown or very difficult to arrive at. What is a ...
13
votes
3answers
2k views

Chernoff-type Inequality for pair-wise independent random variables

Chernoff-type inequalities are used to show that the probability that a sum of independent random variables deviates significantly from its expected value is exponentially small in the expected value ...
22
votes
2answers
2k views

Bounds on $E[f(x)]$ in terms of $f(E[x])$ other than Jensen's inequality?

If $f$ is a convex function then Jensen's inequality states that $f(\textbf{E}[x]) \le \textbf{E}[f(x)]$, and mutatis mutandis when $f$ is concave. Clearly in the worst case you cannot upper bound $\...

1 2 3
4