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,025 questions
10
votes
2
answers
3k
views
Statistics for Haar measure of random matrices?
Let's say I have $M$ samples of $N\times N$ real orthogonal matrices. What statistics can I calculate to test if they could have been drawn from a distribution consistent with Haar measure over $O(N)$?...
10
votes
2
answers
2k
views
random category theory
This question is in some sense dual to the one asked in Is there an introduction to probability theory from a structuralist/categorical perspective? since contrary to the OP who asks for references ...
10
votes
3
answers
907
views
Learning roadmap: 'combinatorial' probability
I am about to finish working through Williams's Probability With Martingales. I have studied analysis up to the first five chapters of Folland's text but have not studied any combinatorics yet.
It ...
10
votes
4
answers
904
views
The distribution of the shortest path through $n$ points
In the big picture, I'd like to know: if I sample $n$ points uniformly at random in the unit square, what is the probability that the shortest path that visits each one of them is very small?
More ...
10
votes
1
answer
508
views
Probability over a plane
I raise this question following the reading of Fifty challenging problems in probability with solutions. One of the problem consists in computing the probability that the quadratic equation $x^2 + 2b ...
10
votes
1
answer
1k
views
Duplicating Matryoshka dolls
We start with a single doll of size $1$. Every second, independently of each other, every doll present produces a new doll of half its size with probability $\frac{1}{2}$. What is the expected size of ...
10
votes
1
answer
701
views
Martingales converging in probability but not a.s
It is known that a random series
$$
\sum_{n\geq 1} X_n
$$
whose terms $X_n$ are independent converges a.s. if and only if it converges in probability.
Is it true that a martingale $(Y_n)$ converges a....
10
votes
2
answers
387
views
Distribution of the area statistic for Catalan paths
A Catalan path of semilength $n$ is a path from $(0,0)$ to $(2n,0)$ that proceeds by taking northeast (1,1) or southeast (1,-1) steps, and never goes below the $x$-axis. The area of a path $P$ is the ...
10
votes
1
answer
2k
views
Law of large numbers for martingales
I apologize in advance if this question is too basic, but I've received no response on Math Stack Exchange, so perhaps it is more appropriate here:
Let $X_n$ be a square-integrable martingale with $\...
10
votes
2
answers
344
views
A moment problem
Suppose $X, Y$ are two positive random variables such that $\mathbb{E}[X^\alpha] = \mathbb{E}[Y^\alpha]$ for all $\alpha \in (0, 1/2)$.
It is also known that the first moment exists for each of them, ...
10
votes
3
answers
450
views
Limiting probabilities for two-player game drawing random uniform numbers
Consider this simple 2-person game I just made up:
Player A goes gets to draw a uniform U[0,1] number up to X times. At any time, he may either keep his number, or draw a brand new uniform number. ...
10
votes
3
answers
4k
views
Extension of the Azuma-Hoeffding inequality (when the differences are bounded with large probability)
Let $(X_i)$ be a super-martingale and suppose their differences are bounded ''with high probability'', that is
$$\mathbb{P}(\exists\,i=1,\dots,n\text{ s.t. }|X_i-X_{i-1}|>c_i) \,\leq\, \epsilon$$
...
10
votes
1
answer
652
views
Extending state space to make a process Feller
Let $X$ be a locally compact Hausdorff space, and let $Y_t$ be a continuous Markov process on $X$ with transition function $P(t, x, \Gamma) := \mathbb{P}_x (Y_t \in \Gamma)$. Let $T_t$ be the ...
10
votes
2
answers
270
views
Maximal in-degree in directed voting graph
Real-life motivation. Our team has $n$ members. For the next in-team presentation session, everyone had 1 talk prepared that he or she would be able to present. Now everyone could cast $1$ vote about ...
10
votes
1
answer
494
views
Ping-pong progress through a quincunx
A quincunx or
Galton board consists of
staggered pegs from which ping-pong balls bounce and eventually display
a binomial / normal distribution in catch-bins. I am wondering if the
downward progress ...
10
votes
1
answer
441
views
Probability that a random distance function is metric
Take a random $n \times n$ nonnegative symmetric matrix $D$ with zero diagonal. What is the probability that it is an abstract distance matrix, i.e. satisfies $D_{xy}+D_{yz} \geq D_{xz}$ for all index ...
10
votes
2
answers
2k
views
Central Limit Theorem (and Berry-Esseen theorem) for non-independent variables
Consider the triangular array $X_{n,k}$ such that, for each $n>0$, the variables $(X_{n,1},\cdots,X_{n,n})$ have the following properties:
For any given $1 \le L \le n$, all
subsets of
$(X_{n,1},\...
10
votes
2
answers
797
views
Fitting a mesh to a density function
Suppose I have a probability density function defined on a region in the plane (in my case, the pdf is of the form $f(x) = \alpha\|x\|^{-\beta}$, and the region is the unit disk). For large $N$, is ...
10
votes
2
answers
673
views
"Probabilistic ultrafilters?"
A naive question.
Let $S$ be a set and let $[0,1]^S$ the set of functions from $S$ to the closed interval $[0,1]$.
Suppose given some function $P \colon [0,1]^S \to [0,1]$ satisfying the following ...
10
votes
1
answer
1k
views
Bounds on $\|P^{k+1} - P^k\|$ for $n$ by $n$ stochastic matrix $P$ with trace $n-1$ and integer $k\gg n$
The problem:
We have a $n$-state Markov chain with arbitrary initial distribution and transition matrix $P$ that is arbitrary except that we know that $P$ has trace $n-1$. Of course $P$ is also a ...
10
votes
1
answer
546
views
Are "étalé spaces" a thing for probability spaces?
Let $PX$ be a $\sigma$-algebra on the set $X$, and let $j : PX \to {\sf Set}_{/X}$ be the tautological functor that sends an event $E\subseteq X$ to itself, regarded as a function with codomain $X$. ...
10
votes
1
answer
827
views
Canonical English edition of Dellacherie and Meyer's "Probabilities and Potential"
Probabilities and Potential by Dellacherie and Meyer is a "bible" of probabilistic potential theory, Markov processes, and many related topics. I want my library to acquire it, but I am a bit ...
10
votes
2
answers
927
views
Isomorphisms between spaces of test functions and sequence spaces
I am in the process of writing some self-contained notes on probability theory in spaces of distributions, for the purposes of statistical mechanics and quantum field theory. Perhaps the simplest ...
10
votes
2
answers
5k
views
Approximate a probability distribution by moment matching
Suppose we want to approximate a real-valued random variable $X$ by a discrete random variable $Z$ with finitely many atoms. Suppose all moments of $X$ is finite. We want to match the moments of $X$ ...
10
votes
4
answers
967
views
What m minimizes E(|m-X|^3) for a random variable X?
Let X be a random variable. Then E(|m-X|^1) is minimized when (as a function of m) when m is the median of X, and E(|m-X|^2) is minimized when m is the mean of x.
A couple weeks ago in a technical ...
10
votes
1
answer
260
views
Sufficient condition for the graph of a measurable map to be measurable
Let $f:X \to Y$ be measurable map between measurable spaces w.r.t. to their corresponding $\sigma$-algebras $\Sigma_X$ and $\Sigma_Y$, resp.
If $(X,\Sigma_X)$ is a standard Borel space can we always ...
10
votes
2
answers
699
views
find the probability that an $n \times n$ determinant formed by taking the numbers $1, 2, \ldots, n^2$ at random is odd
In the January 1963 (p. 94) issue of the American Mathematical Monthly, D.C.B. Marsh proved that for a $3 \times 3$ determinant formed from a random distribution of the integers $1, 2, \ldots, 9,$ the ...
10
votes
2
answers
389
views
Tangled random triangles: One giant component?
Suppose you have $n$ triangles whose corners are random points on a sphere $S$
in $\mathbb{R}^3$.
Viewing the triangles as built from rigid bars as edges,
two triangles are linked if they cannot be ...
10
votes
4
answers
792
views
Speed of convergence in Lebesgue's density theorem
Let $\lambda=\text{unif}([0,1])$ be uniform distribution on $[0,1]$ and $B$ be any Borel set. Lebesgue's density theorem states that for $\lambda$-almost all $x\in[0,1]$ the limit
$$\lim_{\epsilon\...
10
votes
2
answers
1k
views
Probability of random (0,1) Toeplitz matrix being invertible
A Toeplitz matrix or diagonal-constant matrix is a matrix in which each descending diagonal from left to right is constant.
What is the probability that a random $n \times n$ binary Toeplitz ...
10
votes
2
answers
2k
views
When is a space of measures a measurable space?
Let $X$ denote a measurable space, that is, a set equipped with a $\sigma$-algebra $\Sigma(X)$. Let $M(X)$ denote the space of real-valued measures over $X$. This is a vector space over the real ...
10
votes
4
answers
4k
views
How to solve a generalization of the Coupon Collector's problem
The coupon collector's problem is a problem in probability theory that states the following (from wikipedia):
Suppose that there are $n$ coupons, from which coupons are being collected with ...
10
votes
1
answer
492
views
(Asymmetric) matrix power series in closed form: $\sum_{i=0}^{\infty} A^i \left(A^i\right)^{\top}={?}$
Let $A\in \mathbb{S}^{N\times N}$ be a symmetric, real and stable matrix, i.e., $\rho(A)<1$, where $\rho(A)$ stands for the spectral radius of $A$. Then, $$\sum\limits_{i=0}^{\infty} A^{2i}=\left( ...
10
votes
1
answer
1k
views
Limit of pushforward measures of random variables is "represented" by a random variable
Suppose we have an arbitrary probability space $(\Omega,\mathcal{F},\mathbb{P})$ and a sequence of real random variables $X_n:\Omega\to\mathbb{R}$ such that the pushforward measures $(X_n)_*(\mathbb{P}...
10
votes
2
answers
1k
views
Reference Request: Probability and (Nonlinear) PDEs
I'm a graduate student interested in learning about probability and (mostly evolutionary) PDEs, just for fun (and as an excuse to learn some probability). I'm mostly interested in things along the ...
10
votes
1
answer
462
views
For what range of edge probability does the following property hold for random graphs?
Let $G(n,p)$ denote the Erdős–Rényi model of random graph. For a given function $p = p(n)$ we say that $G \in G(n,p)$ asymptotically almost surely has property $\mathcal{P}$ if
$$\mbox{Pr}[G \mbox{ ...
10
votes
2
answers
913
views
Random Trigonometric Polynomial
Let $t_{1},t_{2},\ldots, t_{n}$ be i.i.d. real Gaussian random variables of zero mean and variance one. Let $a_{1},a_{2},\ldots, a_{n}$ be positive and fixed real numbers and define the random ...
10
votes
1
answer
3k
views
Applications of Banach-Tarski Paradox to Probability Theory?
I was just curious, since the B-T paradox is a measure theoretic result, if there are any consequences of this paradox in probability theory? Also, is there is a way of stating the B-T paradox in the ...
10
votes
1
answer
527
views
Random geometric graphs and spanners
I would grateful to learn of work mixing
random geometric graphs with random graphs under
the
Erdős-Renyi model, and in particular concerning spanners.
Select $n$ points uniformly at random from the ...
10
votes
3
answers
2k
views
Random walks and Lyapunov exponents
Given a sequence $Y_1, Y_2, \dots$ of i.i.d. matrices in $\mathrm{GL}_n(\mathbb R)$, there is a theorem of Furstenberg and Kesten which says that if $\mathbb E(\log\|Y_1\|)$ is finite, there exists a ...
10
votes
2
answers
674
views
Expectation of minimum of correlated Gaussian
What is the order of the following expectation with respect to $n$?:
$$\mathbb{E}(\min_{1\leq i\leq n}|z_i|^2)$$
where
$$(z_1,...,z_n)^T\sim N(0,I+11^T), 1=(1,1,...,1)^T$$
I know that when $z_i$ are ...
10
votes
2
answers
544
views
Does the optimal strategy converge in poker if the SPR tends to infinity?
This a a theoretical question about poker type games.
I'm sure I don't have to explain the rules - you can consider No Limit Texas Hold'em or some simple theoretical model, where each player holds a ...
10
votes
1
answer
532
views
a question on 0-1 valued stochastic process
Here's a question on probability theory from a layman (I'm a game theorist). It is very likely that the question will be a straightforward matter for someone who is a probability theorist. I guess I'm ...
10
votes
1
answer
2k
views
Bounds on the moments of the binomial distribution
I'm looking for simple and reasonably tight bounds on the k-th moment of the Binomial distribution $B(n,p)$, namely, $E[B(n,p)^k]$. I'm interested in the case when k is large (say on the order of $\...
10
votes
3
answers
1k
views
Rapid evaluation of multivariate normal integral
I'm implementing a model that requires me to numerically evaluate a multivariate normal integral of the following form
$$\int_{-\infty}^\infty \phi(z)\displaystyle\prod_{i=1}^N \Phi(a_iz+b_i) \, dz,$...
10
votes
1
answer
936
views
exactly simulating a random walk from infinity
In diffusion-limited aggregation on the square lattice, one lets a particle do "random walk from infinity" until it hits the current aggregate, at which point the site occupied by the particle is ...
10
votes
2
answers
2k
views
Convergence of an empirical distribution w.r.t. the Hellinger distance
Let $P$ be a probability distribution on a finite set $\mathcal{X}$ and let $X_1, X_2, \ldots, X_n$ be drawn i.i.d. according to $P$. Define the empirical distribution:
$\hat{P_n}(x) = \frac{1}{n} \...
10
votes
2
answers
1k
views
Continuity of the mutual information
The mutual information $I(\mathfrak A_1;\mathfrak A_2)$ of two complete $\sigma$-algebras $\mathfrak A_1$ and $\mathfrak A_2$ in a Lebesgue probability space $(X,m)$ is the integral of the logarithm ...
10
votes
1
answer
567
views
Is this a well-known probabilistic model?
While I was thinking about the Erdős discrepancy problem, the following random walk model arose rather naturally. You fix a positive integer k, and you take a random step of 1 or -1 at each stage,...
10
votes
2
answers
847
views
Minimum separation among $m$ random points on an $n$-dimensional unit sphere
Consider $m$ points $v_1, \ldots, v_m \in R^{n}$, which are uniformly distributed on the $n$-dimensional unit sphere $S^{n-1} = \{v:\|v\|_2 = 1\}$. Let the minimum separation be
$$
\rho = \min_{i,j\in{...