# Questions tagged [pr.probability]

Questions in probability theory

194 questions
Filter by
Sorted by
Tagged with
29 views

### What is better to chose as field probability and statistic or ANN? [closed]

I am an engineering student. In our college some subjects chose for elective subjects. That include chooses for Artificial neural network and probability and statistic i'm confused to chose any one ...
14 views

### Least-buffer 2ᵏ→n∈⟨1;2ᵏ⟩∩ℕ base conversion of equal-probability messages source

Having an infinite source of messages of $2^k$ possible values of equal probability of occurrence, what is the least necessary buffer needed for a reversible conversion of it to a source of messages ...
102 views

217 views

### How tight is the XOR lemma?

The XOR lemma states that if you have a distribution $D$ on $\{0,1\}^n$, and all the Fourier coefficients of $2^n D$ are small, then it is close in $L_1$ to the uniform distribution. Specifically, ...
65 views

### Reconstruction of a sequence generated by a Markov chain - reference request

Let S be a finite sequence of symbols from a finite alphabet, with gaps - that is on some known locations an unknown number of symbols are missing. Assuming that the sequence , including the symbols ...
151 views

### Why is differential privacy defined over the exponential function?

For adjacent database $D,D'$, a randomized algorithm $A$ is $\varepsilon$-differential private when the following satisfies $$\frac{\Pr(A(D) \in S)}{\Pr(A(D') \in S)} \leq e^\varepsilon,$$ where $S$ ...
189 views

137 views

### Tighter Probability Bounds

Let $\mathcal{F}$ be a class of binary functions on a probability space $\Omega$. For $f \in \mathcal{F}$, let $P(f) =\mathbb{E}(f(Z))$ and $P_n(f) = \frac{1}{n} \sum_{i=1}^n f(Z_i)$ where $Z_i$'s are ...
150 views

### Application of the inequality with expectations

Let $\Vert\cdot\Vert$ is a norm in $R^n$. Let $x_1,\dots,x_N$ non-independent Rademacher random variables random variables (variables which are uniform on $\{-1, 1\}$). . By $E$ we denote an ...
180 views

269 views

160 views

### Lower bound on probability of getting two close points in a sample of $n$ points

Let $D\subseteq \mathbb{R}^k$. Assume that $Pr_{u,v\leftarrow U_D}[|u-v| <B]>p$ for some $B,p$, where $|u-v|$ is the L1 distance of the vectors. $S\subseteq D$ is obtained by sampling $n$ ...
263 views

### What is the connection between moments of Gaussians and perfect matchings of graphs?

Today, I heard the following statement in a talk: The 4th moment of a $1$-dimensional Gaussian distribution with mean $0$ and variance $1$ is the same as the number of perfect matchings of a ...
385 views

### Reference for the number of samples needed to distinguish two probability distributions

I am looking for a reference (and/or a full proof) for this statement: $O(1/\epsilon^2)$ samples suffice to distinguish any two probability distributions with variation distance $\epsilon$. I ...
167 views

### Approaches for Theoretical Analysis of Estimates of Probability Distributions

Consider that you have a probability distribution p of some quantity X and you have obtained (via some algorithm) an estimate q of p according to some definition of closeness. Are there methods/papers ...
326 views

### Understanding proof of Theorem 3.3 in Karp's “Probabilistic Recurrence Relations”

Background: In Karp's paper on Probabilistic Recurrence Relations, he develops tail-bounds for random variables satisfying the following recurrence: $$T(x) = a(x) + T(h(x))$$ where $T(x)$ is a ...