# Questions tagged [pr.probability]

Questions in probability theory

200 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
66 views

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 &...
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 ...
243 views

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 ...
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 ...
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 ...
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-...
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 ...
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)$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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: ...