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
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 ...
Zur Luria's user avatar
  • 1,643
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 ...
martin's user avatar
  • 1,903
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 ...
Simd's user avatar
  • 3,377
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 ...
Louigi Addario-Berry's user avatar
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,...
Jean-Philippe Burelle's user avatar
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?
Gérard Lang's user avatar
  • 2,655
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$ ...
Benoît Kloeckner's user avatar
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 ...
kjetil b halvorsen's user avatar
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 ...
Xiaomi's user avatar
  • 231
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 ...
Joseph Turian's user avatar
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)$ ...
RadonNikodym's user avatar
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 ...
Dan's user avatar
  • 3,567
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,...
Denis Serre's user avatar
  • 52.3k
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 ...
Jiahao Chen's user avatar
  • 1,890
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 ...
Amir's user avatar
  • 303
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 ...
Antoine Levitt's user avatar
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 ...
Yaniv Tenenbaum Katan's user avatar
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 ...
Lviv Scottish Book's user avatar
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 ...
Anthony Quas's user avatar
  • 23.2k
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(...
Takirion's user avatar
  • 549
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 ...
Joseph O'Rourke's user avatar
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, ...
scaramouche's user avatar
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$ ...
Nilotpal Kanti Sinha's user avatar
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 ...
Paolo Leonetti's user avatar
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 ...
Richard Stanley's user avatar
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) \...
Falk's user avatar
  • 233
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. ...
Matthew Kahle's user avatar
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 $...
Minh-Toan's user avatar
  • 131
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 ...
Jose A Rodriguez's user avatar
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 ...
gradstudent's user avatar
  • 2,246
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? ...
ABIM's user avatar
  • 5,405
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 ...
Joseph O'Rourke's user avatar
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 ...
Rob Grey's user avatar
  • 599
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). ...
Louigi Addario-Berry's user avatar
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} \, \...
Igor Pak's user avatar
  • 17k
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: ...
svangen's user avatar
  • 326
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 ...
shu's user avatar
  • 1,111
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 ...
Qiaochu Yuan's user avatar
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$ ...
Bjørn Kjos-Hanssen's user avatar
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 ...
Christopher D. Long's user avatar
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 ...
Dor's user avatar
  • 723
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$...
Dan's user avatar
  • 3,567
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 ...
Joseph O'Rourke's user avatar
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 ...
JSE's user avatar
  • 19.2k
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 ...
Stefan Steinerberger's user avatar
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 ...
John Gunnar Carlsson's user avatar
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\...
neverevernever's user avatar

1
8 9
10
11 12
181