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,022 questions
14
votes
0
answers
1k
views
The threshold for a perfect matching in a random subgraph of a regular bipartite graph?
The following question seems very natural.
It is a well known consequence of Hall's Theorem that every regular bipartite graph has a perfect matching. Another classical result states that the ...
14
votes
0
answers
585
views
Apparent disparity between the results of two papers (nearest neighbours)
This is a follow up question this one on MSE, which can basically be summarised as Robert Abilock originally posed in American Monthly in 1967:
The Rifle-Problem:
$n$ riflemen are distributed at ...
14
votes
0
answers
629
views
Probability of many overlapping zero inner products on a circle
[Question edited and changed a little on June 14 2015]
Consider an $n$-dimensional vector $v$ with $v_i \in \{-1,1\}$. Now consider an $n$-dimensional vector $w$ with $w_i \in \{-1,0,1\}$. The ...
14
votes
0
answers
587
views
Why, and how badly, does the proof of "no percolation at the critical point in half-spaces" fail for full spaces?
The proof by Barsky et. al. that there is no percolation in half-spaces proceeds by a dynamic renormalization argument. The proof couples critical percolation in the half-space $\mathbb{H}^d$ with a ...
13
votes
11
answers
6k
views
A problem of an infinite number of balls and an urn
I think that the following problem originated in a probability textbook :
You have a countably infinite supply of numbered balls at your disposal. They are all labeled with the natural numbers {1,2,3,...
13
votes
2
answers
3k
views
Who first chose the names Alice and Bob for players A and B? [closed]
Who first chose the names Alice and Bob for the players (or observers) A and B?
13
votes
7
answers
2k
views
Finite-space dynamical systems
This question is quite open-ended, but I will formulate several sub-questions that I'll try to make precise. It is about finite-state dynamical system: start with a finite set $X$, with say $n$ ...
13
votes
4
answers
5k
views
Gaussian processes, sample paths and associated Hilbert space.
Given a Gaussian process on some topological space $T$, with a continuous covariance kernel
$C(\cdot,\cdot)\colon T\times T\to R$, we can associate a Hilbert space, which is the reproducing kernel ...
13
votes
2
answers
1k
views
A comprehensive list of random walk inequalities?
I am interested in finding a comprehensive list of all noticeable random walk inequalities.
ie. $S_n = \sum_{k\leq n} X_i$ for i.i.d symmetric $X_i$
I can only seem to find books/papers that list ...
13
votes
5
answers
71k
views
How do I convert a uniform value in [0,1) to a standard normal (Gaussian) distribution value?
I have uniform value in [0,1). I'd like to transform it into a standard normal distribution value, in a deterministic fashion.
What I'm confused about with the Box-Muller transform is that it takes ...
13
votes
4
answers
5k
views
What is known about the Gaussian measure of the unit ball in a Hilbert Space?
Let $X$ be an infinite dimensional separable Hilbert Space with norm $||\cdot||$ and let $\mu$ be a Gaussian measure on $X$ such that $\mu(X) = 1$. What do we know about $\mu(B(0,1))$, where $B(0,1)$ ...
13
votes
8
answers
1k
views
The vertices of a triangle are three random points on a unit circle. The side lengths are, in random order, $a,b,c$. Show that $P(ab>c)=\frac12$
The vertices of a triangle are three unifomly random points on a unit circle. The side lengths are, in random order, $a,b,c$.
There is a convoluted proof that $P(ab>c)=\frac12$. But since the ...
13
votes
7
answers
1k
views
Probabilistic (and other mathematical) methods of physics without the physics?
Many of the methods of physics are vastly more general than their use in that discipline. For example, information theory overlaps with a lot of statistical mechanics, and the latter actually ...
13
votes
3
answers
933
views
Probability of commutation in a compact group
It is well known that if $G$ is a finite group, then the probability that two elements commutte is either $1$ (if $G$ is abelian) or less than or equal to $\frac58$.
If instead $K$ is a compact group,...
13
votes
4
answers
1k
views
What results would follow from or imply "randomness" of the primes?
This question on random versions of deterministic problems reminded me that many conditional results in number theory hold if the primes are in some sense random, and it is common knowledge that the ...
13
votes
4
answers
1k
views
Why only three classical matrix ensembles in random matrix theory?
I am just starting out on understanding random matrix theory from a background in applied mathematics. I have a very basic question about the Gaussian ensembles: why are there only three classical ...
13
votes
2
answers
1k
views
Probability vector $p$ majorizes its normalized entropy vector $\small \frac{-p\log p}{H(p)}$
I guess the following inequality
$$ \sum_{i=1}^n g \left (\frac{-p_i \log p_i}{H(\boldsymbol{p})} \right ) \le \sum_{i=1}^n g (p_i)$$
holds for any continuous convex function $g$ and any probability ...
13
votes
2
answers
715
views
What time does it take for irrational rotations to hit an interval?
Hi,
Consider $\theta_n = (\theta_0 + n \theta) \mod 1$, $\theta$ being an irrational number, and $\theta_0$ an uniform random variable in $(0,1)$. Is there any estimates for the time it will take ...
13
votes
4
answers
4k
views
The probability for a streak when tossing a coin
I'm trying to solve the following problem:
Let's say I'm tossing a coin $N$ times. The coin is not fair, such that the probability for heads is $p_0$ and for tails is $1-p_0$.
What is the ...
13
votes
2
answers
669
views
An inequality for expected value of normally distributed variables
Question. Let $X_1,\dots,X_n$ be random variables with normal distribution. Is it true that
$$\mathbb E \prod_{i=1}^nX_i^{2k}\ge\prod_{i=1}^n\mathbb E X_i^{2k}$$for any $k\in\mathbb N$?
(The ...
13
votes
2
answers
1k
views
Non-integrable ergodic theory
Can anyone help me out with proofs/counterexamples? I'm working on an operator-valued multiplicative ergodic theorem and need what may(?) be a well-known fact. This fact (if true) would help me get ...
13
votes
2
answers
1k
views
Is there a homotopy/homology-theory for probability spaces?
Please excuse that the following will be a somewhat soft question.
Let $(M,d)$ be a metric space and $X(\omega)$ a random variable on $M$ with distribution $\mu$.
Assume now that $M = \overline{B_1^n(...
13
votes
1
answer
791
views
How nearly abelian are nilpotent groups?
It is not uncommon to read that "nilpotent groups are 'close to abelian'."1,2
Can this sentiment be made precise
in the sense of the
Turán and Erdős definition of "the probability that two elements of ...
13
votes
1
answer
6k
views
What's the maximum entropy probability distribution given bounds [a,b] and mean?
What is the continuous probability distribution that maximizes entropy, given only the bounds of the random variable [a,b] and the mean mu of the probability distribution?
For example:
if a=0, b=1, ...
13
votes
1
answer
762
views
If $(a,b,c)$ are the sides of a triangle, then the probability $P(ax + by \ge c) = \frac{4}{\pi^2}\chi_2(x) + \frac{4}{\pi^2}\chi_2(y)$
Posting this question in MO since it is unanswered in MSE
Let $(a,b,c)$ be the side of a triangle. In its most general linear form, the triangle inequality can be expressed as: Does $ax + by \ge c$ ...
13
votes
1
answer
693
views
Gambler's ruin: The fair game is the longest
Consider a gambler who, in every trial of a game, wins or loses a dollar with
probability $p\in\left( 0,1\right) $ and $q=1-p$, respectively. Let his
initial capital be $z>0$ and let him play ...
13
votes
2
answers
879
views
The expected square of the determinant of a random row stochastic matrix
In this
question Anthony Quas asks about the expected absolute value of
the determinant of an $n\times n$ row stochastic matrix $A$, where
the rows are independently selected from the uniform ...
13
votes
1
answer
3k
views
What is the maximum-entropy distribution given mean, variance, skewness, and kurtosis?
$X\in \mathbb{R}$. Which distribution $P(X)$ has the highest possible entropy given its expected value, variance, skewness, and kurtosis? Is it an exponential family distribution of the form $P(X) \...
13
votes
2
answers
383
views
Comparing two measures on trees on $n$ vertices
A standard measure on trees on $n$ vertices is the Uniform Spanning Tree (UST) on the complete graph. This is the measure where every tree has equal probability, $1 / n^{n-2}$ by Cayley's formula.
...
13
votes
2
answers
3k
views
The probabilistic method - reference to less challenging questions
I am teaching a course in combinatorics and large part of it is dedicated to the probabilistic method especially in the case of graphs. The course is an undergraduate level (almost none of the ...
13
votes
4
answers
535
views
Alignment of random points
Whenever I draw randomly about ten points, I see that there will be always 3 points that are "almost" collinear. This observation leads me to considering the following questions:
Question 1: Suppose $...
13
votes
3
answers
1k
views
A property of unimodal sequences
It is well-known that $(-1)^j \sum_{i=0}^j (-1)^i\binom{n}{i} \geq 0$. This inequality can be used to prove Bonferroni's inequalities for example. Recently I noticed that a similar inequality applies ...
13
votes
1
answer
10k
views
KL divergence and mixture of Gaussians
Do we have an exact formula to compute the KL divergence between 2 mixtures of Gaussians (i.e convex combinations of a finite number of Gaussian distributions)?
If not exactly known, are there good ...
13
votes
2
answers
789
views
Geometric characterization of martingales
Recently I've read a paraphrasing from Ito saying that he sometimes thinks of martingales as geodesics in a very large dimensional manifold.
My question is, is there any research studying this idea?
...
13
votes
3
answers
1k
views
Random Reidemeister moves to unknot
Suppose one has a link diagram of the unknot, and applies random Reidemeister moves
until the unknot is reached.
Surely it requires an exponential number of moves, exponential in, say, the crossing ...
13
votes
1
answer
1k
views
How far can a particle travel from its origin if it exhibits self-avoiding Brownian motion in two-dimensions?
Let's say I have a point-like Brownian particle undergoing two-dimensional diffusion on an infinite plane with the caveat is that the particle can never return to a coordinate that it previously ...
13
votes
1
answer
2k
views
Counting subtrees of a random tree ("random Catalan numbers")
Given a rooted tree $T$ and an integer $k \geq 1$, let $N_k(T)$ be the number
of subtrees of $T$ containing the root and having exactly $k$ nodes (take $N_k(T)=0$ if $T$ has less than $k$ nodes).
...
13
votes
1
answer
564
views
Coincidences between average Catalan tableaux
There are Catalan number $C_n$ of standard Young tableaux of shape $(n,n)$, which we view as $2\times n$ matrices. Denote by $P_n$ the average of these matrices:
$$
P_n \, := \, \frac{1}{C_n} \, \...
13
votes
1
answer
1k
views
Does $P(X_1>X_2)$ and $P(X_1=X_2)$, where $X_1$ and $X_2$ are independent and Poisson distributed, uniquely determine the parameters?
Let $X_1$ and $X_2$ be independent Poisson distributed random variables with parameters $\lambda_1$ and $\lambda_2$, respectively.
Let $a = P(X_1 > X_2)$ and $b = P(X_1 = X_2)$.
Question: ...
13
votes
1
answer
3k
views
random walk and Brownian motion on Riemannian manifold
As we know, the random walk on $\mathbb{Z}/n$ will converge(in some sense) to the Brownian motion on $\mathbb{R}$ when $n\to\infty$. I would like to know is there some higher dimensional analogy ...
13
votes
4
answers
1k
views
Reference request: probability / ergodic theory without measure spaces
In his notes on free probability, Terence Tao describes a general approach to non-commutative probability which prioritizes the algebra of random variables above the sample space; I find this ...
13
votes
1
answer
654
views
Is the nearest walk to Brownian motion uniform?
Let $W:[0,1]\rightarrow\mathbb R$ be standard Brownian motion with $W(0)=0$.
Let $F_n$ denote the collection of all the $2^n$ many piecewise linear continuous functions $f:[0,1]\rightarrow\mathbb R$ ...
13
votes
2
answers
518
views
Asymptotics of a randomized Fibonacci sequence
Let $f(1)=f(2)=1$ and recursively define $f(n+1) = f(n) + f(i)$, where $i$ is chosen uniformly at random from $1,\ldots,n-1$. About how big should we expect $f(n)$ to be for $n$ large? We can examine ...
13
votes
1
answer
713
views
Identity involving the probability that a random walk stays below a curve
I'm looking for a direct proof of the following identity:
Let $W_n$ be a simple random walk with $W_0=0$. For all $x>0$ we have
$$
\lim _{N\to \infty} \sqrt{N} \cdot \mathbb P \Big( \forall n \le ...
13
votes
1
answer
484
views
A probability involving areas in a random pentagram inscribed in a circle: Is it really just $\frac12$?
This question was posted at MSE but was not answered.
The vertices of a pentagram are five uniformly random points on a circle. The areas of three consecutive triangular "petals" are $a,b,c$...
13
votes
1
answer
889
views
Probability that random nonnegative integer matrix is singular
Q. What is the probability that an $n \times n$ matrix, whose elements
are independent uniformly random integers in $\{0,1,\ldots,k\}$, is singular?
For example, for $n=3$ and $k=2$, the first ...
13
votes
1
answer
869
views
Lotteries, Turan's problem, and minimization of risk
Suppose I am a high-volume broker aiming to make some money on a state lottery. In this lottery, six balls are drawn from a population of (let's say) 50, without replacement. A ticket is a choice of ...
13
votes
1
answer
696
views
$\ell^1$-norm of eigenvectors of Erdős-Renyi Graphs
Setting. Let $G(n,p)$ denote the usual Erdős-Renyi (random) graphs. For each such graph there is an associated Laplacian matrix $L = D - A$ where $D$ collects the degrees on the diagonal and $A$ is ...
13
votes
1
answer
815
views
2/3 power law in the plane
I've recently come across a particular problem whose solution turns out to be a probability distribution given by $f(x) = \alpha \|x\|^{-2/3}$ in the unit disk in $\mathbb{R}^2$ and zero elsewhere (I ...
13
votes
2
answers
656
views
Random matrix with given singular values
Let $\sigma_1\geq\sigma_2\geq...\geq\sigma_n\geq0$ be any deterministic sequence of positive real numbers such that $\sum_{i=1}^n\sigma_i^2=1$. Let
$$D=diag\{\sigma_1,...,\sigma_n\}\in\mathbb{R}^{n\...