Questions tagged [pr.probability]

Questions in probability theory

Filter by
Sorted by
Tagged with
4
votes
0answers
145 views

Concentration Bounds for Dependent Rounding

Consider the following random process which is defined on $n$ numbers $0\leq x_1,\ldots,x_n\leq 1$: At each step, pick an arbitrary number, say $x_i$. Then randomly (and independently) change its ...
9
votes
2answers
565 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 ...
3
votes
0answers
66 views

Set-systems with some version of independence

Let $S \subset [N]$ be a fixed set of size $n$. Suppose $p$ is the probability that a random set $T$ of size $m$ intersects $S$ in $k$ or more points. That is, $$ \Pr_{\substack{T\subset [N]\\|T| = m}}...
1
vote
2answers
916 views

Chernoff Bounds for settings with limited dependence

Could someone point me to a way of bounding the tail probability of sums of bernoulli variables each generated by the same distribution but the condition of independence is only partially satisfied. ...
3
votes
0answers
92 views

A sampling and learning question

Suppose there is an oracle that returns a number $b \in \mathbb{Z}_{n}$ whenever I press the button. We have $b = a + e$, where $a \in \mathbb{Z}_n$ is a fixed number and $e$ is sampled according to ...
3
votes
1answer
208 views

Boundedness of expected reward Markov chain

This is a repost of a question I asked on math.SE. The problem: I have an infinite Markov chain $M$ over the natural numbers, with transition probabilities $$P(n,m)=\sum_{i=0}^{min(m,n)} {n\choose i}...
2
votes
1answer
732 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 &...
5
votes
2answers
166 views

Behaviour of Labelled Markov Processes

Labelled Markov Processes (LMP) seem to be a generalization of Probabilistic Automata (PA) studied by Segala to the case of the general state space. Namely, any LMP is given by a be a finite set of ...
1
vote
0answers
243 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
388 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 ...
6
votes
2answers
516 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 ...
24
votes
2answers
2k views

Balls and Bins analysis in the $m \gg n$ regime: gaps

Suppose we are throwing $m$ balls into $n$ bins, where $m \gg n$. Let $X_i$ be the number of balls ending up in bin $i$, $X_\max$ be the heaviest bin, $X_\min$ be the lightest bin, and $X_{\mathrm{sec-...
3
votes
1answer
225 views

Coupon collector - the effect of randomization

Given a set $S = \{1, ..., n\}$, an element is randomly drawn with replacement from $S$. Let's say we got the following sequence $X = \{x _1, ..., x _k\}$ until all elements of $S$ are seen, where $x ...
-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 ...
7
votes
1answer
346 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 = \...
11
votes
0answers
395 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 ...
3
votes
1answer
349 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
164 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 ...
5
votes
1answer
250 views

Random walk returning probability

Consider a two-dimensional random walk, but this time the probabilities are not $1/4$, but some values $p_1, p_2, p_3, p_4$ with $\sum_{i=1}^4 p_i=1$. For example, from $(0,0)$, it goes to $(1,0)$ ...
9
votes
2answers
288 views

Guessing a low entropy value in multiple attempts

Suppose Alice has a distribution $\mu$ over a finite (but possibly very large) domain, such that the (Shannon) entropy of $\mu$ is upper bounded by an arbitrarily small constant $\varepsilon$. Alice ...
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
188 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 ...
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, ...
2
votes
1answer
253 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 ...
13
votes
2answers
540 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 ...
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, ...
9
votes
3answers
542 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
353 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
567 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}$ ...
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 ?
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 ...
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)$ ...
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
689 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 ...
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 the balls ...
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 ...
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 ...

1 2 3
4