**3**

votes

**0**answers

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

**7**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**2**answers

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

**2**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**2**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**2**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**2**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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 ...