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
4
answers
4k
views
What are two independent, uniformly distributed random variables on the unit interval?
I have been dabbling in learning basic things about probability theory and (of course) being of the school of abstract nonsense I have tried to understand things in its language. I apologize if this ...
- 7,273
14
votes
4
answers
2k
views
Gaussian distributions as fixed points in Some distribution space
I'm taking a course on topology and probabily. Today, the professor remarked something along the lines of:
If you look at the space of probability distributions with $0$ mean and variance $1$, ...
- 935
14
votes
2
answers
1k
views
A random urn problem - do the faster duplicating balls always dominate?
There are $N \geq 1$ white balls and $1$ black ball in an (infinitely big) urn. Every turn, a ball is drawn from the urn uniformly at random. If a white ball is drawn, it is put back into the urn ...
- 6,213
14
votes
2
answers
2k
views
How many people have the same exact number of hairs?
Assume we look at $n\in\mathbb N$ people that can have anywhere between $1$ to $k\in\mathbb N$ hairs on their head.
Formally, I look at $n$ independent (in fact, this is not really true in real life ...
- 1,326
14
votes
2
answers
892
views
Do distance functionals separate probability measures?
Let $(\Omega,d)$ be a compact metric space and $\mathcal P(\Omega)$ its space of Borel probability measures. Let $D=\{ d_p\mid p\in\Omega\}$ where $d_p(x)=d(p,x)$ be the set of all "distance ...
- 459
14
votes
1
answer
8k
views
Expectation of square root of binomial r.v.
Let $X\sim B(n,p)$ denote a binomial random variable. Is there any approximation available for the quantity $E(\sqrt{X})$? Clearly Jensen's inequality holds, but rudimentary tooling around with ...
14
votes
2
answers
988
views
Properties of Some Random Graphs
Working in a problem the following family of graphs appears naturally. Consider the set $A_{n}=\{1,2,3,\ldots,n\}$ and let $\mathcal{C_{n}}$ be the set of all permutations of $A_{n}$ of order $n$ (...
- 3,626
14
votes
6
answers
2k
views
Density of numbers having large prime divisors (formalizing heuristic probability argument)
I want to prove that the set of natural numbers n having a prime divisor greater than $\sqrt{n}$ is positive.
I have a heuristic argument that this density should be $\log 2$, which is approximately ...
- 7,320
14
votes
1
answer
2k
views
A determinantal formula
In my research, I encounter the following formula which I believe is correct (checked for $n\le3$). Is it classical ? If so, what is a reference ?
I am given a real symmetric matrix
$$S:=\int Y(t)Y(t)...
- 52.3k
14
votes
3
answers
1k
views
On the number of consecutive divisors of an integer
Define for $n \in \mathbb{N}$ the function $$\tau_1(n):=\sum_{\substack{d|n, \\ d+1|n}}1,$$ i.e. the number of consecutive divisors of an integer. The average of $\tau_1(n)$ is $1$ since $$\sum_{n\leq ...
- 3,062
14
votes
3
answers
1k
views
Probability of coprime polynomials
Given positive integer $N$, we choose $m_1, m_2, n_1, n_2$ independently and with equal probabilities from $\{0,1,\ldots,N\}$, and let
$f_1 = x^{m_1} + (1+x)^{n_1}$ and $f_2 = x^{m_2} + (1+x)^{n_2}$ ...
- 54.2k
14
votes
2
answers
2k
views
A random walk on an infinite graph is recurrent iff ...?
Q. Is there a master theorem that can be used to determine whether or not
a simple random walk (choose a random neighboring vertex as the next step)
on a given infinite graph
leads to ...
- 151k
14
votes
3
answers
3k
views
Expected value of the minimum with limited independence
Imagine you sample $n$ number with replacement uniformly from the integers $1,\dots, n$. Let $X$ be the minimum of these samples. I am interested in $\mathbb{E}(X)$ but with a twist. All I know is ...
- 3,377
14
votes
4
answers
3k
views
A learning roadmap to the Schramm-Loewner evolution (SLE) for the complex analyst
I would like some good references to learn about the Schramm-Loewner evolution (SLE), for a complex analyst with no background in probability.
A quick google search gave a lot of references on SLE ...
- 2,154
14
votes
3
answers
907
views
Theorems like the Lovász Local Lemma?
The Lovász Local Lemma gives a probability bound in a context where there are many events that are "not quite" independent.
What other theorems exist in this genre? That is, what other theorems have ...
- 523
14
votes
3
answers
2k
views
Concentration bounds for sums of random variables of permutations
I'm trying to find theorems regarding random variables derived from sampling permutations, specifically concentration bounds.
As an example, let $X_i$ be the $\{0,1\}$-random variable that represents ...
- 539
14
votes
4
answers
2k
views
How long for a simple random walk to exceed $\sqrt{T}$?
Let $R_n$ be a simple random walk with $R_0 = 0$, and let $T$ be the smallest index such that $k\sqrt{T} < |R_T|$ for some positive $k$.
What is an expression for the probability distribution of $...
- 2,302
14
votes
1
answer
813
views
Large-n limit of the distribution of the normalized sum of Cauchy random variables
What is the large-n limit of a distribution of the following sample statistic:$$x\equiv\displaystyle\frac{\sum^{n}X_{i}}{\,\sqrt{\,\sum^{n}X_{i}^{2}\,}\,}$$ when sampling the Cauchy(0,1) distribution? ...
- 419
14
votes
3
answers
610
views
Union of random intervals with total length equal to infinity
Let $a_1,a_2,\dots$ be a sequence of positive numbers less than $1$, such that $$\sum_{n=1}^\infty a_i= \infty,$$ and $S^1 = \mathbb{R}/\mathbb{Z}$.
Suppose $I_1,I_2,\dots$ be random intervals with ...
- 4,484
14
votes
1
answer
3k
views
How is the "conformal prediction" conformal?
The question is clarified by Prof.V.Vovk. See his answer below for discussion.
Recently, early works of Gammerman, Vanpnik and Vovk[4] are rediscovered by Wasserman et.al[1] and proposed it as a ...
- 8,071
14
votes
2
answers
1k
views
Expected number of lines meeting four given lines or "what is 1.72..."
Given four random lines in $\mathbb{R}P^3$, how many lines intersect all of those lines?
In the recent paper Probabilistic Schubert Calculus, Peter Bürgisser and Antonio Lerario
discuss this question ...
- 10.7k
14
votes
1
answer
2k
views
Expected survival time in Russian Roulette not monotone?
Let $a, n$ be positive integers with $a < n$. A revolver with $n$ chambers is loaded with $a$ bullets, where the distribution is uniform among all $\binom{n}{a}$ possible choices of $a$ objects ...
- 6,213
14
votes
1
answer
2k
views
Prokhorov's theorem in non separable metric spaces
Recently, working in some calculations I needed to use the Prokhorov's theorem
about compactness for probability measures. However, a friend warned me that
I had not the hypotesis of separability ...
- 757
14
votes
1
answer
1k
views
Normal numbers, Liouville function, and the Riemann Hypothesis
This is a question about whether or not some number $\lambda^*$ is normal in base 2. More specifically, I am wondering if $\lambda^*$ is not normal. Proving it is normal would be next to impossible, ...
- 3,098
14
votes
1
answer
1k
views
A disc contains many random points. Each point is connected to its nearest neighbor. What is the expectation of average cluster size?
A disc contains $n$ independent uniformly distributed points. Each point is connected by a line segment to its nearest neighbor, forming clusters of connected points.
For example, here are $20$ random ...
- 3,567
14
votes
2
answers
1k
views
Error term for renewal function
Consider a sequence of independent uniform $[0,1]$ random variables, and for nonnegative real $t$, let $m(t)$ be the expected number of terms in the first partial sum that exceeds $t$. For instance it'...
- 5,492
14
votes
3
answers
9k
views
Solving a Rubik's cube via a series of randomly selected (quarter-turn) Singmaster moves
In July of 2010, Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge demonstrated (computationally) that a $3\times3\times3$ Rubik's cube, starting in an arbitrary configuration, can ...
- 173
14
votes
2
answers
783
views
Are two probability distributions uniquely constrained by the sum of their p-norms?
Let A, B and C be finitely supported probability distributions with at most d nonzero probabilities each. Now consider the following simultaneous equations using p-norms, for each value of p≥1, ...
- 2,649
14
votes
1
answer
1k
views
A Question on Random Matrices
Consider the following $n\times n$ random matrix $V_{n}$ where the $(p,q)$ entry is given by
$$
V_{n}(p,q):= \frac{1}{\sqrt{n}}\exp(2\pi i(p-1) x_{q})
$$
where $x_{1},x_{2},\ldots,x_{n}$ are iid ...
- 3,626
14
votes
1
answer
1k
views
Berry Esseen type result for probability density functions
Let $X_1, X_2, \cdots$ be i.i.d. random variables with $E(X_1) = 0, E(X_1^2) = \sigma^2 >0, E(|X_1|^3) = \rho < \infty$.
Let $Y_n = \frac{1}{n} \sum_{i=1}^n X_i$ and let us note $F_n$ (resp. $\...
14
votes
1
answer
4k
views
Is KL divergence $D(P||Q)$ strongly convex over $P$ in infinite dimension
By KL divergence I mean $D(P||Q) = \int dP \log(\frac{dP}{dQ})$. I am looking for the conditions under which this strong convexity is true and possible references. I could not find an answer for ...
- 193
14
votes
1
answer
2k
views
Why do we mainly integrate with respect to martingales?
Although my resarch focuses on PDEs (optimal transport, these days), I am currently trying to learn stochastic calculus and integration. I am just beginning in this topics, but I was wondering: why do ...
- 5,380
14
votes
1
answer
449
views
References for reasoning about the spectrum of a convex body?
By "spectrum of a convex body", I mean: start with a convex body $B$ in $\mathbb{R}^d$, then consider the corresponding $d \times d$ covariance matrix resulting from a uniform distribution over $B$ -- ...
- 143
14
votes
2
answers
319
views
Shortest path through $n^{1/3}$ points out of $n$
Say I sample $n$ points uniformly at random in the unit cube in $\mathbb{R}^3$, and then I look for the shortest path through $n^{1/3}$ of those points (rounding up, say). What happens to the length ...
- 141
14
votes
1
answer
440
views
Smallest $k$ so that $k$-wise independence guarantees a constant expected minimum
Imagine you sample $n$ numbers with replacement uniformly from the integers $1,\dots, n$ (we can assume $n$ is large). Let $X$ be the minimum of these samples. I am interested in $\mathbb{E}(X)$ but ...
- 3,377
14
votes
1
answer
417
views
Lipschitz property of the determinant
$\newcommand{\A}{\mathcal A}\newcommand{\Tr}{\operatorname{tr}}$For $c$ and $C$ such that $0<c<C<\infty$, let $\A_{d;c,C}$ denote the set of all symmetric positive-definite real $d\times d$ ...
- 128k
14
votes
3
answers
694
views
Probability to be the winner in a tournament
In a project in Game Theory we (Ayala Arad and Ariel Rubinstein) are stuck with the following "simple" question. We are sure of the conjecture but we failed to find a (hopefully simple) proof:
Let $...
- 141
14
votes
1
answer
2k
views
Combinatorial proof for the number of lattice paths that return to the axis only at times that are a multiple of 4
Consider lattice paths consisting of $2n$ steps, each of which is either $(1,1)$ or $(1,-1)$. The number of such lattice paths that return to the horizontal axis only at times that are a multiple of $...
- 3,283
14
votes
2
answers
962
views
The power of two random choices with pairwise independence
Throw $n$ balls into $n$ bins, and let $X_n$ be the max load. That is the number of balls in the fullest bin. It is known that if the balls are thrown uniformly and independently at random then $\...
- 3,377
14
votes
1
answer
579
views
How to roll a $p$
Let $p$ be a positive integer (which is not a power of $2$), and suppose we want to generate a number uniformly randomly in the set $\{ 0, 1, \dots , p-1 \}$ (to emulate a dice roll). We are given ...
- 12.4k
14
votes
2
answers
2k
views
Markov chains: invariant measures and explosion
The following seems like such an elementary question, but I didn't get anywhere with it.
Suppose you are considering a Markov chain in continuous time which is transient and has an invariant measure (...
14
votes
1
answer
995
views
Number guessing game with lying oracle
You are probably already familiar with the usual number guessing game. But for concreteness I restate it.
The usual game
The Oracle chooses a positive integer $n$ between 1 and 1024 (or any power of ...
- 39.1k
14
votes
1
answer
1k
views
Natural probability on integers
This is a follow-up to this classical question asked recently here: we know (e.g. using the second Borel-Cantelli Lemma) that no probability measure on $\mathbb{Z}$ has the property that $n\mathbb{Z}$ ...
- 14.4k
14
votes
1
answer
956
views
Partitioning the vertices of an n-cube with random hyperplane cuts
An evolutionary biologist asked me a question which boils down, at least in part, to what seems to me an interesting question of combinatorial/probabilistic geometry.
It is an old chestnut of a ...
- 19.2k
14
votes
1
answer
781
views
Perimeters of random-walk polygons
I have a random walk on $\mathbb{Z}^2$ that takes a step
with equal probability in the three directions that avoid
retracing the previous step.
The walk proceeds until it returns to a lattice point
...
- 151k
14
votes
1
answer
2k
views
surprisingly difficult filtration problem
I am interested in a proof of the following statement which seems intuitive, but is somehow really tricky:
Let $X$ be a stochastic process and let $(\mathcal{F}(t) : t \geq 0)$ be the filtration ...
- 473
14
votes
2
answers
2k
views
Is the conditional expectation a contraction in weak $\mathbb L^p$ spaces?
Let $(\Omega,\mathcal F,\mu)$ be a probability space. It is well-known that if $\mathcal A$ is a sub-$\sigma$-algebra of $\mathcal F$, $p\geqslant 1$ and $X$ is an element of $\mathbb L^p$ which takes ...
- 3,968
14
votes
2
answers
2k
views
What is the maximum diameter of $N$ steps of a random walk?
Since probability is quite far away from my daily buisiness, please forgive me if my use of terminology is wrong or the question is too trivial. However, I was not able to find the right keyword to ...
- 12.7k
14
votes
0
answers
718
views
Lower bounds on analytic functions connected to Fox H
The question is related to the one I asked before and never got an answer to. Fourier transform of $f_a(x)= a^{-2}\exp(-|x|^a)$, $a \in (0,2)$, is decreasing in $a$ . I need to demonstrate that the ...
- 178
14
votes
0
answers
358
views
What is the asymptotic dynamics of the winning position in this game?
$n$ players indexed $1,2,...,n$ play a game of mock duel. The rules are simple: starting from player $1$, each player takes turns to act in the order $1,2,...,n,1,2,...$. In his turn, a player ...
- 2,619