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
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)$?...
Jiahao Chen's user avatar
  • 1,890
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 ...
Sylvain JULIEN's user avatar
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 ...
Jyotirmoy Bhattacharya's user avatar
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 ...
Will Schaefer's user avatar
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 ...
mathcounterexamples.net's user avatar
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 ...
Nate River's user avatar
  • 6,313
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....
Liviu Nicolaescu's user avatar
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 ...
David Galvin's user avatar
  • 1,112
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 $\...
user90661's user avatar
  • 103
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, ...
random_person's user avatar
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. ...
bigO6377's user avatar
  • 211
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$$ ...
user118866's user avatar
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 ...
Nate Eldredge's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Joseph O'Rourke's user avatar
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 ...
Felix Goldberg's user avatar
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},\...
jmscarlett's user avatar
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 ...
John Gunnar Carlsson's user avatar
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 ...
JSE's user avatar
  • 19.2k
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 ...
Warren Schudy's user avatar
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$. ...
fosco's user avatar
  • 13.6k
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 ...
Nate Eldredge's user avatar
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 ...
Abdelmalek Abdesselam's user avatar
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$ ...
gondolier's user avatar
  • 1,839
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 ...
Michael Lugo's user avatar
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 ...
Packo's user avatar
  • 285
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 ...
mark's user avatar
  • 153
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 ...
Joseph O'Rourke's user avatar
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\...
user240643's user avatar
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 ...
user avatar
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 ...
Tom LaGatta's user avatar
  • 8,512
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 ...
Herman's user avatar
  • 101
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( ...
Augusto Santos's user avatar
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}...
Mizar's user avatar
  • 3,146
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 ...
Dean's user avatar
  • 101
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{ ...
Matthew Kahle's user avatar
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 ...
ght's user avatar
  • 3,626
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 ...
Matt Calhoun's user avatar
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 ...
Joseph O'Rourke's user avatar
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 ...
Elena's user avatar
  • 315
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 ...
neverevernever's user avatar
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 ...
domotorp's user avatar
  • 19k
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 ...
Arkadi Predtetchinski's user avatar
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 $\...
Vitaly's user avatar
  • 211
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,$...
melchimm's user avatar
  • 101
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 ...
James Propp's user avatar
  • 19.7k
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} \...
Anand Sarwate's user avatar
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 ...
R W's user avatar
  • 17k
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,...
gowers's user avatar
  • 29k
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{...
Minkov's user avatar
  • 1,127

1
14 15
16
17 18
181