Theory and applications of probability and stochastic processes: e.g. central limit theorems, large deviations, stochastic differential equations, models from statistical mechanics, queuing theory.

learn more… | top users | synonyms (1)

3
votes
0answers
188 views

Maximization of a total variation distance subject to another total variation distance in Markov chain

Suppose two dependent random variables $X$ and $V$ from finite alphabets $\mathcal{V}$ and $\mathcal{X}$ with known joint and marginal distributions are given. Let $P_{XV}$ and $P_X$ and $P_V$ are the ...
36
votes
14answers
30k views

If you break a stick at two points chosen uniformly, the probability the three resulting sticks form a triangle is 1/4. Is there a nice proof of this?

There is a standard problem in elementary probability that goes as follows. Consider a stick of length 1. Pick two points uniformly at random on the stick, and break the stick at those points. What ...
95
votes
10answers
11k views

Is there an introduction to probability theory from a structuralist/categorical perspective?

The title really is the question, but allow me to explain. I am a pure mathematician working outside of probability theory, but the concepts and techniques of probability theory (in the sense of ...
219
votes
15answers
31k views

Why do roots of polynomials tend to have absolute value close to 1?

While playing around with Mathematica I noticed that most polynomials with real coefficients seem to have most complex zeroes very near the unit circle. For instance, if we plot all the roots of a ...
32
votes
6answers
3k views

Geometric / physical / probabilistic interpretations of Riemann zeta(n>1)?

What are some physical, geometric, or probabilistic interpretations of the values of the Riemann zeta function at the positive integers greater than one? I've found some examples: 1) In MO-Q111339 ...
34
votes
1answer
3k views

Probability that a stick randomly broken in five places can form a tetrahedron

The following problem was brought to my attention by a doctoral dissertation on Mathematics Education, but - as far as I know - the solution remains unknown. I have already asked this question on ...
11
votes
4answers
3k views

Is there a simple way to compute the number of ways to write a positive integer as the sum of three squares?

It's a standard theorem that the number of ways to write a positive integer N as the sum of two squares is given by four times the difference between its number of divisors which are congruent to 1 ...
19
votes
3answers
1k views

Probabilities in a riddle involving axiom of choice

The question is about a modification of the following riddle (you can think about it before reading the answer if you like riddles, but that's not the point of my question): The Riddle: We assume ...
2
votes
1answer
203 views

Probability a Brownian particle with an exponentially distributed lifetime hits a sphere before vanishing

Imagine I have a point source $p_0 = (x_0,y_0,z_0)$ that releases a point-like Brownian particle with a lifetime given by an exponentially distributed rate parameter $\lambda$. When the particle's ...
57
votes
17answers
42k views

Google question: In a country in which people only want boys [closed]

Hi all! Google published recently questions that are asked to candidates on interviews. One of them caused very very hot debates in our company and we're unsure where the truth is. The question is: ...
27
votes
2answers
1k views

The probability for a symmetric matrix to be positive definite

Let me give a reasonable model for the question in the title. In ${\rm Sym}_n({\mathbb R})$, the positive definite matrices form a convex cone $S_n^+$. The probability I have in mind is the ratio ...
21
votes
4answers
1k views

Distribution of roots of complex polynomials

I generated random quadratic and cubic polynomials with coefficients in $\mathbb{C}$ uniformly distributed in the unit disk $|z| \le 1$. The distribution of the roots of 10000 of these polynomials are ...
11
votes
2answers
392 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 ...
10
votes
3answers
960 views

Expected second moment for random points on a circle

Let $S$ be a circle with unit circumference. Suppose that $n$ random points are chosen independently uniformly from $S$; choosing one arbitrarily as $x_1$, label the rest $x_2, \dots, x_n$ in ...
22
votes
1answer
2k views

Expected halting time for “The 2^n Game” (aka 2048) — with random moves

Recently I encountered an online flash game that features an m-by-m grid and input from the directional pad (up, down, left, right). At any point in the game, the grid contains numbers ('blocks') from ...
9
votes
1answer
856 views

Has anyone seen this series?

I come across the following infinite series. $$ \sum_{n=1}^{\infty} \frac{t^n}{n!\: n^{a}}, \quad\text{for $t>0$ and $a>0$}. $$ In particular, I am interested in the case where $a=1/4$. ...
10
votes
10answers
3k views

A problem of an infinite number of balls and an urn [closed]

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 ...
6
votes
4answers
2k views

Mean minimum distance for N random points on a unit square (plane)

A previously posted question "mean minimum distance for N random points on a one-dimensional line" produced an elegant answer: for a line of length L, the expected minimum distance (between random ...
5
votes
2answers
218 views

Anticoncentration of the convolution of two characteristic functions

Edit: This is a question related to my other post, stated in a much more concrete way I think. I am interested in anything (ideas, references) related to the following problem: Suppose that $A ...
7
votes
1answer
192 views

The time to drift a binary string from one state to another via deterministic selection of two possible random bit mutation procedures

I have some length $L$ binary string consisting of an ordered array of bits: $(b_1, b_2, ..., b_{L})$, where all bit values $b_i$ are originally set to zero. I'd like a particular set of $n$ bits to ...
2
votes
1answer
384 views

Asymptotic behavior of max of chi-squared distribution

Suppose $X_{\max}$ is the maximum in a sequence $X_1,X_2,\ldots,X_n$ where each $X_i\sim\chi^2_k$ is an i.i.d. chi-squared random variable with $k$ degrees of freedom. Since chi squared distribution ...
1
vote
1answer
118 views

Gibbs sampler with linear constraints

My problem concerns the estimation of truncated multivariate normal distributions under constraints. Let $X_1$ and $X_2$ two random variables following normal distributions ...
5
votes
1answer
530 views

Publishing an elementary proof of a less-general and less-useful version of a classic result?

Background Let $X_t$ be a stochastic process on the state space {Working, Broken}. Let $U$ be the cumulative sojourn Working during an interval $[0,\tau]$ (the process's uptime). It is well-known ...
4
votes
2answers
193 views

Brownian motion and hitting a Quadrilateral

I want to compute the hitting probability of a bounded plane by a Brownian motion starting at the origin. In other words, given the coordinates of a quadrilateral A , can we compute ...
3
votes
1answer
229 views

Quotients of standard Borel spaces

Let $X$ and $Y$ be standard Borel spaces: topological spaces homeomorphic to Borel subsets of complete metric spaces. Given a surjective Borel map $f:X\to Y$, we get an equivalence relation ...
82
votes
25answers
23k views

What is convolution intuitively?

If random variable $X$ has a probability distribution of $f(x)$ and random variable $Y$ has a probability distribution $g(x)$ then $(f*g)(x)$, the convolution of $f$ and $g$, is the probability ...
57
votes
20answers
7k views

Probabilistic Proofs of Analytic Facts

What are some interesting examples of probabilistic reasoning to establish results that would traditionally be considered analysis? What I mean by "probabilistic reasoning" is that the approach should ...
53
votes
9answers
7k views

How is it that you can guess if one of a pair of random numbers is larger with probability > 1/2?

My apologies if this is too elementary, but it's been years since I heard of this paradox and I've never heard a satisfactory explanation. I've already tried it on my fair share of math Ph.D.'s, and ...
45
votes
5answers
2k views

Random manifolds

In the world of real algebraic geometry there are natural probabilistic questions one can ask: you can make sense of a random hypersurface of degree d in some projective space and ask about its ...
15
votes
5answers
3k views

What mathematical treatment is there on the renormalization group flow in a space of Lagrangians?

What mathematical treatment is there on the renormalization group flow in a space of Lagrangians?
20
votes
6answers
5k views

A balls-and-colours problem

A box contains n balls coloured 1 to n. Each time you pick two balls from the bin - the first ball and the second ball, both uniformly at random and you paint the second ball with the colour of the ...
21
votes
1answer
2k views

When should we expect Tracy-Widom ?

The Tracy-Widom law describes, among other things, the fluctuations of maximal eigenvalues of many random large matrix models. Because of its universal character, it obtained his position on the ...
34
votes
3answers
3k views

the following inequality is true,but I can't prove it

The inequality is \begin{equation*} \sum_{k=1}^{2d}\left(1-\frac{1}{2d+2-k}\right)\frac{d^k}{k!}>e^d\left(1-\frac{1}{d}\right) \end{equation*} for all integer $d\geq 1$. I use computer to verify ...
21
votes
2answers
941 views

Drawing natural numbers without replacement.

Suppose we start with an initial probability distribution on $\mathbb{N}$ that gives positive probability to each $n$. Let's call this random variable $X_1$ so we have $P(X_1=n)=p_{1,n}>0$ for all ...
20
votes
5answers
2k views

A random walk with uniformly distributed steps

The following problem has bothered me for a long time. Let us imagine a point on the real axis. At the beginning, it is located at point $O$. Then it will "walk" on the real axis randomly in the ...
18
votes
6answers
1k views

Measures of non-abelian-ness

Let $G$ be a finite non-abelian group of $n$ elements. I would like a measure that intuitively captures the extent to which $G$ is non-commutative. One easy measure is a count of the non-commutative ...
16
votes
5answers
2k views

Brownian motion and spheres

Consider a Brownian motion on $[0;1]$. A (finite) discrete approximation of this Brownian motion consists of $N$ iid Gaussian random variables $\Delta W_i$ of variance $\frac{1}{N}$: $$ ...
30
votes
1answer
2k views

An Entropy Inequality

Let $X,Y$ be probability measures on $\{1,2,\dots,n\}$, and set $K=\sum_i\sqrt{X(i)Y(i)}$ so that $Z:=\frac{1}{K}\sqrt{XY}$ is also a probability measure on $\{1,2,\dots,n\}$. How can we prove the ...
27
votes
3answers
1k views

Random knot on six vertices

This question is inspired by Joseph O'Rourke's beautiful question on random knots. Choose an random ordered 6-tuple of points on the unit sphere in $\mathbf{R}^3$, and form a knot by connecting ...
16
votes
2answers
672 views

Persistent homology of Gaussian Fields in Euclidean space

If you generate points in $\mathbb R^n$ via a process that respects a Gaussian normal distribution, then compute the persistent homology / barcodes, to my eye something fairly regular seems to be ...
31
votes
5answers
4k views

Heuristically false conjectures

I was very surprised when I first encountered the Mertens conjecture. Define $$ M(n) = \sum_{k=1}^n \mu(k) $$ The Mertens conjecture was that $|M(n)| < \sqrt{n}$ for $n>1$, in contrast to the ...
27
votes
2answers
792 views

Shortest path through $\sqrt{n}$ points out of $n$

Say I sample $n$ points uniformly at random in the unit square, and then I look for the shortest path through $\sqrt{n}$ of those points (rounding up, say). What happens to the length of this path as ...
16
votes
2answers
1k views

The Bruss-Yor conjecture about an iterated integral

Is the sequence $$w_n=n! \int_0^{1/2} \int_{x_1}^{2/3} \cdots\int_{x_{n-2}}^{\frac{n-1}{n}} \int_{\frac{n}{n+1}}^1 dx_n dx_{n-1} \cdots dx_1$$ increasing for $n\ge 3$? This is a conjecture of F. ...
7
votes
2answers
483 views

What is the tropical Robinson-Schensted-Knuth correspondence?

And what are it's applications? A conceptual explanation would be great! Is there an expository note about this somewhere? Some references have already appeared in the answers and comments below. To ...
48
votes
9answers
7k views

Does War have infinite expected length?

My question concerns the (completely deterministic) card game known as War, played by seven-year-olds everywhere, such as my son Horatio, and sometimes also by others, such as their fathers. The ...
40
votes
4answers
3k views

Connectivity of the Erdős–Rényi random graph

It is well-known that if $\omega=\omega(n)$ is any function such that $\omega \to \infty$ as $n \to \infty$, and if $p \ge (\log{n}+\omega) / n$ then the Erdős–Rényi random graph $G(n,p)$ is ...
14
votes
3answers
971 views

Not-lonely runners

The lonely runner conjecture has several formulations. They all involve a number $n$ runners running on a circular track, each with a different speeds, and the conjecture is that each runner is ...
13
votes
1answer
557 views

Randomly switching street lights, in a square city

This is a combinatorics-probability question, best stated however in "recreational" terms. Imagine a $N\times N$ city, meaning that we have $N$ horizontal streets, and $N$ vertical streets. At each ...
11
votes
3answers
7k views

Maximum of Gaussian Random Variables

Let $x_1,x_2,…,x_n$ be zero mean Gaussian random variables with covariance matrix $\Sigma=(\sigma_{ij})_{1\leq i,j\leq n}$. Let $m$ be the maximum of the random variables $x_{i}$ $$ ...
7
votes
3answers
2k views

randomness in nature [closed]

What is the explanation of the apparent randomness of high-level phenomena in nature? For example the distribution of females vs. males in a population (I am referring to randomness in terms of the ...