Skip to main content

All Questions

Filter by
Sorted by
Tagged with
91 votes
8 answers
16k views

Is there a natural random process that is rigorously known to produce Zipf's law?

Zipf's law is the empirical observation that in many real-life populations of $n$ objects, the $k^\text{th}$ largest object has size proportional to $1/k$, at least for $k$ significantly smaller than $...
Terry Tao's user avatar
  • 114k
24 votes
2 answers
1k 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 $...
HMPanzo's user avatar
  • 551
21 votes
3 answers
5k views

James-Stein phenomenon: What does it mean that a James-Stein estimator beats least squares estimator?

Background James-Stein estimator and Stein's phenomenon, as described in Wikipedia are rather counterintuitive and amazing. It is claimed that if one wants to estimate the mean $\Theta$ of Gaussian ...
Alexander Chervov's user avatar
15 votes
1 answer
1k views

Table with the most seated customers in Chinese restaurant process

Suppose we have some initial configuration of people seated at some tables. We start taking new customers and seat them following Chinese restaurant process. Is there some known work on finding the ...
Stakhanov's user avatar
  • 151
11 votes
2 answers
78k views

Coin pusher game

While doing laundry at my local laundromat, I saw a coin pusher game. Below is a picture, and here is a video depicting how it works (disregard non-coins). Essentially, one has a distribution of ...
Alex R.'s user avatar
  • 4,952
9 votes
1 answer
723 views

Popular mistakes in probability

$\DeclareMathOperator\Var{Var}\DeclareMathOperator\Bern{Bern}\DeclareMathOperator\Pois{Pois}$Question: What not-trivial mistakes do students often make when solving problems in probability theory, ...
7 votes
4 answers
1k views

Recent impressive combinatorial developments in probability theory

In the preface to the second edition of Daniel Stroock's book "Probability Theory: An Analytic View", there is this striking claim (on p. xv) ... I suspect that, for at least a decade, the most ...
an12's user avatar
  • 1,302
7 votes
3 answers
995 views

Kolmogorov probability axioms without non-negativity condition

What is a minimal consistent modification of probability axioms to include negative values? Is it enough to use a minimal modification of axioms obtained by formal exclusion of non-negativity ...
Alex 'qubeat''s user avatar
7 votes
2 answers
605 views

Uniform Concentration Bounds on Weighted Sum of i.i.d. Bernoulli Random Variables

Let $\delta_1,...,\delta_n$ be $n$ independent identically distributed Bernoulli random variables with $\mathbb{P}(\delta_1=1)=p$. We consider a set $\Omega = \{\mathbf{a}:=(a_1,...,a_n)~|~a_i\in [0,c/...
tourzhao's user avatar
6 votes
2 answers
2k views

Are Gaussian Processes more important than other stochastic processes?

I am doing a course at university and it deals with Gaussian Processes mainly. We use them for fitting data and prediction, machine learning, regression, classification. Is there any particular reason ...
s5s's user avatar
  • 87
6 votes
1 answer
2k views

Brownian motion and its maximum and its minimum

Let $W_u, 0\leq u \leq t$ be Brownian motion. Let $m_t= min_{0\leq u\leq t} W_u$ and $M_t = max_{0 \leq u \leq t} W_u$. The fact that $(M_t , W_t)$ is absolutely continuous with respect to Lebesgue ...
Seongqjini's user avatar
6 votes
1 answer
375 views

Deviation bound for the maximum of the norm of Wiener process

Let $W(t)$ be an $n$-dimensional Wiener process. Denote by $\chi_n^2$ a chi-squared random variable with $n$ degrees of freedom. I have recently found the following inequality given without proof: $$ {...
Raindog's user avatar
  • 61
5 votes
1 answer
297 views

Random walk with continuously distributed steps on [-1,1]

A simple random walk $S_n = X_1 +\cdots +X_n$, where $P(X_i = 1) = p \not = 0.5$ and $P(X_i=-1)= q \triangleq 1-p$, admits the following probability $$P(S_n \textrm{ reaches } a \textrm{ before} -b) =...
mikew's user avatar
  • 108
5 votes
1 answer
219 views

Do there exist (almost surely) $C^{\infty}$-smooth Gaussian random fields?

Let $d \ge 1$. Do there exist Gaussian random fields on $\mathbb R^d$ which are (almost surely) $C^{\infty}$-smooth, but which are not analytic? If so, what are necessary and sufficient conditions ...
Tom LaGatta's user avatar
  • 8,512
5 votes
1 answer
567 views

Donsker's Theorem for triangular arrays

I should mention that I already posed this question on Math Stack Exchange, but didn't receive much feedback. Assume we have a sequence of smooth i.i.d. random variables $(X_i)_{i=1}^{\infty}$. Given ...
Indigo's user avatar
  • 233
5 votes
0 answers
485 views

Hierarchical Random Walk (also known as Hierarchical Hidden Markov Model)

Let us consider the following hierarchical (recursive) random walk model, which is also known as the hierarchical hidden Markov model in computer science (https://en.wikipedia.org/wiki/...
Minkov's user avatar
  • 1,127
4 votes
1 answer
423 views

Concentration inequalities on the supremum of average after time $n$

Let $R_1, R_2, \cdots$ be i.i.d. Rademacher random variables (taking values $-1,+1$ w.p. $0.5$). At time $k$, their average is $\frac{1}{k}\sum_{i=1}^k R_i$. One can imagine after $k\geq n$ for some $...
Martin Zhang's user avatar
4 votes
1 answer
258 views

When is $\prod_{i=0}^\infty (I-x_i x_i^T)=0$ for isotropic Gaussian $x_i$?

Suppose $x_i$ is sampled IID from isotropic zero-centered Gaussian random variable in $d$ dimensions with covariance $\Sigma=c*I$. When is the following true with probability 1? $$\prod_{i=0}^\infty (...
Yaroslav Bulatov's user avatar
4 votes
1 answer
804 views

Proof for power-law tail of Poisson-Dirichlet distribution (Pitman-Yor process & Zipf's law)

I'm trying to understand the motivation of using Pitman-Yor (PY) processes in language modeling, in particular Teh's hierarchical LM based on PY processes. A motivation frequently stated in research ...
Mirko Vogel's user avatar
4 votes
1 answer
239 views

Uniform inequality of the form $\text{Proba}(\sup_{v \in [-M,M]^k}|p^Tv-\hat{p}_n^Tv| \le \epsilon_n) \ge 1 - \delta$

Let $M > 0$, $k$ be a positive integer, and $\mathcal V:=[-M,M]^k$. Finally, let $p \in \Delta_k$, (where $\Delta_k$ is the $(k-1)$-dimensional probability simplex) and let $\hat{p}_n$ be an ...
dohmatob's user avatar
  • 6,853
4 votes
1 answer
378 views

Limit theorem : reproduce a proof with an adaption from discrete to continuous time

Im considering Theorem 5.2.2 in M. Sørensen "Exponential Families of stochastic processes". The setup is as follows: We have a Levy-Process $X_t$ fullfilling the CLT \begin{align} \sqrt{t}(X_t/t-E(...
ziT's user avatar
  • 257
4 votes
1 answer
463 views

Variance and expectation of timed-change squared Bessel process

Let $X_t$ be a squared Bessel process satisfying the SDE: $$ dX_t=\left(1-\frac{\beta}{(1-\beta)(1-\rho^2)} \right) dt +2\sqrt{X_t}dW^{(1)}_t $$ and $v_t=v_0e^{-\alpha^2 t/2+\alpha W^{(2)}_t}$ be a ...
KNN's user avatar
  • 323
4 votes
1 answer
159 views

diffusions corresponding to estimators

I am an undergraduate math student preparing my thesis. Currently I am reading L.D Brown's (1971) paper Admissible Estimators, Recurrent Diffusions, and Insoluble Boundary Value Problems. Here is a ...
user973's user avatar
  • 43
4 votes
2 answers
255 views

The necessary sufficient condition for recurrence of a Markovian random walk

Suppose $\sigma_{1},\sigma_{2},...$are i.i.d random variables.$S_{0}=0$. Define $S_{n}=S_{0}+\sum_{i=1}^{n}\sigma_{i}$, then ${S_{n}}$ is a Markovian random walk. I want to figure out the necessary ...
Lotayou's user avatar
  • 41
4 votes
1 answer
421 views

Order statistic of Markov chain sample path and related probabilities

Consider a one dimensional sample path, denoted as $\{X(1), ..., X(t), ..., X(n)\}$, generated from a discrete time finite state (time homogeneous) Markov chain over states $\{1,...,m\}$, with ...
Abhishek Halder's user avatar
4 votes
2 answers
519 views

Cramér–Rao type bound for absolute estimation error

Let $\{X_1, X_2, \dotsc, X_n\}$ be independent and identically distributed (i.i.d.) random variables sampled from a common distribution with density $f_{\theta}(x)$, where $\theta$ is an unknown ...
Michael's user avatar
  • 544
4 votes
0 answers
91 views

What is the entropy of binomial decay?

Let's play a game. I start with $N$ indistinguishable tokens, and I wait $T$ turns. Every turn, each token has probability $p$ of disappearing. I want an analytic formula for the entropy of this ...
Andrew's user avatar
  • 141
4 votes
0 answers
980 views

Inverse Fourier Transform involving a Bessel Function, Exponential, and Power

I'm interested in this integral as a function of $r$ for various spectral densities $S(s)$: $\frac{2 \pi}{r^{p/2}-1} \int_{0}^{\infty} S(s) J_{p/2-1}(2 \pi r s) s^{p/2} ds $, where $J_{p/2-1}$ is a ...
Gordon's user avatar
  • 41
4 votes
0 answers
153 views

A simplified MCMC / MH algorithm. Are there known convergence results?

Hi, I hope this isn't too basic. We were working on a simulation using a Monte Carlo Within Metropolis algorithm and noticed that the whole thing could be expressed in the form below and simplified ...
user32372's user avatar
  • 241
4 votes
1 answer
839 views

A balls into bins problem with combinatorial constraints

We are given $m$ balls and $n$ bins, with $m \ge n$. Each bin can contain at most $c$ balls (we assume that $c$ is an even integer). In a sequential fashion, at each time step, one ball is placed into ...
Penelope Benenati's user avatar
3 votes
2 answers
319 views

Concentration inequality of joint event over time of a submartingale

Consider a discrete time submartingale $X_n$ with bounded difference $|X_n-X_{n-1}|\leq c$. With Azuma inequality we have the concentration of a single time event as $$ P(X_t-X_0 \leq -t) \leq exp\...
Sung-En Chiu's user avatar
3 votes
1 answer
663 views

Stationary non-isotropic spatial stochastic processes

I asked this question in math.stackexchange but got no response; Are there any interesting examples of second order stationary processes on ${\mathcal R}^2$ or ${\mathcal R}^3$ that are not isotropic?...
Arin Chaudhuri's user avatar
3 votes
2 answers
751 views

An Upper Bound for the Average of Top Order Statistics

The following problem arises when we try to bound the expected offline optimal value of a simple online assignment problem with random values and unit weights, by its deterministic approximation. The ...
Santiago's user avatar
  • 197
3 votes
1 answer
532 views

What is a tensor product of random variables?

I am trying to understand the the following paper https://arxiv.org/pdf/1810.10971.pdf, in particular Example 2: If $ Y \sim N(0,1)$, the standard normal on $\mathbb{R}$, then $ \begin{align*} \Big( \...
anatolvitold's user avatar
3 votes
1 answer
650 views

Poisson process with stochastic intensity correlated with a Brownian Motion

I am currently confused with the moment of non-homogeneous compound Poisson process and a Brownian Motion. I know that generally Poisson Process and Brownian Motion are independent if they are adapted ...
distinguishable modification's user avatar
3 votes
0 answers
98 views

Probability measure on $\mathbb{R}^n$ with given marginals and given correlation matrix

In all what follows, let $\mathcal{P}(\mathbb{R}^n)$ denote the set of probability measures on $(\mathbb{R}^n, \mathcal{B}(\mathbb{R}^n))$ and $\mathcal{C}_n$ the set of $n \times n$ correlation ...
Tom's user avatar
  • 279
3 votes
0 answers
158 views

How are these two multi-armed bandit problems similar?

I am reading the multi-armed bandit survey by Bubeck and Bianchi. This question is for the lower bound section (2.3) of the survey. Let us define Kullback-Leibler divergence $kl(p, q) = p \log \frac{p}...
Shishir Pandey's user avatar
3 votes
2 answers
941 views

Probability distribution for two-state system that depends on residence time

I am a statistical physicist, and I've come across a problem that I don't know how to solve. I believe my issue lies with how to formulate it mathematically. I'd be very grateful for any assistance, ...
ionlet's user avatar
  • 33
2 votes
1 answer
187 views

Law of iterated logarithm for quadratic variation of Brownian motion

Let $(\Omega, \mathcal{F}, \mathbb{P})$ denote a probability space supporting a standard Brownian motion $B$. Let $\Pi=\{\pi_n : n \ge 0\}$ denote the sequence of dyadic uniform partitions of the ...
user6384's user avatar
2 votes
1 answer
186 views

Understanding some Hoeffding-type martingale inequality

Would anyone know how to prove the following, coming from the proof of theorem 2 in this paper (https://arxiv.org/pdf/1605.08671.pdf)? Consider i.i.d. Sub Gaussian random variables $(X_t)_{t\geq 1}$ ...
Aurelien's user avatar
  • 301
2 votes
2 answers
351 views

Weak convergence for discrete-time processes using characteristic functions

I am looking for a good reference about the analogues of the Bochner Theorem and the Lévy Continuity Theorem for probability measures on $\mathbb{R}^{\mathbb{N}}$ with the product topology. ...
Abdelmalek Abdesselam's user avatar
2 votes
2 answers
206 views

non-homogeneous counting process

Consider a counting process $\{N(t), t\geq 0\}$ where the time distribution between any two consecutive events, say $k$ and $k+1$ has a Poisson rate $\lambda(k)$, which is an explicit function of $k$....
user86217's user avatar
2 votes
1 answer
327 views

Recursive parameter estimation for partially observed Ito SDEs

I'm trying to get my head around online (recursive) maximum-likelihood parameter estimation in the language of stochastic processes and in the context of stochastic filtering, i.e. where we have a ...
S.Surace's user avatar
  • 1,675
2 votes
1 answer
3k views

Empirical estimator fot the total variation distance on a finite space

I have two probability measures $p$ and $p'$ on a finite set $X$ which I do not know precisely, but which I can sample from. I would like to estimate their total variation (omitting multiplier $2$): $$...
SBF's user avatar
  • 1,655
2 votes
1 answer
155 views

Kalman filter distribution of observation process

Let $(X_t,Y_t)$ be a pair of stochastic processes such that $$ \begin{aligned} dX_t =& A_t X_t dt + C_t dW_t,\\ dY_t = & H_t X_t dt + K_tdB_t \end{aligned} $$ for some non-random matrix-valued ...
ABIM's user avatar
  • 5,405
2 votes
1 answer
1k views

Rademacher complexity of composition of functions

I am looking for a bound on the empirical Rademacher complexity of the following class: $G=\left\{x \rightarrow \frac{h^T f(x)}{\|h\|_2 \cdot \|f(x)\|_2} : h\in R^d, f()=(f_1(),\ldots,f_d()), f_j \in ...
axk's user avatar
  • 517
2 votes
1 answer
164 views

Is there any parameter space of Cramér–Rao_bound

It is known that Cramér–Rao_bound is the lower bound of variance of a parameter. A useful link is https://en.wikipedia.org/wiki/Cram%C3%A9r%E2%80%93Rao_bound There is also a term called '...
Creator's user avatar
  • 495
2 votes
1 answer
150 views

Normalized concentration inequality for empirical CDF (iid sum)

Consider the empirical and population CDF, $$ F_n(t) = \frac{1}{n} \sum_{i=1}^n 1\{X_i \leq t\} \quad \mbox{and} \quad F(t) = \mathbb{E} [F_n(t)], $$ where above $X_1, \dots, X_n$ are iid, real-...
Drew Brady's user avatar
2 votes
1 answer
110 views

Lower bound on likelihood of binary outcomes

I am wondering about the following: does there exist a stochastic process $(X_n)_{n \ge 1}$ with values in $\{0,1\}$ on a probability space $(\Omega, \mathcal F, \mathbb P)$ such that for all $n \ge 1$...
Tartrate's user avatar
  • 341
2 votes
1 answer
192 views

Upper confidence bound for Poisson process rate parameter

Admittedly, this is an elementary question for mathoverflow. However, I've had no real bites on math and stats.stackexchange so I'm cross-posting. I am interested in computing an upper confidence ...
ted's user avatar
  • 283