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.
9,027 questions
7
votes
2
answers
338
views
Set theoretic forcing, large cardinals and probabilistic methods
This question is motivated by the work of Ajtai "The complexity of the pigeonhole principle" and similar works. In this paper, the author proves that $PHP_n$, the pigeonhole principle for $...
7
votes
1
answer
719
views
Tightness and Functional Analysis
Let $(\Omega , \mathbb{P})$ be a probability space and $X$ be a real-valued random variable. Then we immediately have the push-forward measure $\mu$ on $\mathbb{R}$ and one can think of $\mu$ as an ...
7
votes
1
answer
621
views
Does every (generalized?) Markov chain admit transition probabilities?
To pose the question let us start by recalling the following notions:
Transition Probabilities. A transition probability matrix between two measurable spaces $(S,\mathcal{S})$ and $(V,\mathcal{V})$ ...
7
votes
1
answer
191
views
Is there a Degenerate Dependency Local Lemma?
The Lovasz Local Lemma has several generalizations, with names usually starting with L, such as Lopsided or Lefthanded.
Here I ask whether another possible generalization (for which I could not yet ...
7
votes
1
answer
1k
views
a $L^1$ convergence for backward martingale
I have a question which may be naive, but I can not find the related result in the classical reference such as "Foundations of Modern Probability" and "Probability"(Billingsley). So if someone knows ...
7
votes
2
answers
417
views
Does every commutative monoid admit a translation-invariant measure?
Let $T$ be a commutative monoid, written additively. The set $T$ is equipped with a canonical pre-order, defined by $s \le t$ when there exists $s' \in T$ so that $s + s' = t$. Consequently, $T$ may ...
7
votes
3
answers
2k
views
Interesting applications of [Martingale/Brown motion/diffusion/percolation ] theory?
This question is motivated by an exercise called "The Star-ship Enterprise's Problem" in Williams's book "probability with martingales", it can be stated as follows:
Suppose the control system on ...
7
votes
2
answers
417
views
Dynamics of a random "quadratic" directed graph
Let G be a directed graph on N vertices chosen at random, conditional on the requirement that the out-degree of each vertex is 1 and the in-degree of each vertex is either 0 or 2. The "periodic" ...
7
votes
2
answers
706
views
Poisson binomial conjecture
Let $X_i\in\{0,1\}$
be mutually independent and distributed according to $\mathrm{Bernoulli}(p_i)$
and similarly, $Y_i\sim\mathrm{Bernoulli}(q_i)$,
for some parameters $p,q\in[0,1]^n$. Put $X:=\sum_{i=...
7
votes
1
answer
524
views
What happens when the diffusion term in an SDE becomes zero?
Consider this time-homogeneous SDE, in the Ito sense:
$$dX_t= -(X_t-a)\,dt+\sigma(X_t)\,dW_t,$$
where $W_t$ is standard Brownian motion, $a<b\in\mathbb{R}$, $X_0\leq b$ a.s., and $\sigma(b)=0$. ...
7
votes
2
answers
235
views
Evolution of the empirical mean of a list as we remove elements proportional to their value
Consider a list of $N$ integers $k_1,k_2,\dots k_N$, drawn independently from some distribution $P(k)$ with $k_i \geq 1$. We denote its mean with $\langle k\rangle=\sum_{k=1}kP(k)$. The first two ...
7
votes
1
answer
186
views
$d$-ball approximation for $d\gg 1$ with a convex hull of random points on its boundary
Given a $d$-ball $\mathcal{S}^{d}$, let $P_n$ a set of $n$ points selected uniformly at random on the boundary $\mathcal{S}^{d-1}$ of $\mathcal{S}^{d}$. Let $\mathcal{C}_n$ the convex hull of $P_n$. ...
7
votes
1
answer
292
views
Local probabilities for lattice random walk
Let $\epsilon <1/2$. Let $X$ be a random variable in $\mathbb Z$ such that $\mathbb P (X=x)\le \epsilon $ for any $x\in \mathbb Z$ (you may add any moment or regularity conditions on $X$ if needed)....
7
votes
1
answer
253
views
Are all quasi-regular points on Polish spaces generic points?
Let $X$ be a Polish space and $T\colon X\to X$ be a continuous map. We say that a point $x\in X$ is quasi-regular if for every bounded continous function $\varphi\colon X\to\mathbb{R}$ the sequence $...
7
votes
1
answer
431
views
What makes Gaussian distributions special? Local field version?
This question is inspired by the recent one about Gaussian measures over the reals:
What makes Gaussian distributions special?
I would be interested in a similar list of characterizations for the ...
7
votes
1
answer
1k
views
Reference request: norm topology vs. probabilist's weak topology on measures
Let $(X,d)$ be a metric space and $\mathcal{M}(X)$ be the space of regular (e.g. Radon) measures on $X$. There are two standard topologies on $\mathcal{M}(X)$: The (probabilist's) weak topology and ...
7
votes
1
answer
409
views
Do i.i.d. sums concentrate any faster than martingales?
Suppose $X_1,X_2, \ldots, X_N \in \mathbb R^d$ are random variables with each $\|X_n\|_2 \le 1/2$ (this choice of the constant simplifies later formulae).
The simplest concentration inequality I know ...
7
votes
1
answer
436
views
What numbers can simulate 1/2?
Given two numbers $p,q\in(0,1)$, we say that $p$ can simulate $q$ if, given a biased coin with probability $p$, we can toss it a bounded number of times and use the results to simuate a biased coin ...
7
votes
1
answer
881
views
Does the strong Markov property imply the "really strong Markov" property?
Let $\mathbf{\Omega}=(\Omega,\mathcal{F},(\mathcal{F}_t)_{t \in [0,\infty)},\mathbb{P})$ be a filtered probability space satisfying the Usual Conditions.
Let $P \colon [0,\infty) \times \mathbb{R} \...
7
votes
1
answer
222
views
Bound on queries to a tree with unusual probabilities
Consider a tree $\mathcal{T}(r) = (V,E)$ rooted at $r \in V$. Let $\kappa_r: V \longrightarrow [0,1]$ such that $\sum_{v \in V} \kappa_r(v)^2 = 1$. Furthermore, for any given vertex $v \neq r$, $\...
7
votes
2
answers
340
views
Sign-oscillations for power series with random coefficients
Let $p(x) = \sum_{k \geq 0} a_k x^k$ where the $a_k$'s are IID random variables taken from a mean-zero random variable taking finitely many values in $\mathbb{R}$; it clearly converges for $-1<x<...
7
votes
2
answers
3k
views
The largest Wasserstein distance to uniform distribution among all probability distributions with uniform marginals
I am looking for the largest Wasserstein distance to the uniform distribution among all probability distributions with uniform marginals.
More specifically, let $\Xi=\{1,2,\ldots,N\}^2$, and let $\nu$...
7
votes
1
answer
222
views
Algorithm to generate random commuting permutations
I am seeking to understand the properties of a typical pair of permutations $(\sigma,\tau) \in \mathrm{Sym}(n)^2$ chosen uniformly at random from all pairs such that $\sigma$ and $\tau$ commute. In ...
7
votes
2
answers
606
views
Uniform Concentration Bounds on Weighted Sum of i.i.d. Bernoulli Random Variables
Let $\delta_1,...,\delta_n$ be $n$ independent identically distributed Bernoulli random variables with $\mathbb{P}(\delta_1=1)=p$. We consider a set $\Omega = \{\mathbf{a}:=(a_1,...,a_n)~|~a_i\in [0,c/...
7
votes
1
answer
178
views
A case of nested central limits
Consider the random variable $S=(s_0, \dots ,s_{N-1})$, a sequence of signs uniformly distributed on the hypercube $\{-1,1\}^N$. We are interested in $N$ large and prime. The Fourier transform $\hat{S}...
7
votes
2
answers
321
views
Random suborbits of a rotation
Let $u_n = x + n\alpha \pmod 1$ with $\alpha$ irrational. We know that $(u_n)_{n \geq 0}$ is dense in $\mathbb{R}/\mathbb{Z}$ (equivalently $(u_n)_{n \geq 0}$ visits every open interval infinitely ...
7
votes
1
answer
441
views
Recursive sequence of binomial random variables
Fix $p>0$ and define a recursive sequence of random variables with $X_1 =1$ and
$$X_{k+1} = X_k + \text{Bin}(X_k,p).$$
Thus, $\mathbf E [ X_k ] = (1+p)^k$.
I would like a left tail bound. Perhaps, ...
7
votes
1
answer
499
views
Moments of a random variable and of its conditional expectation
Let $X$ be a bounded random variable with $\mathbb{E}X=0$. Since $X$ is bounded, all its moments exist. Let $\mathcal{G}$ be any $\sigma$-field and let $Y:=\mathbb{E}[X|\mathcal{G}].$ I am interested ...
7
votes
1
answer
467
views
Properties of the algebraic self-difference set of Brownian motion zeros
As I was trying to exhibit new interesting(?) path transformations of Brownian motion, I became interested in
the (random) set of times $t$ such that $B(t)=B(t+1)=0$, where $B(t)$ denotes a standard ...
7
votes
1
answer
355
views
Injectivity of matrix "fingerprint"
Consider $S$, the set of all $n\times m$ real matrices with specified row sums $(r_1,...,r_n)$, column sums $(c_1,...,c_m)$, and strictly positive entries.
For any matrix $A$, define
$$ D_A(i,j)=\...
7
votes
2
answers
639
views
Is there an algebraically normal function from $\mathbb{Z}^{n}$ to $\{ 0 , 1\}$?
Definition: Let $h$ be a polynomial in $n$ variables, then :
$\gamma(h,r,R):=\{ v \in \mathbb{Z}^{n} : \vert h(v) \vert \leq r, \Vert v \Vert < R \}$
Let $\omega : \mathbb{Z}^{n} \to \{ 0 , 1\}$...
7
votes
3
answers
377
views
Expected minimum face angle of random convex polyhedron in $\mathbb{R}^3$
Let $P_n$ be a "random convex polyhedron" in $\mathbb{R}^3$ of $n$ vertices, where "random" could follow any one
of a number of models:
(1) the convex hull of $n$ points randomly and uniformly ...
7
votes
1
answer
296
views
Existence of Limiting Distribution for Moving Regions in Stat. Phys. Models
As the title (hopefully) suggests, I've been trying to prove (or disprove) the existence of a limiting distribution for a certain projection in a statistical physics model. I'll give the details of ...
7
votes
1
answer
239
views
Size doubling amoeba
Note: Here time is assumed to be discrete and indexed by the naturals $\mathbb N$.
A curious species of amoeba undergoes the following evolution rule - at each time step, with probability $0 < p &...
7
votes
2
answers
307
views
PDE for the probability of Brownian motion staying in an area (reference request)
I am looking for a (preferably some monograph) reference on the following fact:
$$
u ( t, x ) = \mathbb{P} \{ x + B_s \in A \ \text{for all} \ s \leq t \}
$$
satisfies the heat equation
$$
\frac{\...
7
votes
1
answer
156
views
Nearest neighbors on random complete graph
Consider the complete graph on $2n$ vertices, where the ${2n \choose 2}$ edges have distinct lengths in uniform random
order. So each vertex $v$ has a nearest neighbor $N(v)$, across the shortest ...
7
votes
1
answer
249
views
Onsager-Machlup functional when drift is time-dependent
Let $X(t)$ be a diffusion process on $\mathbb{R}^d$ generated by
\begin{align}
\mathcal{D} = \nabla^2 + \sum_{i=1}^d b_i(x) \frac{\partial}{\partial x_i},
\end{align}
where $b_i(x) \in \mathcal{C}_b^2(...
7
votes
1
answer
274
views
Uniqueness of stationary measures for $(G,\mu)$ boundaries
Let $G$ be a countable group acting minimally by homeomorphisms on a compact Hausdorff space $X$ and $\mu$ be a probability measure on $G$ whose support generates $G$ as a semigroup.
Let $\nu$ is a $\...
7
votes
1
answer
258
views
Collecting proofs of the birth of the giant component
I want to collect different proofs of Erdös-Rényi result on the double jump of the largest connected component on $G(n,p)$ (or in $G(n,M)$.
I know the original proof of Erdös-Rényi, the proof that ...
7
votes
1
answer
424
views
Transportation-cost inequality for pushforward measure
Let $X=(X,d_X)$ and $Y=(X,d_Y)$ be metric spaces and $\varphi: X\rightarrow Y$ be an $L$-Lipschitz map, with $0 \le L < \infty$. Suppose $\mu$ is a probability measure on $X$ which satisfies ...
7
votes
1
answer
880
views
Bound for largest eigenvalue of symmetric matrices of uniform random variables over $[0,1]$ and fixed $1$s along diagonal and scattered $1$s
Given a $n\times n$ symmetric random matrix whose diagonal elements are all fixed as $1$. In addition, there are $k$ $1$s will be randomly scattered in upper triangular (of course, the corresponding ...
7
votes
1
answer
278
views
A Converse of the Skorokhod Embedding Theorem
I am wondering whether the following "sort of converse" of Skorokhod's embedding theorem holds:
Suppose that $\{D_t\}_{t \geq 0}$ is a stochastic process with continuous paths, $D_0 = 0$, and suppose ...
7
votes
1
answer
266
views
Is there a proof that the Law of Large Numbers is the limit (numerical) for estimation of expected values?
For the sake of this question I want to focus on an unfair coin.
Assuming we have a number of $i.i.d.$ samples $X_1, ..., X_n$ and a precision level requirement $\tau$. I search for the optimal ...
7
votes
1
answer
421
views
Convex representation of a measure
Let $\mathcal P(X)$ denote the space of all probability measure defined on a measurable space $X$. We canonically endow the former with its own measurability structure, generated by evaluation maps. ...
7
votes
2
answers
409
views
Estimating entropy conditional to an event
Take for example the measure $\mu(n)=n^2$ on $\{1, \ldots, N\}$ and a random variable $X$ distributed according to the probability obtained by normalizing $\mu$.
Does there exists a constant $K>0$...
7
votes
1
answer
1k
views
Central limit theorem for biased random walk
Define random variables $X_n$ by $X_0 = 0$ and
\begin{equation*}X_n - X_{n-1} = \begin{cases}
1 & \text{with probability } g(X_{n-1}) \\
0 & \text{with probability } 1-g(X_{n-1})
\end{cases}
\...
7
votes
1
answer
444
views
Is an infinite-dimensional "Lebesgue measure" uniquely determined by a set of positive finite measure?
Let $\mu$ be a probability measure on a subset $C \subset \mathbb{R}^\infty$ of the space of sequences, and assume, for simplicity, that $C$ is closed and convex.
We say that $\mu$ admits shifts if ...
7
votes
1
answer
468
views
Mean time to get $k$ heads for a coin with growing bias
For integers $n,k\geq 1$ we repeatedly toss a coin and count the number of heads that occur. The probabilty of getting a head is $min(t/n,1)$ where $t$ is the current discrete time step. I am trying ...
7
votes
1
answer
309
views
The time to drift a binary string from one state to another via deterministic selection of two possible random bit mutation procedures
I have some length $L$ binary string consisting of an ordered array of bits: $(b_1, b_2, ..., b_{L})$, where all bit values $b_i$ are originally set to zero. I'd like a particular set of $n$ bits to ...
7
votes
2
answers
698
views
Convergence rate of the convolution of almost uniform measures on $\mathbb{Z}_p$
Statement Given a finite abelian group $G$ and two independent random variables $X,Y$ taking values in $G$ and satisfying $d_{TV}(X,U_G)\leqslant \delta$ and $d_{TV}(Y,U_G)\leqslant \delta$ (where $...