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
13
votes
1
answer
736
views
Idempotent measures on the free binary system?
Let $(S,*)$ be the free (non associative) binary system on one generator (so $S$ is just the set of terms in $*$ and $1$). There is an extension of $*$ to the space $P(S)$ of finitely additive ...
- 3,547
13
votes
2
answers
398
views
Expected sorting time of random permutation using random comparators
In sorting networks, a comparator of positions $i < j$ is an operator which takes a permutation, checks if $p_i > p_j$, and if it is the case, swaps $p_i$ and $p_j$.
Using this, we can define ...
- 3,319
13
votes
1
answer
3k
views
Does this metric have an official name? Lévy metric? Ky Fan metric?
Let $X$ and $Y$ be random variables taking values in a separable metric space $(S,d)$. The metric I have in mind is
$$\rho(X,Y) = \mathbb{E}[\min\{d(X,Y),1\}]$$
if $X$ and $Y$ take values in the a ...
- 6,287
13
votes
0
answers
711
views
Minimizing total variation under constraint
For $p\in[0,1]$, we write $\mathrm{Ber}(p)$
to denote the Bernoulli measure on $\{0,1\}$;
that is, $\mathrm{Ber}(p)(0)=1-p$,
$\mathrm{Ber}(p)(1)=p$.
For $n\in\mathbb{N}$ and $p=(p_1,\ldots,p_n)\in[0,1]...
- 6,541
13
votes
0
answers
882
views
Arguments against Freiling's argument against Continuum Hypothesis
Freiling's axiom of symmetry ($\sf AS$) is known as a justification for falsity of Continuum Hypothesis. Freiling in his 1986 paper, Axioms of symmetry: throwing darts at the real number line, ...
13
votes
0
answers
412
views
Transitivity of balanced mass transport in Z
Given two atomic measures $\mu$ and $\nu$ on $\mathbb{Z}$, write $\mu \sim \nu$ iff there exist countable decompositions $\mu = \mu_1 + \mu_2 + \cdots$ and $\nu = \nu_1 + \nu_2 + \cdots$ along with ...
- 19.7k
13
votes
0
answers
509
views
First passage percolation on a random geometric graph in the large connectivity limit
Let $V_\rho\subset\mathbb{R}^2$ be a point set in the plane obtained from a Poisson process of density $\rho$. The random geometric graph $G_\rho$ is obtained from $V_\rho$ by connecting points that ...
- 3,927
13
votes
0
answers
1k
views
Constructive aspects of Caratheodory's theorem in convex analysis
Let me paraphrase Caratheodory's theorem in a probabilistic setup:
Let $X$ be a real-valued random variable. For $k = 1, \ldots, m$, let $f_k: \mathbb{R} \to \mathbb{R}$ be a continuous function such ...
- 1,839
12
votes
12
answers
2k
views
What are fun elementary subjects in probability?
I have to read several lectures on probability or applications of probability for high school students (of high level). There is no necessary part I must lecture, that is, my aim is just advertisement....
12
votes
4
answers
2k
views
Throwing a fair die until most recent roll is smaller than previous one
I roll a fair die with $n>1$ sides until the most recent roll is smaller than the previous one. Let $E_n$ be the expected number of rolls. Do we have $\lim_{n\to\infty} E_n < \infty$? If not, ...
- 48.9k
12
votes
3
answers
3k
views
Area Enclosed by the Convex Hull of a Set of Random Points
Consider $n$ points generated randomly and uniformly on a unit square. What is the expected value of the area (as a function of $n$) enclosed by the convex hull of the set of points?
- 123
12
votes
3
answers
5k
views
Sigma algebra without atoms ?
I'm looking for an example of a set S, and a sigma algebra on it, which has no atoms.
Motivation: It seems to me that a lot of definitions in probability and stochastic processes - conditional ...
- 581
12
votes
5
answers
1k
views
What is hidden in Hidden Markov Models? [closed]
Why the word "hidden" present in hidden markov model? What exactly is hidden.
Whatever is hidden in HMM isn't it hidden in normal Markov Models?
- 139
12
votes
2
answers
820
views
Size of largest square divisor of a random integer
Let $x$ be an integer picked uniformly at random from $1 \ldots N$. Write $x = r^2 t$ where $t$ is square-free. How does the expected value of $r$ scale with $N$? Is anything known about the variance ...
- 1,703
12
votes
2
answers
3k
views
Does there exist an event independent of a given sigma-algebra?
The following question came up in a discussion with my advisor:
Let $(\Omega, \mathcal F, \mathbb P)$ be a non-trivial probability space, and suppose that $\mathcal G$ is a proper sub-$\sigma$-...
- 8,512
12
votes
4
answers
4k
views
Mixtures of Gaussian distributions dense in distributions?
It seems that a mixture of Gaussians can approach any probability distribution, as the number of mixture components approaches infinity. Is this true? And if so, is it precise and correct to say ...
- 141
12
votes
4
answers
4k
views
Tail bound for Poisson random variable
Is the following fact about Poisson random variables true?
For any $\lambda \in (0,1)$ and integer $k > 0$, if $X$ is a Poisson random variable with mean $k \lambda$, then $\Pr(X < k) \geq e^{...
- 785
12
votes
3
answers
1k
views
A Modern Proof of Erdos and Renyi's 1959 Random Graph Paper?
In their paper, Erdos and Renyi consider a random graph with a fixed number of edges, as opposed to the more modern approach of adding each edge independently with probability $p$. From what I ...
- 470
12
votes
3
answers
1k
views
Correlations in last-passage percolation
Consider the last passage percolation model on $\mathbb{Z}^2$ with, say, geometric weights on each edge. By a landmark result of Johansson (http://arxiv.org/abs/math/9903134), we know that if $T_n(\...
12
votes
4
answers
3k
views
What structure is needed to define a Gaussian distribution on a given space?
In most textbooks, the normal distribution is defined on $\mathbb{R}^n$ by specifying its probability density function. This works perfectly well, but it isn't really amenable to generalisation.
I'm ...
- 1,666
12
votes
2
answers
2k
views
What is the probability a random Turing machine is isomorphic to a DFA?
This is a sort of Chaitin/Omega constant type question, and so I do not expect this probability to be computable to arbitrary precision. However, it is also a very practical thing to know from the ...
- 2,392
12
votes
3
answers
5k
views
What are Central Limit Theorems and why are they called so?
I know two opinions:
1) "Central" means "very important" (as it was central problem in probability for many decades), and CLT is a statement about Gaussian limit distribution. If the limit ...
- 109k
12
votes
3
answers
2k
views
Looking for sufficient conditions for positive Fourier transforms
I am looking for some sufficient conditions for an even, continuous, nonnegative, non-increasing, non-convex function to be non-negative definite. In other words
$$
\int_0^\infty f(x)\cos(x\omega) \, ...
- 178
12
votes
1
answer
5k
views
Martingales in both discrete and continuous setting
I am wondering, polynomials like
$S_n^4-6n S_n^2+3n^2+2n$ for $$S_n=\sum_{i=1}^n{X_i}$$ where $$\mathbb{P}(X_i=1)=\mathbb{P}(X_i=-1)=\frac{1}{2}$$ is a martingale (under the conventional filtration). ...
- 255
12
votes
1
answer
789
views
Lattice random walk under gravity
Suppose a random walk on $\mathbb{Z}^2$ takes a step left or right with
probability $\frac{1}{4}$, but up with probability $\frac{1}{2} p$
and down with probability $\frac{1}{2} (1-p)$, where $p \in [...
- 151k
12
votes
3
answers
3k
views
Gaussian distribution, maximum entropy and the heat equation
I have asked this question on MathSE, but I got no replies, so I thought of trying here.
Consider the Gaussian distribution on $\mathbb{R}$ with mean $m$ and variance $t=\sigma^2$. This has the ...
- 577
12
votes
2
answers
2k
views
Is it ever unnecessary to mathematically formalize a concept?
From my understanding, mathematics sometimes gives rise to new physical/tangible laws and the converse is also true. In particular, physical phenomena give rise to new mathematics.
In all of the cases ...
- 131
12
votes
6
answers
3k
views
Marginal density of uniform spherical distribution
Suppose that $X$ is distributed uniformly in the scaled $n$-sphere $\sqrt{n} \mathbf{S}^{n-1} \subset \mathbf{R}^n$. Then apparently the distribution of $(X_1, \dots, X_k)$, the first $k < n$ ...
- 420
12
votes
4
answers
2k
views
Convex combination iid Bernoulli random variables
I'm looking for a lower bound for the probability that an arbitrary convex combination of iid Bernoulli (p) random variables is at least p. My guess is p/k (for some constant k; k must be at least e, ...
- 947
12
votes
2
answers
928
views
The metric of the expected difference of random variables
Suppose we have a set of independent random variables $X_1,\ldots,X_n$ over $\mathbb{R}$.
It is easy to see that
$$d_{ij}=E[|X_i-X_j|]$$
satisfy the triangle inequality.
Is there any study of such ...
- 401
12
votes
3
answers
1k
views
Connections between martingales and Fourier analysis
I have had this strange feeling recently that somehow, the theory of martingales we study in probability, and the theory of Fourier analysis are very alike. But I am not able to formalize my thoughts.
...
- 319
12
votes
3
answers
549
views
A probabilistic angle inequality
Conjecture: There is a universal constant $c$ such that for any fixed nonzero real vector $q$ of any dimension $n$ and any random vector $p$ of the same dimension $n$ with independent components ...
- 3,873
12
votes
3
answers
2k
views
How to efficiently sample uniformly from the set of $p$-partitions of an $n$-set?
Let $n,p \in \mathbb{N}_+$ with $p \leq n.$ Let $\mathcal{P}$ denote the set of partitions of $\{1, \ldots, n\}$ into $p$ nonempty sets. How can I efficiently sample uniformly from $\mathcal{P}$?
- 922
12
votes
3
answers
870
views
Measure theory in nuclear spaces
Much of the literature on measure theory in linear spaces focuses on the case of normed linear spaces (e.g., the outstanding book by Vakhania, or its sequel). However, nuclear linear spaces "as far ...
- 8,512
12
votes
2
answers
997
views
Is there a percolation threshold in the hard discs model?
Take a random configuration of $n$ non-overlapping discs of radius $r$ in the unit square $[0,1]^2$. (You could think of this as taking $n$ points uniform randomly in $[r,1-r]^2$ and then restricting ...
- 7,857
12
votes
3
answers
911
views
Expected number of compositions needed to get constant function
This is somewhat inspired by Factoring a function from a finite set to itself.
Fix natural number $n$ and let $[n] := \{1,2,\ldots,n\}$. Set $g_0 \colon [n]\to [n]$ to be the identity, and for $i \geq ...
- 24.2k
12
votes
3
answers
4k
views
How many proofs of the Polya's recurrent theorem are there?
Polya's famous theorem states that a simple random walk on $\mathbb{Z}^d$ is transient if $d>2$ and recurrent if $d=1,2$. This theorem is included in almost every textbook on probability theory.
...
- 121
12
votes
1
answer
2k
views
Limit of distance between two random points in a unit-radius $n$-sphere
This is a companion contrast to the earlier analogous question for unit $n$-cubes,
where the answer (provided by several respondents) is $\infty$ .
What is the limit, as $n \to \infty$, of the ...
- 151k
12
votes
3
answers
2k
views
Compactness of the set of densities of equivalent martingale measures
Consider an incomplete market $(\Omega,\mathcal F,\mathbb P)$ driven by a semimartingale $S=(S_t)_{t\in[0,T]}$. Under the no free lunch under vanishing risk (NFLVR) assumption, the set $\mathcal P^\...
- 243
12
votes
2
answers
2k
views
Convex hull of $k$ random points
Suppose we have $k$ realizations of a random variable uniformly distributed over the unit cube $[0,1]^n$.
What is the probability that their convex hull has all of the $k$ points as extreme points?
...
- 413
12
votes
2
answers
812
views
Inequality in Gaussian space -- possibly provable by rearrangement?
The following problem arose for my collaborators and me when studying the computational complexity of the Maximum-Cut problem.
Let $f : \mathbb{R} \to \mathbb{R}$ be an odd function. Let $\rho \in [...
- 6,694
12
votes
3
answers
1k
views
How to sample a uniform random polyomino?
A polyomino is formed by joining finitely many unit squares edge to edge. It may be regarded as a finite subset of the regular square tiling with a connected interior. In particular, for us, ...
- 7,857
12
votes
3
answers
666
views
An "inchworm-like" random walk on an integer interval
Imagine I place $k$ stones on an infinite one-dimensional integer interval $Z$ s.t. no stone is more than some distance $d$ from any other stone. For example, if $d=1$ and $k = 5$, we might place the ...
- 121
12
votes
2
answers
2k
views
Probability of having a "perfect" game of Set
The card game Set has very simple rules (see here for rules), and it has prompted mathematicians to ask several questions. I will describe one of these questions. When the game ends, there are usually ...
- 121
12
votes
3
answers
782
views
Connectedness of random distance graph on integers
This is not my field, a friend needs the answer for the following question. Suppose we have a decreasing probability function, $p: N \rightarrow [0,1]$ such that $sum_n p(n) = \infty$. Take the graph ...
- 19k
12
votes
3
answers
8k
views
Constructing Bernoulli random variables with prescribed correlation
For which $n \times n$ correlation matrix $C$ can one construct Bernoulli random variables $(B_1, \ldots, B_n)$ with correlation $C$ ?
Following the approach described in this MO thread, one can ...
12
votes
1
answer
525
views
An inequality about unit vector orthogonal to $(1,1,...,1)$
Does there exist a constant $\alpha>0$ such that the following holds?
$$\liminf_{n\to\infty}\inf_{x\in\mathbb{R}^n, \sum_{i=1}^nx_i^2=1, \sum_{i=1}^nx_i=0}\frac{\sum_{i<j, |i-j|\leq\frac{n}{4}}(...
- 1,495
12
votes
2
answers
406
views
Does asymmetric fraction of finite groups tend to $0$?
Let’s define asymmetric fraction of a finite group $G$ as the number $$\mathrm{af}(G) = \frac{|\{(g, a) \in G \times \mathrm{Aut}(G)\mid a(g) = g\}|}{|G|\cdot|\mathrm{Aut}(G)|}.$$ Equivalently it can ...
- 2,618
12
votes
2
answers
1k
views
lower-bound for $Pr[X\geq EX]$
Given n random variables, $X_1, ..., X_n$, each takes value 0 or $a_i \in[0, 1]$. $X = \sum_{i=1}^n X_i$ and $EX \geq 1$ is the expected value of $X$. Can we get a lower-bound for $Pr[X \geq EX]$? It ...
- 121
12
votes
3
answers
4k
views
How to explain "Feller process" to an undergraduate student?
I had to explain in informal terms what a Feller process was, to undergraduate students who understand Markov property, Poisson processes and such. It was easy to define Levy process as generalisation ...
- 519