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,024 questions
12
votes
2
answers
3k
views
The Borel $\sigma$-algebra of the set of probability measures
Let $X$ be a compact metric space and $M(X)$ the set of all Borel probability measures on $X$.
It is know that $M(X)$ is a convex compact metric space endowed with the weak-* topology i.e.
$(\mu_n)_n \...
- 133
12
votes
1
answer
2k
views
Mean of i.i.d Random Variables With No Expected Value
Let $X$ be an integer-valued random variable and let $X_n$ be the sum of $n$ independent realizations of $X$. I would like to understand the behavior of $X_n/n$ for large $n$ in some cases where $X$ ...
- 23k
12
votes
4
answers
1k
views
Constructing Riemann maps using Brownian motion?
There's a relation between two-dimensional Brownian motion and conformal maps, see e.g. Thurston's answer to this question. Given two non-empty simply-connected domains $U$ and $V$ in the complex ...
- 524
12
votes
3
answers
891
views
Looking for at least one beautiful and not too technical result in asymptotic group theory
We have a student seminar devoted to the problems of asymptotic group theory with some connections to ergodic theory and measure theory in general. Each talk concerns one of the problems of this ...
12
votes
2
answers
2k
views
Can we do better than Azuma-Hoeffding when the variance is small?
The Azuma-Hoeffding Inequality says that if $X_1,X_2, \ldots$ is a martingale and the differences are bounded by constants, $\|X_i - X_{i-1}\| \le 1$ say, then we should not expect the difference $\|...
- 1,955
12
votes
2
answers
3k
views
The conditions in the definition of Brownian motion
A (standard, real-valued) Brownian motion $W = \{W(t): t \geq 0\}$ is commonly defined by the following properties: 1) $W(0) = 0$ a.s., 2) the process has independent increments, 3) for all $s,t \...
- 1,468
12
votes
1
answer
1k
views
Riesz–Markov–Kakutani representation theorem for compact non-Hausdorff spaces
Let $X$ be a compact Hausdorff topological space, and $\mathcal C^0 (X) = \{f:X\to\mathbb{R}; \ f \text{ is continuous }\}$. It is well known that for any bounded linear functional $\phi: \mathcal C^...
- 333
12
votes
3
answers
760
views
Asymptotics of functional of i.i.d. Rademacher random variables
Let $X_1,\ldots, X_n$ be i.i.d. Rademacher random variables. That is, $\operatorname{Pr}(X_i = 1) = \operatorname{Pr}(X_i = -1) = 1/2$. I was wondering if the following argument is true:
$$
\mathbb{E} ...
- 1,127
12
votes
1
answer
10k
views
Square root of normal distribution
Let $X$ and $Y$ be independent random variates with the same probability distribution, $P(x)$. Assuming that the product $Z=XY$ is a random variate with normal distribution, say $$f_Z(x) = \frac{1}{\...
- 377
12
votes
2
answers
1k
views
Should you bet in poker against Darth Vader?
This is a theoretical question about poker-type games. I'm not going to specify the rules. You can consider No Limit Texas Hold'em or some simple theoretical model, where each player holds a number ...
- 19k
12
votes
3
answers
383
views
Probability of $\ell_1$-norms of vertices of the rotated Hamming cube
Let $O$ be a $d$-dimensional rotation matrix (i.e., it has real entries and $OO^T = O^TO = I$). Let $\mathbf{x}$ be a uniformly random bitstring of length $d$, i.e., $\mathbf{x} \sim U(\{0,1\}^d)$. In ...
- 223
12
votes
1
answer
883
views
The dance marathon problem
In his book, "The Strange Logic of Random Graphs", Joel Spencer describes the "Dance Marathon" problem:
Imagine $n$ couples at a Dance Marathon. Each dance each couple remains ...
- 3,979
12
votes
2
answers
861
views
Can the Law of the Iterated Logarithm be strengthened?
http://en.wikipedia.org/wiki/Law_of_the_iterated_logarithm
.$\quad$1. Can the independence assumption be weakened, similar to this?
.$\quad$2. Can the identically distributed assumption be dropped/...
user5810
12
votes
1
answer
419
views
Coloring $K_n$ via edge-weight sums
This is a question inspired by
and tangential to "A Question on 1, 2 ,3 Conjecture"—and certainly
much easier!
Suppose one assigns a random edge weight among $\{1,2,3,\ldots,k\}$ to each
edge ...
- 151k
12
votes
3
answers
1k
views
Is there a simple inductive procedure for generating labeled trees uniformly at random, without direct recourse to Prüfer sequences?
Suppose you have a labeled tree $T$ on vertices $V=\lbrace 1,\ldots,n\rbrace$ that is drawn uniformly at random from the set of all $n^{n-2}$ such trees. I am seeking an $f$ satisfying the following ...
- 1,068
12
votes
1
answer
762
views
Wander distance of self-avoiding walk that backs out of culs-de-sac
Suppose a self-avoiding walk on $\mathbb{Z}^2$, with random steps each one unit long,
backs out of culs-de-sac, but retaining the lattice points on which it stepped
marked as unavailable for future ...
- 151k
12
votes
5
answers
3k
views
Properties preserved under passage to augmented filtration
Dear all,
generally speaking, my question is about which properties of a stochastic process are preserved when I skip from the original to the augmented filtration.
Recall that if $(\mathcal{F}_t)_{...
- 121
12
votes
1
answer
617
views
Mode of a sum of Bernoulli random variables
Let $S_n=\tau_1+\cdots+\tau_n$ be a sum of independent Bernoulli random variables such that $\mathbb{P}(\tau_i=1)=p_i$. Is it true that the mode of $S_n$ is either its mean rounded up or rounded down?
- 2,288
12
votes
1
answer
694
views
History of the Jaccard distance $d(A,B) = \mathbb P(\overline A\cup\overline B\mid A\cup B)$
I'm wondering where the relative probabilistic distance or Jaccard distance was first studied:
$$d(A,B) =\mathbb P(\overline A\cup\overline B\mid A\cup B)$$
where $\overline A$ is the complement of $A$...
- 24.8k
12
votes
1
answer
2k
views
Hardy spaces: analysis <---> martingales
Let $H^p$ be the Hardy space of analytic functions on the open unit disk $\mathbb{D}$: $f \in H^p$ if $f$ is analytic on $\mathbb{D}$ and $\sup_{r < 1} \int_0^{2\pi} |f(re^{i\theta})|^p d\theta <...
- 943
12
votes
2
answers
947
views
How rare are unholey permutations?
For $S\subset [n]:=\{1,2,\dotsc,n\}$, define $\delta(S)$ to be the number of $m\in S$ such that $m+1\notin S$.
Given a permutation $\pi$ of $[n]$, we define the holeyness $D(\pi)$ of $\pi$ as being $...
- 20.2k
12
votes
2
answers
3k
views
Is it fine to inquire about a paper that's been under review for around 9 months?
I have submitted a paper on applied probability in one of SIAM journals. The paper is under review for 9 months. I asked the editor 1 month ago about it, I was told that one review report has come and ...
12
votes
1
answer
295
views
On Sampling rank $r$ matrices
Sample $n^2$ integers $a_{11},\dots,a_{nn}$ in $\{-d,\dots,-1,0,1\dots,d\}$ uniformly.
What is the probability that the resulting matrix $[a_{ij}]$ has rank $r$?
Is there a nice parametrization of ...
- 13.9k
12
votes
3
answers
552
views
Estimate on currents in Cayley graphs
Take a Cayley graph $\Gamma$ (thought of as an electrical network with all edges having equal resistance) and break one edge $e$ and put a battery there. (Assume the graph has only one end* so that ...
- 4,432
12
votes
1
answer
4k
views
Karhunen–Loève approximation of Brownian motion and diffusions
The Karhunen–Loève theorem says that Brownian motion on the interval [0,1] can be represented as follows:
$W_t = \sum_{n=1}^\infty Z_n \frac{\sin((n-1/2)\pi t)}{(n-1/2)\pi},$
where $Z_n \sim \mathcal{...
- 1,666
12
votes
3
answers
1k
views
Expectation of the product of almost independent Gaussians
Let $X_ i$ be copies of the standard real Gaussian random variable $X$. Let $b$ be the expectation of $\log |X|$. Assume that the correlations $EX_ iX_ j$ are bounded by $\delta_ {|i-j|}$ in absolute ...
- 61.9k
12
votes
1
answer
400
views
Probability that random cubic polynomials meet in a square
Let $p_1(x)$ and $p_2(x)$ be cubic polynomials with
random coefficients in $[-1,1]$.
I wanted to compute the probability that $p_1$ and $p_2$
share at least one point within
the square $[-1,1]^2$.
Of ...
- 151k
12
votes
1
answer
1k
views
Entropy of edit distance
The edit or Levenshtein distance between two strings is the minimum number of single character insertions, deletions and substitutions to transform one string into another. If we take random binary ...
user32786
12
votes
1
answer
330
views
Convergence of an implicitly defined sequence of random variables
Let $\{X_n\}_{n\ge 1}$ be a sequence of independent identically distributed Poisson random variables with mean $\lambda^*$. Consider a sequence of random variables $\{\hat{\lambda}_{n}\}_{n\ge 1}$ ...
- 171
12
votes
1
answer
460
views
No limit shape for random Young diagrams under z-measure?
In their paper Random partitions and the Gamma kernel (Advances in Mathematics 194 (2005) 141–202), Borodin and Olshanski state that:
An important difference between the Plancherel measures and the ...
- 1,038
12
votes
1
answer
811
views
'Nonclassical' abstract Wiener space
Is it possible to construct an abstract Wiener space $(W,H,\mu)$ such that $C^{0,\frac{1}{2}}(\Omega)\subset H$ and $W$ is a normed function space such that the convergence in norm implies convergence ...
- 121
12
votes
2
answers
2k
views
Gluing Markov processes
I am looking for a reference on the gluing together of strong Markov processes to get a new one.
Here is an example of what I have in mind. Let $B^1, B^2, \ldots $ be independent one-dimensional ...
- 461
12
votes
0
answers
704
views
From biased coins (and nothing else) to biased coins
Background
We're given a coin that shows heads with an unknown probability, $\lambda$. The goal is to use that coin (and possibly also a fair coin) to build a "new" coin that shows heads ...
- 697
12
votes
0
answers
196
views
UMD constant of finite dimensional spaces
For a Banach space $B$, its one-sided Unconditional Martingale Difference (UMD) constant $C^-_p$ (for $p \in (1,\infty)$) is the smallest value such that for all $B$-valued martingale difference ...
- 408
12
votes
1
answer
628
views
A function with unexpectedly simple Legendre transformation
Let $I(x) = \frac{1}{2\pi} \int_{-2}^2 \sqrt{4-y^2}\ln|x-y|dy$. Then $I(x)$ is a concave function and
\begin{equation}
I(x)=
\begin{cases}
\frac{1}{4}x^2-\frac{1}{2}, &\text{if } |x|\leq2 \\
\...
- 1,608
12
votes
0
answers
490
views
Is this extension of Hoeffding's inequality known?
Question Overview:
Is it already known that, when using Hoeffding's inequality to lower bound the mean of i.i.d. random variables, you can replace the upper bound on the random variables with the ...
- 399
12
votes
0
answers
825
views
Eigenvalues of permutations of a real matrix: how complex can they be?
This is sort of complementary to this thread. I’ll repeat the definitions here:
For a matrix $M\in GL(n,\mathbb R)$, consider the $n!$ matrices obtained by permutations of the rows (say) of $M$ and ...
- 13.4k
12
votes
0
answers
1k
views
American put option pricing by "binomial trees"
I'm teaching a financial mathematics course and have found a fascinating (to me) numerical phenomenon and wonder if anyone has studied it, or knows anything similar.
I'll try and give a description ...
- 23.2k
11
votes
4
answers
2k
views
Is the function $e^{x^2/2} \Phi(x)$ monotone increasing?
Hello,
Here is an interesting problem. It looks elementary, but it has taken me some efforts without solving it. Let
$$
h(x) = e^{x^2/2} \Phi(x),\qquad \text{with}\quad \Phi(x):=\int_{-\infty}^x \...
- 1,649
11
votes
7
answers
29k
views
Resultant probability distribution when taking the cosine of gaussian distributed variable
I am trying to do a measurement uncertainty calculation. I have a gaussian distributed phase angle (theta) with a mean of 0 and standard deviation of 16.6666 micro radians. The variance is the ...
- 113
11
votes
4
answers
3k
views
What is the cover time of a random walk on a cube?
I can't quite figure this problem yet. There is an ant at one vertex of a cube. The ant goes from one vertex to another by choosing one of the neighboring vertices uniformly at random. What is the ...
- 241
11
votes
6
answers
5k
views
Secret Santa (expected no of cycles in a random permutation)
In a Secret Santa game, each of $n$ players puts their name into a hat and then each player picks a name from the hat, who they buy a Christmas present for. Obviously, if someone picks their own name ...
- 823
11
votes
5
answers
2k
views
Coin flipping and a recurrence relation
How can one solve the following recurrence relation?
$f(n) = 1 + \frac{1}{2^n} \sum_{k = 0}^n {{n}\choose{k}} f(k)$
$f(0) = 0$
As it happens, I can show $f(n) = \Theta(\log n)$ through other means (...
- 501
11
votes
4
answers
3k
views
When does a probability measure take all values in the unit interval?
Let $\mathbb{P}$ be a probability measure on some probability space $(\Omega,\mathcal{A})$. Are there conditions on the $\sigma$-algebra $\mathcal{A}$ such that for every real number $c\in [0,1]$ we ...
- 313
11
votes
4
answers
3k
views
Another colored balls puzzle
This is a puzzle a colleague asked me recently.
Imagine you have $n$ balls in a bag that are colored from $1$ to $n$. At each turn you take two balls at random out that have different colors and ...
- 131
11
votes
3
answers
4k
views
Maximum of a set of sums of iid random variables
Consider some probability distribution $D$ over non-negative reals with finite expectation $\mu$. Now for any positive $T$ consider sums of $T$ iid random variables drawn from $D$. A single sum of ...
- 501
11
votes
3
answers
858
views
Hitting time for two out of three random walk particles
I'm imagining a simple random walk on $\mathbb{Z}$ with three independent particles (maybe add laziness so they don't jump over each other). Suppose the particles are initially placed at, say, $-10$, $...
- 349
11
votes
2
answers
934
views
Decoupling inequality/counterexample
I am embarrassed to be stuck on this seemingly simple question.
Suppose that $X,Y$ are mean-zero real-valued random variables and $\tilde X,\tilde Y$ are their "independent copies": $\tilde ...
- 6,541
11
votes
4
answers
1k
views
A trick or a general technique? (Probabilistic Method)
Suppose we have some positive quantites $P$ and $Q$ which depend on some choices that we make, and we want to show that some choice makes the quotient $P/Q$ fall below some cool bound.
One idea is to ...
- 9,720
11
votes
2
answers
3k
views
Limit of distance between two random points in a unit $n$-cube
What is the limit, as $n \to \infty$, of the expected distance between two
points chosen uniformly at random within a unit edge-length hypercube
in $\mathbb{R}^n$?
For $n=1$, the average distance ...
- 151k