Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [pr.probability]

Theory and applications of probability and stochastic processes: e.g. central limit theorems, large deviations, stochastic differential equations, models from statistical mechanics, queuing theory.

0
votes
0answers
4 views

Concentration of the norm of a random vector

Suppose $X$ is a random vector denoted as $(X_1,\cdots,X_n)$, where $X_1,\cdots,X_n$ are iid random variables with sub-Gaussian distributions. For all $i$, suppose $E[X_i^2]=1$ for simplicity and $\|...
0
votes
0answers
22 views

Characterization of Time-homogeneous flows for conditional expectation

Let $X_t,Y_t$ be $\mathbb{R}^d$-valued processes. It is well known that for every $t\geq 0$, and every bounded function $\phi:\mathbb{R}^d\rightarrow \mathbb{R}$, there exists a Borel function $f_t:\...
0
votes
1answer
58 views

Strictly Proper Scoring Rules and f-Divergences

Let $S$ be a scoring rule for probability functions. Define $EXP_{S}(Q|P) = \sum \limits_{w} P(w)S(Q, w)$. Say that $S$ is striclty proper if and only if $P$ always minimises $EXP_{S}(Q|P)$ as a ...
4
votes
3answers
75 views

A clean upper bound for the expectation of a function of a binomial random variable

I wonder if there is a closed-form, or clean upper bound of this quantity: $\mathbb{E}[|X/n-p|]$, where $X\sim B(n,p)$.
-4
votes
0answers
26 views

Probability and profit [on hold]

I have the following problem: I am taking trades. The probability that I win any given trade is 0.6. The probability that I lose any given trade is 0.4. If I win 3 times in a row, I win 7. If I win ...
1
vote
1answer
50 views

Hanson-Wright inequality (quadratic form concentration inequality) for bounded random vectors

Is there a concentration inequality for quadratic forms of bounded random vectors $X \in [-1, 1]^n$ with zero mean and given covariance matrix $\Sigma \in \mathbb{R}^{n \times n}$ but otherwise ...
2
votes
1answer
51 views

Bounding integral arising from expectation of a random variable satisfying Bernstein's inequality

Let $X$ be a random variable s.t. for $v, b > 0$ and $C \geq 1$: $$ P(X \geq t) \leq C\exp\left(-\frac{t^2}{2(v^2 + bt)} \right) $$ I am trying to show that $\mathbb{E}X \leq 2v(\sqrt{\pi} + \...
-1
votes
0answers
46 views

Numerical expectation involving Dirac-delta function

I'm looking for the way for numerical integration including Dirac-delta function. Here is what I want to obtain in numerical way such as Monte Carlo sampling. $$ \int m(\mathbf{x})\delta(G(\mathbf{x}))...
0
votes
0answers
35 views

Computational Time Complexity bounds for approximate maximum of a sequence/array

The problem I have is the following: Given a sequence $x_1, \ldots, x_N$ for $N$ very large. For any $\varepsilon, \delta > 0$, find a number $\hat{x}_{\varepsilon, \delta}$ such that $$\mathbb{P}(...
0
votes
1answer
78 views

How to find a special random variable? [on hold]

Suppose random variables $X_1$ and $X_2$ have the same distribution under P, $Y_1$ is an arbitrary random variable,let $Z_1:=X_1+Y_1$.Can we find a r.v. $Y_2$ which has same distribution as $Y_1$,such ...
-2
votes
0answers
58 views

Joint PDF of Laplace distribution and Gaussian Distribution

If $X$ follows a Laplace distribution with PDF $f(x\left| {\mu ,b} \right.) = \frac{1}{{2b}}\exp \left( { - \frac{{\left| {x - \mu } \right|}}{b}} \right)$ where $\mu$ is a location parameter and $b&...
2
votes
0answers
56 views

Skorokhod representation for weak convergence of exchangeable arrays

Let $(X_e)=(X_e)_{e\in \mathbb{N}^{(k)}}$ be a $k$-dimensional exchangeable real random array (see this note for the definition), where $k\in \{1,2,\ldots \}$ is fixed and $\mathbb{N}^{(k)}$ denotes ...
1
vote
1answer
61 views

Expected size of matchings in a cubic graph

Let $G$ be a random cubic graph on $n$ vertices. Let $M$ be the set of (not necessarily maximum) matchings of $G$. What is the expected size (i.e. number of edges) of an element of $M$? In other ...
3
votes
1answer
88 views

Mixing time and spectral gap for a special stochastic matrix

Conisder the following dimension stochastic matrix, \begin{bmatrix} p & q & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 &...
10
votes
2answers
488 views

Theorems like the Lovász Local Lemma?

The Lovász Local Lemma gives a probability bound in a context where there are many events that are "not quite" independent. What other theorems exist in this genre? That is, what other theorems have ...
3
votes
1answer
80 views

concentration inequality for a weighted sum of independent but not identical binary variables

Let $\alpha\in[0,1]$ be a fixed constant, and let $w,x\in[0,1]^n$ be two vectors such that $\sum_i w_i x_i=\alpha$. Define $Y = \sum_i w_i X_i$, where $X_i \sim \operatorname{Bernoulli}(x_i)$, so it ...
1
vote
0answers
40 views

Monotonicity of $\mathbb{P}\left[\sum_{i=1}^n X_i \leq n \cdot c \right]$ in $n$ for $c>\mathbb{E}(X).$

The nice question below was answered in the affirmative in On the sum of uniform independent random variables Let $X_1,...,X_n$ be independent uniform random variables in [0,1] and assume $c>1/2$. ...
2
votes
1answer
62 views

Asymptotic bound on the total variation distance between a standard multivariate normal and a simple mixture

Let $P = N(\vec{0}, I^d)$ be a standard multivariate Gaussian distribution in $d$ dimensions. Let $Q$ be distributed the same as $P$, except that samples from $Q$ have one of their coordinates, chosen ...
1
vote
0answers
47 views

About a class of expectations

Consider being given a $n-$dimensional random vector with a distribution ${\cal D}$, vectors $a \in \mathbb{R}^k$, $\{ b_i \in \mathbb{R}^n \}_{i=1}^k$ and non-linear Lipschitz functions, $f_1,f_2 : \...
1
vote
2answers
137 views

Integral formula involving Legendre polynomial

I would like a proof of the following equation below, where $(P_n)$ denotes Legendre polynomials. I guess this formula to hold; I checked the first several values. \begin{equation} \int_{-1}^{1}\sqrt{...
2
votes
1answer
177 views

Statement about independence of random variables

If I have 2 random variables $\xi, \eta$ and $\forall n,m \ \mathbb E\xi^n\eta^m=\mathbb E\xi^n \mathbb E\eta^m$, does this imply that $\xi,\eta$ are independent? How to show it?
0
votes
0answers
21 views

Reference: Stochastic Filtering Infinite Dimensions

I've come across these Hilbert Space Signal Finite Dimensional Measurements and Linear Gaussian Hilbert space signal and measurements. Is there any literature solving the Zakai equation when both ...
3
votes
1answer
65 views

Gaussian expectation of outer product divided by norm (check)

I am trying to get compute at least the directional component of the following expectation, where $M$ is a symmetric, invertible, PD matrix: $$\mathbb{E}_{v \sim N(0, I)}\left[\frac{vv^T}{||Mv||_2}\...
-2
votes
0answers
25 views

Looking for a generalization of Binomial distribution and it's properties

In my research (coming from computer science), I have encountered a family of discrete probability distributions that seems to be some sort of generalization of the binomial distribution. A ...
3
votes
2answers
76 views

Expected minimum of a linear function on the unit cube

Let $c\in\mathbb{R}^n$ and let $X_1,X_2$ be two independent uniform samples on the unit cube in $\mathbb{R}^n$. Is there anything at all (in an analytic sense) we can say about the expectation $E\min\...
2
votes
0answers
44 views

Why control a continuous approximation of stochastic gradient descent instead of just the SGD?

In "Stochastic modified equations and adaptive stochastic gradient algorithms" (Li et. al 2015) the authors approximate stochastic gradient descent, as in $$x_{k+1} = x_k - \eta u_k \nabla f_{\...
1
vote
0answers
82 views

Clarification about the ϵ -net argument

I have been reading the paper Do GANs learn the distribution? Some theory and empirics. In Corollary D.1, they reference the paper Generalization and Equilibrium in Generative Adversarial Nets which ...
0
votes
0answers
32 views

Asymptotic upper densities in infinite binary stochastic processes

Consider an infinite binary process $X=X_1,X_2,\ldots$ (with corresponding probability $P$). For some bits $1$ is less probable than $0$. I am interested in the following asymptotic upper density : $$\...
21
votes
0answers
393 views

How many random walk steps until the path self-intersects?

Take a random walk in the plane from the origin, each step of unit length in a uniformly random direction. Q. How many steps on average until the path self-intersects? My simulations suggest ~$8....
3
votes
0answers
59 views

Domain of the Generator of a Bessel process

Consider the Bessel Process of index $\nu\in (-1,0)$, or dimension $\delta=2\nu-1$ \begin{align} \rho_{t}=x+\frac{\delta-1}{2}\int_{0}^{t}\frac{1}{\rho_{s}}\,ds+W_{t} \end{align} where $(W_{t})_{t\geq ...
-1
votes
0answers
43 views

Identical push-forward but not stationary

I'm having some trouble coming up with a counter-example for this problem: Give an example of a stochastic process $\{X_n : n \in \mathbb{Z}^+\}$ on $(\Omega, \mathcal{F}, P)$ such that $P_{X_n} = P_{...
1
vote
1answer
52 views

Concentration inequality for quadratic form of Gaussian variables with non-idempotent matrix

Given $y \sim N(0,\sigma^2 I)$, and $M$ that is a symmetric matrix (not necessarily idempotent) what is the distribution of ${y^T M y}$? is there a high probability bound on $|{y^T M y}|$? Most ...
0
votes
1answer
121 views

Divergence form degenerate pde and Feynman Kac

Consider $$ Au:=\operatorname{div}\left(y^{\beta}\nabla u\right) \text{ for } (x,y)\in \mathbb{H} $$ and $u|_{\mathbb{R}}(x,0)=\phi(x)$ and some $\beta\in (0,1)$. For $\phi\in L^{2}(\mathbb{R},dx)$ (...
1
vote
1answer
54 views

Convergence of probability density function

There are various kinds of (convergence of random variables) but I have never read about convergence of density functions. Let $X_1, X_2, \dots, X$ be random variables $\Omega \to \mathbb{R}$ and $...
4
votes
1answer
50 views

Rate of decay in the multivariate Central Limit Theorem

The celebrated Berry-Esseen inequality tells us that the rate of convergence in the univariate CLT is of magnitude $\frac{1}{\sqrt{n}}$ for sums $S_n=X_1+\cdots+X_n$ of independent random variables $...
6
votes
2answers
146 views

A limit obtained from a probability distribution on the positive integers

Let $p_n$ be a probability distribution on the positive integers $n$. Let $$ \frac{1}{1-\sum_{n\geq 1} p_nx^n}=\sum_{k\geq 0}a_kx^k. $$ Suppose there does not exist an integer $d>1$ such that $d|...
3
votes
0answers
126 views

Central Limit Theorem for simultaneous sums

Take a sample $X_1 \ldots X_n$ of $n$ independent observations $X_j \in \mathbb{R}$ with zero mean and finite variances $\sigma_j^2$. For $i = 1, 2, \ldots$, define the sums $$S^n_i = \frac{\pm X_1 \...
5
votes
1answer
74 views

Variance of sum of $m$ dependent random variables

I originally posted this question in Mathstackexchange, but since I got no answer I'm posting it also here. Let $X_1,X_2,...$ be a sequence of identically distributed and $m$-dependent random ...
1
vote
0answers
38 views

Gilbert-Varshamov with weight condition

For $N$ integer, it is known (Gilbert-Varshamov) that there exists a subset $S$ of $\{0,1\}^N$ such that $|S|$ is still exponential in $N$ and such that two elements $x, x'$ in $S$ are at least ...
1
vote
0answers
92 views

Different balls in bins: What is the probability distribution of the sum of the minimum of the two types of balls over all bins?

Assume that there are $N$ different bins and two different kinds of balls, $R$ red balls and $W$ white balls. The red balls and the white balls are randomly distributed across the bins (that is, for ...
0
votes
0answers
52 views

Probability of detecting small bias in a die in the low confidence regime

We are given a biased $m$-sided die: one of the sides has probability $\frac{1}{m} + \gamma$ and all the rest have probability $\frac{1}{m} - \frac{\gamma}{m-1}$ each. The goal is to figure out which ...
2
votes
1answer
71 views

How to efficiently sample uniformly from the set of $p$-equipartitions of an $n$-set?

I have a question related to this one. For $n,p \in \mathbb{N}_+$ such that $p\mid n$, let $\mathcal{P}^{\rm eq}$ be the set of all equipartitions of $n$ in $p$ sets; i.e., in sets of equal size $\...
3
votes
0answers
165 views

How should the proof of the XYZ theorem be understood?

The XYZ Theorem of Shepp [1] states that for a given poset $P$. Consider the probability space of all the linear extensions of $P$, where each possible extension is equally likely. Then for any three ...
0
votes
0answers
39 views

Mean first-passage time for a marked Poisson process

Given a marked Poisson process in one dimension $$ Y(t)=\sum_{\{t_i,a_i\}}g(t-t_i,a_i) $$ so that $Y(t)$ is a sum of impulses arriving as a Poisson process and the impulses $g$ belong to a family of ...
8
votes
1answer
106 views

Log-concavity of repeated convolution

Let $A = (a_0,a_1,\ldots,a_k)$ be a sequence of strictly positive numbers, and let $A^{\ast k}$ denote the $k$-fold repeated convolution (defined by $A^{\ast 1} = A$ and $A^{\ast k+1} = A^{\ast k} \...
0
votes
0answers
49 views

Generalized eigenvectors of block triangular random matrices

Let $A = (a_{ij})_{1 \leq i,j \leq N}$ and $B = (b_{ij})_{1 \leq i,j \leq N}$ be random matrices, with each $a_{ij}$ and $b_{ij}$ an independent random variable with continuous density function, zero ...
-1
votes
0answers
31 views

One sided point-wise Berry-Esseen like inequality for discrete variable

Let us consider a distribution $\mathcal{L}$ on a finite set of integers (actually I'm even happy with any RV on the set $\{-1,0,1\}$) (with probability not to extremes : roughly around 1/4 for -1, 1 ...
2
votes
2answers
149 views

Birthday problem extension to unequal probabilities and multiple collisions

Let $p_1, ... ,p_k$ denote the probabilities of drawing bin $1, .. ,k$, where $\sum_{i = 1}^{k} p_i= 1$. My question is if we draw $n$ times, how can I show that the probability that all bins are ...
5
votes
1answer
141 views

Binomial Distributions and Inequality

Suppose $c>2$ is a real number, and $x$ solves equation $f(\frac{1}{2}+x,m,2m)=(2m+1)cx$ for some $m>0$ integer number, where $f$ is probability mass function for binomial distribution, with ...
-1
votes
1answer
99 views

Distribution of first time a 1D random walk hits n or -n

Let $(\omega_1, \omega_2, \ldots)$ be iid in $\{-1, 1\}$ and $X_k = \sum_{i=1}^k \omega_i$ be a simple one-dimensional random walk. Let $\tau_n = \min \{i\in\mathbb{N}: |X_i|=n\}$ be the first time ...