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.

Filter by
Sorted by
Tagged with
3 votes
1 answer
156 views

Uniform iid sequence

The Rademacher functions are an explicit iid sequence with Bernoulli law. Does it exist an explicit construction of an iid sequence with uniform law?
0 votes
2 answers
114 views

Show that the set of strictly stationary, mean zero and finite variance stochastic processes is closed (or not)

Let $\mathcal{P}$ be the set of real-valued and strictly stationary processes with expectation zero and finite variance, i.e.: \begin{equation} \mathcal{P}:=\left\{ X = (X_t)_{t \in \mathbb{Z}} \, ...
  • 131
1 vote
0 answers
50 views

Constructing k-wise independent variables over a general set

We have seen in class a polynomials based construction that builds in $O(n^k)$ time, $n$ random variables, $k$-wise independent, over a field with $n$ elements. More specifically, you generate all the ...
  • 11
8 votes
5 answers
483 views

Distributions of distance between two random points in Hilbert space

Let $\mu$ be a probability distribution on a separable infinite-dimensional Hilbert space. Let $D$ be the distance between two independent random samples from $\mu$. So $D$ has some probability ...
1 vote
0 answers
122 views

Eigenvalue distribution of random matrices

Given basis $M_1,M_2\dotsc,M_{d^2}$ in $\mathbb C^{d\times d}$, we consider $$\sum_i x_i M_i$$ for random variables $x_i$. What is the distribution of $$\lVert\sum_i x_i M_i\rVert_1=\sum \sigma_k?$$ ...
  • 1,385
2 votes
1 answer
214 views

Idempotent splitting for Markov kernels

Let $X$ be a standard Borel space and $e : X \to X$ a Markov kernel. Suppose that $e$ is idempotent, that is $e \circ e = e$, or written out using the Chapman-Kolmogorov equation, $$e(A|x) = \int_X e(...
  • 4,553
0 votes
0 answers
27 views

Integral of product of centered lognormals

This is motivated by a specific question here Suppose $X(s)$ is a Gaussian field in $[0,1]$ with some short range correlation. Consider the integral $$\int E\left[\prod_{i\geq 1} (e^{X(a_{i}-c)}-1)\...
  • 1,649
3 votes
0 answers
123 views

Tail bound on trace norm / nuclear norm / Schatten-1 norm of Rademacher matrix

Let $0 < r \leq d$ integers. Let $X$, $Y$ be $d \times r$ matrices of independent Rademacher variables, that is, $X,Y \in \mathbb{R}^{d \times r}$ with entries $\pm1$ with probability $1/2$. I am ...
3 votes
0 answers
92 views

An infinite moving average is stationary iff its innovations are stationary

Let $(a_j)_{j \in \mathbb{N}_0}$ be a real-valued sequence such that $\sum_{j = 0}^\infty a_j^2 < \infty$. Further, define an infinite moving average time series $X = \{ X(t), t \in \mathbb{Z}\}$ ...
5 votes
2 answers
467 views

Relationship between KL, chi-squared, and Hellinger

There are many well-known relationships between the KL divergence, chi-squared ($\chi^2$) divergence, and the Hellinger metric. In the paper "Assouad, Fano, and Le Cam" by Bin Yu, the author ...
  • 63
0 votes
0 answers
62 views

Likelihood ratio of non-trivial cycles in an inhomogeneous random square lattice graph embedded on a toroidal surface

Consider a square lattice (random) graph $G$ embedded on a toroidal surface. Each edge $(i, j)$ of the graph has an associated likelihood probability $p_{ij}$. The probabilities $p_{ij}$ come from a ...
3 votes
1 answer
244 views

Discrimination between set of binary distributions

Suppose we know two sets of distributions $A=\{p_1,p_2,\cdots,p_k\}$ and $B=\{q_1,q_2,\cdots,q_k\}$. We are given $C=\{r_1,r_2,\cdots,r_k\}$ such that $r_i=p_i$ for all $i$ or $r_i=q_i$ for all $i$. ...
  • 1,385
1 vote
1 answer
106 views

Vector version of concentration of Lipschitz functions on sphere (Levy's Lemma)

Levy's Lemma asserts Lipschitz functions of vectors chosen uniformly from the unit hypersphere concentrate: Lemma. Suppose $f:\mathbb{S}^{d-1} \to \mathbb{R}$ is $L$-Lipschitz on the unit hypersphere. ...
  • 111
0 votes
0 answers
72 views

If all moment of X are greater than all moment of Y, can we said something about their probability?

Consider a continuous probability distribution $f$ and two random variables $X, Y$ both are greater than equal to $0$ and they are not identical random variables. Let's say one can show that $E[X]^k \...
8 votes
2 answers
525 views

Why Kleisli Markov categories and not the Eilenberg-Moore categories of the associated monads

Why is there so much interest in the Markov categories which are Kleisli categories for monads corresponding to distributions etc. but not much discussion of the E.M. categories? For example, the E.M. ...
4 votes
1 answer
228 views

Bounds on discrepancy metric of product measures

Consider two measurable spaces $X_1 = (\mathbb{R}^m,\mathcal{B}(\mathbb{R}^m),\mu_1)$ and $X_2 = (\mathbb{R}^m,\mathcal{B}(\mathbb{R}^m),\mu_2)$ and the product spaces $$X_1^{q} = (\times_{i=1}^q\...
  • 2,662
0 votes
0 answers
83 views

What to do when the second moment method does not provide a sufficient bound for $P(X=0)$

We have that for a real valued random variable $X$, $$ P(X=0) \leq \frac{\text{Var}(X)}{\left(\mathbb{E}(X)\right)^2} $$ known as Chebyshev's inequality. Consider a random variable $X \in \{0,1,2,\...
  • 532
2 votes
1 answer
220 views

An oversimplified model for optimal distribution of wealth

Consider the following, overly simplified, model for determining an optimal wealth distribution for society: Let $X$ be a random variable, which will model the distribution of wealth in a society. The ...
1 vote
1 answer
88 views

Minimax estimation rate of sparse vector $w_\star$, w.r.t to mixed norm $\|\hat w_n-w_\star\| := \|\hat w_n - w_\star\|_2 + \|\hat w_n-w_\star\|_q$

Let $n,d,s$ be positive integers with $s \le d$, and let $B_0(d,s)$ be the set of all (real) $d$-dimensional vectors with at most $s$ nonzero components. Given an $n \times d$ matrix $X$ with rows $...
  • 6,094
4 votes
1 answer
365 views

Why is every Gaussian process a linear process?

In Section 4.2.4 of [1], the authors write In this section we consider a causal linear process $$ X_t = \sum_{j = 0}^\infty a_j \varepsilon_{t - j}, \quad t \in \mathbb{N}, $$ where, without loss of ...
2 votes
1 answer
135 views

Bernoulli trials with small dependencies: asymptotics (central limit theorem, law of the iterated logarithm)

Let $\{X_k\}$ be a sequence of random variables, with $X_k\in\{+1, -1\}$ for $k>0$, generated as follows. First, define $S_n=X_1+\dots +X_n$, with $X_0=S_0=0$, and let $0<\beta<\frac{1}{2}$. ...
1 vote
0 answers
52 views

Optimal Kelly criterion for process with N discrete outcomes

I am trying to come up with a generalisation of the Kelly formula for optimal fractional betting but and have hit a roadblock. The Kelly criterion is usually explained via a game that ends in 1 of 2 ...
0 votes
1 answer
123 views

Given correlated Gaussian random variables, how to bound the probability that the first is the largest?

Let $Z\sim \mathcal{N}(\mu, \Sigma)$ be a Gaussian random vector in $\mathbb{R}^d$. What are some nontrivial bounds on $p=\mathbb{P}(S)$, where $S$ is the event $Z_1=\max_i Z_i$? This is motivated by ...
2 votes
0 answers
73 views

Optimal Monte Carlo Trace Estimator

For a psd real symmetric $d\times d$ matrix $A$ and a function $f: \mathbb{R}^d \to \mathbb{R}$, with $f(x) := x^T A x$ we have that with $p(x) = \mathcal{N}(0_d, I_d)$ (i.e. standard multivariate ...
7 votes
1 answer
233 views

Local probabilities for lattice random walk

Let $\epsilon <1/2$. Let $X$ be a random variable in $\mathbb Z$ such that $\mathbb P (X=x)\le \epsilon $ for any $x\in \mathbb Z$ (you may add any moment or regularity conditions on $X$ if needed)....
  • 723
7 votes
1 answer
226 views

Are all quasi-regular points on Polish spaces generic points?

Let $X$ be a Polish space and $T\colon X\to X$ be a continuous map. We say that a point $x\in X$ is quasi-regular if for every bounded continous function $\varphi\colon X\to\mathbb{R}$ the sequence $...
5 votes
2 answers
165 views

Entropy & difference between max and min values of probability mass

Let $X$ be a random variable with probability mass function $p(x) = \mathbb{P}[X = x]$. I know entropy $H(X)$ of $X$ measures the uncertainty of $X$ and a large value of $H(X)$ means $p(x)$ is nearly ...
1 vote
1 answer
157 views

Using gradient descent in probability case

Suppose we have i.i.d. samples $x_i\sim N(0,\Sigma)$ and $y_i\sim x_i^T\omega^*+\xi_i,\xi_i\sim N(0,1)$ where $\omega^*$ is the fixed point of: $$\omega_{i+1} = \omega_i − \eta\nabla_\omega f(\omega_i,...
3 votes
1 answer
136 views

An inequality relating the Kullback-Leibler divergence of two discrete distributions with constant reference distribution

Suppose that $D_{KL}(p_1\parallel q)<1$ and $D_{KL}(p_2\parallel q)<1$. I'm trying to show that either $D_{KL}(p_1\parallel p_2)$ or $D_{KL}(p_2\parallel p_1)$ will have an upper bound close to ...
8 votes
0 answers
207 views

Decay of orthogonal contributions in a random set of vectors

Suppose we sample $k$ vectors $v$ from normal distribution centered at zero and diagonal covariance with diagonal entries $1,\frac{1}{2},\ldots,\frac{1}{d}$ and normalize $v$: $$\frac{v_1}{\|v_1\|},\...
2 votes
1 answer
79 views

Approximation of a stationary process by a sequence of ergodic and stationary sequence of stochastic processes

Let $X = [X_t : t \in \mathbb{Z}] \sim P$ and $Y = [Y_t : t \in \mathbb{Z}]\sim Q$ be two stochastic processes. Let's define the Mallows metric. Let $\mathcal{M}_m$ be the random vectors $(X,Y)$ ...
  • 131
6 votes
0 answers
94 views

Hamilton cycles in random graphs with just enough connectivity

What is the asymptotic probability that $G$ has a Hamilton cycle if $G$ is a random $n$ vertex $\frac{4}{3}n$ edge graph, with minimum degree 2 and without degree 2 vertices at distance 1 or 2 to each ...
1 vote
0 answers
82 views

Width of the critical window in a random graph

In an Erdős–Rényi random graph $G(n,p)$, the giant component emerges with thresholding function $p(n) = c/n$, where $c>1$. When $c=1$, and $\lambda \in \mathbb{R}$, we can write or "...
  • 532
0 votes
1 answer
99 views

What's the cumulative probability of these particular bags of liquorice allsorts?

After eating a bag of liquorice allsorts in one sitting, as one does, I noticed that it had contained an unusual amount of brown ones (which, you will agree, are an abomination that should never have ...
  • 123
0 votes
0 answers
36 views

Tracing (or marginalizing) an input wire in a Markov category

Because Markov categories are monoidal, their morphisms can be seen as boxes with one or more input wires and one or more output wires. If the Category supports deleting wires by marginalization or ...
3 votes
2 answers
164 views

Is every compound Poisson distribution a mixed Poisson distribution?

I asked and bountied this question at math SE but didn't get any answers, so I suspect that only experts (if anyone) may know the answer. The mixed Poisson distribution and compound Poisson ...
  • 873
1 vote
2 answers
96 views

How to compute the trace of this random matrix: $\mathrm{Tr} ( a Y_1+ b Y_2)^{-1} ( c Y_1+ d Y_2)$?

Lets say $Y=\frac{1}{n}XX^\intercal$ and $X$ is a $n\times m$ random matrix whose entries are i.i.d gaussian. We know when $n$ and $m$ go to infinity with a fixed ratio, the singular values of $Y$ ...
0 votes
1 answer
99 views

Invariance principle: Brownian bridge and random walk conditioned on end point

Let $\{X_i, i \in \mathbb{N}\}$ be a sequence of non-lattice i.i.d. centered random variables, $\mathbb{E} |X_1| ^3 < 0$. Let $S_n = \sum\limits _{i=1} ^n X_i$ be the corresponding random walk and ...
  • 694
1 vote
1 answer
164 views

What is the exact definition of a sharp transition?

In "Sharp threshold phenomena in statistical physics", H. Duminil-Copin, Japanese J. of Math. 14, 2019, a sharp transition of a boolean function is defined as follows: A sequence of ...
  • 532
0 votes
0 answers
51 views

Bins and colored balls: minimum number of bins containing a subset of colored balls

We are given $n$ bins and $dm$ colored balls. There are $m$ colors in total such that there are exactly $d$ balls of each color. For each color, we randomly choose $d$ bins and put the $d$ balls of ...
  • 439
0 votes
1 answer
153 views

When can a convolution be written as a change of variables?

Suppose $X$ is a random variable with a density $f(x)$ such that $f(x)$ is a convolution of some density $g$ with some other density $q$: $$ f = g\ast q. $$ Under what conditions does $X=h(Y)$, where $...
1 vote
1 answer
80 views

Lower bound for KL divergence of bounded densities and $L_{2}$ metric

I am currently reading "Smoothing of Multivariate Data" by Klemela. It contains Lemma 11.6, which upper and lower bounds the KL-divergence of two densities in terms of the $L_{2}$-metric. ...
6 votes
1 answer
304 views

Average and max. hitting time to a specific vertex

Consider simple random walks that stop when reaching a given node $x$ in an undirected, unweighted and connected graph on $n$ nodes. Let $H(i,x)$ denote the (expected) hitting time from $i$ to $x$, ...
8 votes
1 answer
297 views

Two dice yielding uniform distribution, part 2

Since this question is on the front page again, a generalization. Let $p$ be prime, and let $a$ and $b$ be positive integers with $a+b=p-1$. Is it possible to have two loaded dice, one with sides ...
0 votes
1 answer
156 views

Simple random walk return time

Let's take a simple random walk on $\mathbb{Z}$, $(S_n)_{n\geq0}$, started at zero. If $\tau^+_0 = \inf\{n \geq 1: S_n = 0\}$ is the first time the walk returns on zero, we know that $\mathbb{E}[\tau^+...
0 votes
1 answer
141 views

Step in proof of Itô formula

I am reading a book on stochastic processes. The author proved Itô formula for $f(t,w(t))$ where $w(t)$ is brownian motion with filtration $F_t$. Then he wants to prove Itô formula for $x(t)=a(t)+b(t)...
3 votes
1 answer
67 views

Stochastic dominance using moment-generating function

Traditionally, stochastic dominance is defined using the cumulative distribution function(CDF). But sometimes, the CDF is not easily to be obtained. For example, the generalized noncentral Chi-square ...
2 votes
0 answers
107 views

Multiple integral with diagonal constraint (short-range)

I am looking for an upper bound on the following integral: $$\int_{X_{\delta}}\prod_{j\neq i=1}^{n}\left ( \frac{\delta}{\min (\max(\epsilon, |a_i-a_j|),\delta)}\right )^{b} \prod_{i=1}^{n} da_{i},$$ ...
  • 1,649
1 vote
0 answers
104 views

Normal numbers and law of the iterated logarithm

If I remember correctly, for the binary digits of a real number in $[0,1]$, I was told that satisfying the law of the iterated logarithm (LIL) is stronger than being normal. That is, supposedly, some ...
3 votes
1 answer
414 views

$\cos(\frac{x}{3})\cos(\frac{x}{9})\cos(\frac{x}{27})\dots$ as $x \rightarrow \infty$

It is known that $$ \cos(\frac{x}{2})\cos(\frac{x}{4})\cos(\frac{x}{8})\dots = \frac{\sin x}{x} = O_{x \rightarrow \infty}(x^{-1}) $$ Is it true that $$ f(x) = \cos(\frac{x}{3})\cos(\frac{x}{9})\cos(\...

1
3 4
5
6 7
159