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
163 views

Derandomization barriers in complexity theory applicable as barriers to constructive arguments replacing probabilistic method

The probabilistic method as first pioneered by Erdős (although others used this before) shows existence of a certain object while finding that object may take exponential time. (1) Is there any ...
27
votes
7answers
1k views

List of proofs where existence through probabilistic method has not been constructivised

Probabilistic method as first pioneered by Erdős (although others used this before) shows existence of a certain object. What are some of the most important objects for which we can show existence but ...
-1
votes
1answer
119 views

For i.i.d X and Y , if X + Y and X - Y are independent, show X is normally distributed [closed]

The question goes as follows: If $X$ and $Y$ are independent and identically distributed, their density function $f(x)$ is strictly positive and second-order continuously differentiable. If $X+Y$ and ...
2
votes
1answer
146 views

Proofs of inequalities used by Erdos-Renyi in their Random Graphs Paper 1

Please refer to this, it is Erdos-Renyi 1959 paper 1 on Random Graphs. I am currently working on this, but I am stuck on the fifth page, where they use two estimates. More specifically, here's the ...
1
vote
0answers
32 views

Integration involving modified bessel function, exponential and power

I need to find the following integration. $$ \int_0^a e^{-(N-1)x}(\sqrt{4x}K_{1}(\sqrt{4x}))^N $$ where $$ a>0, \quad N \geq 1 $$ Any help will be much appreciated. BR Frank
0
votes
0answers
55 views

Integral involving modified bessel function of second kind, exponential and power

I need to compute the following integral. $$ \int_0^a e^{-bx}\sqrt{4(a-x)}K_1(\sqrt{4(a-x))}dx\,. $$ where $$ a>0$$ and $b$ can be greater than zero or less than zero but it is not a complex ...
6
votes
2answers
324 views

A measure of how “spread out” a probability measure is

Consider a random variable $X$ whose variance is large. As a contrast to Markov's or Chebyshev's inequality, both of which measure the concentration of a probability distribution, is there a measure ...
2
votes
1answer
53 views

Bounding exceedance probabilities for correlated normal variables

Suppose $y\sim N(0,\Sigma)$ is an $n-$dimensional vector. I'm interested in an upper bound for $\Pr(\max_{1\leq i\leq n} y_i > k)$ for $k$ large. I know a little about $\Sigma$: ...
1
vote
1answer
99 views

Feller processes / probability generators

I am looking for a example of a function in $C_0(\mathbb{R})$ such that $f',f'' \,\text{and}\, f''' \in C_0(\mathbb{R})$ with $$ \inf f < \inf (f-a*f''')$$ for some $a>0$, but I couldn't find ...
2
votes
1answer
206 views

Proof that it's possible to colour all elements in set, that all subsets will be bicolored

(For my easy understanding, let me rewrite the question. The author should feel free to remove my edit or... accept it; I am leaving the original formulation at the end intact). ================= ...
1
vote
1answer
69 views

Minimum and maximum bound on mean of product of three pairwise uncorrelated random variables

There are three pairwise uncorrelated random variables $X, Y, Z$ $$E(X) = E(Y) = E(Z) = 0$$ $$E(X^2) = E(Y^2) = E(Z^2) = \sigma^2$$ How we could find minimum and maximum bound on $E(XYZ)$?
0
votes
0answers
92 views

Comparison of Parameter estimation using maximum likelihood and Maximum entropy

I am not sure if the question is appropriate but I want to try my luck. One can estimate a parameter using maximum likelihood and we know it is optimal. On the other hand there are methods which uses ...
1
vote
2answers
235 views

Bayes statistics precisely formulated

I am trying to learn something about Bayesian statistics, however, I am struggling already with the simplest equations and, moreover, with the very basic questions: What are we given? What is our ...
3
votes
2answers
180 views

Distribution of the hitting time of a random walk

Consider the random walk on $\mathbb R$ with $X_0 = a >0$ and $$X_{n+1} = X_n + U_n,$$ where $U_0, U_1, U_2,\ldots $ is an i.i.d. sequence of uniform random numbers in $[-1,1]$. How does the ...
4
votes
1answer
157 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) ...
3
votes
0answers
58 views

What is the influence of unreliable comparisons on the results of sorting

Considering sorting algorithms based solely on binary comparisons of the elements to be sorted(algorithms such as insertion sort, selection sort, quicksort, and so on), what problems do we face when ...
0
votes
0answers
33 views

Stochastic dominance for subsets

The subsets of a set $N=\{1,2,\ldots,n\}$ form a lattice, with larger sets being higher up, and a subset $B$ connected to another subset $A=B\cup\{x\}$ (for any $x\not\in B$) higher up by a "pipe". ...
2
votes
1answer
174 views

Topologies for which the ensemble of probability measures is complete

I have been struggling quite a bit with reconciling my intuitive understanding of probability distributions with the weird properties that almost all topologies on probability distributions possess. ...
0
votes
1answer
70 views

Weak existence for modified Tanaka SDE

Tanaka's theorem (wikipedia) implies that $X_t = |B_t|$ is a weak solution to the SDE $dX_t = dW_t + dL_t^0(X_t)$, where $W_t$ is a Brownian motion and $L_t^0(X_t)$ is the local time of $X_t$ at ...
1
vote
0answers
35 views

Marginal of mean from product of student-t and gamma

Let's say we have a distribution with PDF described by the product of Gamma and Student-t distributions. This is equivalent to a generative model, in which precision is first drawn from Gamma, and the ...
0
votes
1answer
102 views

Markov chain with Feller property

Does anybody know whether there is an analysis of when the monotone decreasing chain has the Feller-property? The monotone decreasing is defined as a chain on $\mathbb{N}$ and the rate of going down ...
0
votes
0answers
74 views

Variance of the average path length of connected graphs

The average path length has been defined for a connected graph $G$. It is defined here: https://en.wikipedia.org/wiki/Average_path_length Has the variance of these path lengths ever been ...
1
vote
0answers
46 views

Integrability of complex gaussian random matrix model

It is known that the partition function $$ \mathcal{Z}_1=\int dH e^{-N{\rm Tr}(H^2)}e^{-NV(H)},$$ where the integral is over $N\times N$ hermitian matrices $H$, with the potential $$ V(H)=\sum_{j\ge ...
4
votes
1answer
77 views

Two-side deviations for ergodic sums

Let $(X,\mu)$ be a probability space and $f\colon (X,\mu)\to (X,\mu)$ be an ergodic automorphism. Let $\phi\in L^\infty(X,\mu)$ be such that $\int\phi d\mu=0$. Suppose that for $\mu$-a.e. $x\in X$, ...
3
votes
1answer
128 views

Is it possible for a random nowhere dense closed set to have a positive probability of hitting any given point?

Given a compact metrisable topological space $X$, we write $\mathcal{N}(X)$ for the set of non-empty closed nowhere dense subsets of $X$, which is a Polish space under the topology induced by the ...
1
vote
1answer
103 views

$q$-connectedness of random digraphs obtained from a fixed graph

Let $G = (E,V)$ be an undirected graph (which can have multiple edges or loops). Let $k,l,m\colon E\to \mathbb{R}_{\geq 0}$ be three edge-weight functions that satisfy $2k(e) + l(e) + m(e) = 1$ for ...
0
votes
0answers
48 views

Majorization in distributions of subsets

The subsets of a set $N=\{1,2,\ldots,n\}$ form a lattice, with larger sets being higher up, and a subset $B$ connected to another subset $A=B\cup\{x\}$ (for any $x\not\in B$) higher up by a "pipe". ...
10
votes
1answer
191 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 ...
4
votes
1answer
193 views

Tail bounds on eigenvalue gaps for GUE

What I'm looking for is a non-asymptotic bound on the probability that the smallest gap between eigenvalues of a GUE matrix does not exceed a certain value. I'm aware of the bounds in ...
1
vote
1answer
96 views

Literature question on the convergence rate of the empirical distribution

Assume that given $n$ i.i.d samples $(X_1, X_2, ..., X_n)$ drawn from $p_X$, an unknown probability mass function defined over a finite alphabet $\mathcal{X}$, one wants to estimate $p_X(x)$ for each ...
3
votes
0answers
62 views

Stochastic equation

Let $X,Y$ be Polish spaces and $\kappa:X\times \mathcal B(Y)\to[0,1]$ be a Borel-measurable stochastic kernel on $Y$ given $X$. Under which conditions for a probability measure $\nu$ on $Y$ there ...
7
votes
1answer
140 views

approximate stationary distributions of a doubly stochastic matrix and its supports

Given a doubly stochastic matrix $M$ and a distribution $v$,let $M=\sum_{\sigma\in S_n}p_{\sigma}M_{\sigma}$ be any Birkhoff decomposition of $M$, where $M_{\sigma}$ is the permutation matrix induced ...
2
votes
0answers
60 views

How sensitive are the n-th step transition probabilities of the simple random walk to a small perturbation of an infinite graph?

Suppose that $G$ is an infinite, locally finite, connected graph. Fix a vertex $o$ in the graph and for each $n$ and $x$ let $p(n,o,x)$ be the probability that a simple random walk (at each step a ...
2
votes
0answers
40 views

LDP respectively almost sure convergence in the context of randomly weighted trees

I am currently working on the following Problem: Imagine you are given a $d$-ary tree $T_d$, which means an infinite tree with one vertex $x_0$ on top and in which each vertex has $d$ children. ...
0
votes
2answers
51 views

A way to possibly calculate one Binomial CDF function from another closely related one?

Let $y < z$ be two numbers between $0$ and $1$, is there a way to relate the CDF functions $F_{n,y}(s)$ and $F_{n,z}(s)$... or approximate one from another, without just saying $F_{n,z}(s) \le ...
2
votes
0answers
48 views

Reference for branching processes

A popular model of a continuous time branching process was introduced around 1970, which is now called the Crump-Mode-Jagers branching process, was introduced here: A General Age-Dependent Branching ...
0
votes
0answers
39 views

Weak solutions of linear parabolic PDEs and corresponding SDEs

It is well known that for an Stochastic differential equation (on the real line) of the form: $dX_t = \mu(X_t)dt + \sigma(X_t)dW$ where $W$ is the standard Wiener process, the transition probability ...
2
votes
1answer
128 views

Asymptotic behavior of a ratio of sums of iid random variables

Let $X_i$ and $Y_i$ be distributed identically to $X$ and $Y$, respectively. Assume both $X$ and $Y$ take strictly positive values. Consider the random variable $R_n \doteq \frac{\sum_{i=1}^n ...
3
votes
2answers
162 views

Uniform Convergence of Moment Generating Function

In the article, "The Empirical Moment Generating Function" by Csörgö, the author defines the empirical moment generating function for a sample of $n$ variables $X_1,X_2, \dots, X_n$ as: $$ ...
2
votes
0answers
87 views

On the Bhattacharyya distance

Let $X$ and $Y$ be two continuous random variables with support $\mathbb{R}^{+}$ and with PDF $f(x)$ and $g(y)$. If the Bhattacharyya distance of $f$ and $g$ is less than $\epsilon$, then is there any ...
1
vote
0answers
53 views

A variance-preserving Boolean function [closed]

Let a random variable $X$ be given with $P_X$ supported over $\mathcal{X}$. What are the necessary conditions for the existence of a boolean function $f:\mathcal{X}\to \{0,1\}$ such that ...
-1
votes
1answer
151 views

Regarding a new divergence function of two probability distributions

Let $X$ and $Y$ be two continuous random variables with common support and with PDF $f(x)$ and $g(y)$. For any $0 \leq \alpha \leq 1$, and any constant $\beta$ within the support of $X$ and $Y$ such ...
0
votes
0answers
63 views

Random process & probability problem met in wireless communication

A random process r obeys the following distribution: $p(r,ṙ)=rb_0\exp(−\frac{r^2}{2b_0})\sqrt{2πb_2}exp(−\frac{\dot{r}^2}{2b_2})$, where $\dot{r}$ is the derivative of r in the time domain. You can ...
1
vote
2answers
232 views

Fourier transform localisation (still unanswered, but apparently off-topic?) [closed]

In the context of Pólya's theorem I was reading these notes here on p. 19. In the last paragraph the authors claim (it is the sentence starting like "standard Fourier theory shows...") that the ...
4
votes
1answer
118 views

concentration inequality for $d$-dimensional martingale

Are any concentration inequality available for $d$-dimensional martingale. It is easy to find such inequality using the inequalities for single dimension, but that will contain the dimension $d$ in ...
2
votes
0answers
46 views

Construction of Stein's exchangeable pair for certain dependent random variables

Given a sequence of exchangeable random variables $X_1,\ldots,X_n$, and a measurable function $g: \mathbb{R}^n \to \mathbb{R}$. Let $S_n=g(X_1,\ldots,X_n)$. Then what is a natural construction of a ...
0
votes
0answers
48 views

$\mathsf{GCD}$s of random linear form

Given $a,b\in\Bbb N_{<M}$ where $M\in\Bbb N_{>\exp(18)}$ is arbitrary with $(a,b)=1$, the probability that $\mathsf{gcd}(ax_1+by_1,ax_2+by_2)=1$ where $x_1,x_2,y_1,y_2\in\Bbb N_{>\ln M}$ is ...
4
votes
1answer
174 views

How are the real-space RG transformations defined?

I'm reading Shang-keng Ma's book Modern theory of critical phenomena, and I'm a bit confused as to how the real-space RG transformations are defined. Ma basically says that these transformations are ...
2
votes
1answer
159 views

General solution to system of stochastic linear differential equations

Assume we are given the system of linear stochastic differential equations $$dx_i = \sum_{j=1}^n a_{ij}(t) \cdot x_j \cdot dt + \sum_{j=1}^n \sigma_{ij}(t) \cdot x_j \cdot dB_{ij,t} + b_j(t)\cdot ...
6
votes
1answer
294 views

Inequality for the maximum of Gaussian variables

Let $X=(X_1,\dots,X_n)$ and $Y=(Y_1,\dots,Y_n)$ be centered Gaussian vectors with variance matrix $\Gamma_X$ and $\Gamma_Y$. We assume that the matrix $\Gamma_Y-\Gamma_X$ is positive definite. Is it ...