Skip to main content

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.

Filter by
Sorted by
Tagged with
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 $...
Mohammad Golshani's user avatar
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 ...
George Shakan's user avatar
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})$ ...
David's user avatar
  • 486
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 ...
domotorp's user avatar
  • 19.1k
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 ...
CodeGolf's user avatar
  • 1,835
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 ...
Tom LaGatta's user avatar
  • 8,512
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" ...
JSE's user avatar
  • 19.2k
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=...
Aryeh Kontorovich's user avatar
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$. ...
ColorfulLion's user avatar
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 ...
papad's user avatar
  • 274
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$. ...
Penelope Benenati's user avatar
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)....
Dor's user avatar
  • 723
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 $...
Dominik Kwietniak's user avatar
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 ...
Abdelmalek Abdesselam's user avatar
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 ...
JohnA's user avatar
  • 710
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 ...
Daron's user avatar
  • 1,955
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 ...
Erel Segal-Halevi's user avatar
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} \...
Julian Newman's user avatar
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$, $\...
Michael Jarret's user avatar
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<...
James Propp's user avatar
  • 19.7k
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$...
O. Richard's user avatar
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 ...
burtonpeterj's user avatar
  • 1,769
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/...
tourzhao's user avatar
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}...
Veit Elser's user avatar
  • 1,085
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 ...
Stéphane Laurent's user avatar
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, ...
mathjunge's user avatar
  • 191
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 ...
Hedonist's user avatar
  • 1,269
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 ...
MassiveJack's user avatar
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)=\...
Bill Bradley's user avatar
  • 3,979
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\}$...
Sebastien Palcoux's user avatar
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 ...
Joseph O'Rourke's user avatar
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 ...
passing by's user avatar
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 &...
Nate River's user avatar
  • 6,321
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{\...
tsnao's user avatar
  • 620
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 ...
David Aldous's user avatar
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(...
Enforce's user avatar
  • 203
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 $\...
Ilya Gekhtman's user avatar
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 ...
Johnny Cage's user avatar
  • 1,561
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 ...
dohmatob's user avatar
  • 6,853
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 ...
Tony's user avatar
  • 272
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 ...
Probabilist's user avatar
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 ...
Thomas Eberhard's user avatar
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. ...
SBF's user avatar
  • 1,655
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$...
Stéphane Laurent's user avatar
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} \...
Lazward's user avatar
  • 295
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 ...
Alexander Shamov's user avatar
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 ...
marshall's user avatar
  • 283
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 ...
Barium's user avatar
  • 133
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 $...
Maciej Skorski's user avatar

1
26 27
28
29 30
181