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)

0
votes
0answers
13 views

Truncated Robbins-Monro

I'm reading Han-Fu Chen's book "Stochastic Approximation and Its Applications", and in Chapter 1, he's got a statement of a theorem and proof on a truncated Robbins-Monro algorithm. In this version, ...
22
votes
5answers
2k views

What is a good method to find random points on the n-sphere when n is large?

As part of a more complex algorithm, I need a fast method to find random points of the n-sphere, $S^n$, starting with a RNG (random number generator). A simple way to do this (in low dimensions at ...
3
votes
1answer
235 views

Quasi-stationary distribution for a death process

In the paper, Survival in a quasi-death process by van Doorn and Pollett, the quasi-stationary distribution of a transient CTMC is discussed and QSD for a simple death process is derived. Consider a ...
-5
votes
0answers
42 views

I cannot solve this question! HELP [on hold]

Imagine a 100 storey building. You want to find the highest floor from which an iphone, when dropped, will not break. If an iphone is dropped and does not break, it can be used again with no adverse ...
4
votes
1answer
56 views

Weakly correlated Bernoulli field

Let $\Lambda\subset\mathbb{Z}^{d}$ ($\Lambda$ is finite). Let $\left\{ \eta_{x}\right\} _{x\in\Lambda}$ be a field of dependent Bernoulli random variables. I assume that their correlation decays ...
-3
votes
0answers
43 views

try to calculate the probability [on hold]

Prove that if you choose two points uniformly and independently on a line of length 1, then the expected distance between the points is 1/3. My answer is 1/6, not match the question
4
votes
1answer
216 views

Strings with no long runs from proper subalphabets

Let $R_{n,k,b}$ be the number of $b$-ary strings of length $n$ that contain some run of length at least $k$ from some $(b-1)$-ary subalphabet. Let $N_{n,k,b}=b^n-R_{n,k,b}$ be the size of the ...
9
votes
0answers
144 views

Two conjectures about zero inner products and dissociated sets

The following problems come from something I worked on (with my coauthors) related to proving a new time lower bound for streaming problems. Having worked on these problems for some time with little ...
2
votes
0answers
44 views

Second eigenvalue of biased reflected random walk

Let $Z_n$ be a reflected random walk on the non-negative integers with negative drift. That is, $Z_n$ is non-negative and moves one to the right w.p. $p<1/2$. It moves one to the left w.p. $1-p$, ...
3
votes
1answer
143 views

Properties of a finite random walk

Consider the simplest random walk - $X_0 = 0$ and from there on (i.i.d), $X_i=X_{i-1}+1$ with probability $p$ or $X_{i-1}-1$ otherwise. Let $Y_N$ be the highest point $X$ have reached on the first ...
-1
votes
0answers
26 views

Probability of co-occurence [on hold]

Of total N people, m people are good at mathematics and c people are good at computer science. What is the expected number of people good at both mathematics and computer science? Or what is the ...
1
vote
0answers
29 views

Scaling of First-passage times for Random Walk on integer lattices

Consider simple symmetric random walk $S_{n} = (S_{n}^{(1)},\dots, S_{n}^{(d)})$ on the d-dimensional integer lattice with starting point the origin. Let $\tau_{N}$ be the first time $S_{n}$ exits ...
8
votes
1answer
557 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 ...
4
votes
2answers
231 views

“Typical” convergence rate for the von Neumann mean ergodic theorem

The von-Neumann theorem states that for a unitary operator $U: {\cal H} \mapsto {\cal H}$, where ${\cal H}$ is a Hilbert space, the following holds: $$ \lim_{N\to \infty} \frac{1}{N} \sum_{n=1}^N U^n ...
4
votes
1answer
131 views

Upper bound of the waiting time of a sum process

Let $n \in \mathbb{N}$, $x_1, \ldots, x_n \in (0,1)$ fix but arbitrary, s.t. $\sum_{i=1}^n x_i = 1$. Let $X_i \sim \operatorname{Unif}(\{x_1, \ldots, x_n\})$ i.i.d., and $T_n = \min\{t \in \mathbb{N} ...
9
votes
5answers
3k views

Any sum of 2 dice with equal probability

The question is the following: Can one create two nonidentical loaded 6-sided dice such that when one throws with both dice and sums their values the probability of any sum (from 2 to 12) is the same. ...
0
votes
0answers
24 views

Bounds on the moments of truncated sub-gaussian random variables

If $X$ is a centered sub-gaussian random variable, then there exists a constant $c$ such that $$ \mathbb{P}[|X|>t] \leq \exp(1-ct^2) $$ for all $t\geq 0$. Moreover, we know that the normalized ...
12
votes
2answers
405 views

Is there a natural measurable structure on the $\sigma$-algebra of a measurable space?

Let $(X, \Sigma)$ denote a measurable space. Is there a non-trivial $\sigma$-algebra $\Sigma^1$ of subsets of $\Sigma$ so that $(\Sigma, \Sigma^1)$ is also a measurable space? Here is one natural ...
1
vote
0answers
47 views

Cramer-Rao type bound for absolute estimation error

Let $\{X_1, X_2, \ldots, 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 ...
2
votes
1answer
274 views

weak convergence of the solutions to stochastic heat equation

$W(t,x)=\sum_ic_ie_i(x)B^i_t$ is a Brownian motion in $L^2(R^d)$, where $\{e_i\}$ is the standard orthogonal basis and $\sum_ic_i^2<\infty$. $$\partial_t u(t,x)=\Delta u(t,x)+u(t,x)\dot{W}(t,x)$$ ...
0
votes
1answer
43 views

How can two random variables are continuous infers that their jointly random variable is continuous [on hold]

We assume that $\forall a,b$ suchthat $a^2+b^2>0$, $aX+bY$ is continuous random variable. But we don't assume that $X$ and $Y$ are independent. My question is the following: Is it true that the ...
2
votes
1answer
126 views

Random walk on a sphere along latitude-longitude grid

Suppose a sphere is partitioned by a latitude-longitude grid, with grid quadrilaterals $\Delta \times \Delta$. All grid nodes have degree $4$, while the North & South poles have degree $2 \pi / ...
8
votes
0answers
129 views

No limit shape for random Young diagrams under z-measure?

In their paper Random partitions and the Gamma kernel (Advances in Mathematics 194 (2005) 141–202), Borodin and Olshanski state that: An important difference between the Plancherel measures and ...
4
votes
2answers
322 views

Expectation of a generalization of Dirichlet distribution

For the standard Dirichlet, the expectation of $X_i$ is $\alpha_i/\alpha_0$, where $\alpha_0 = \sum_i \alpha_i$ [http://en.wikipedia.org/wiki/Dirichlet_distribution]. I am considering the following ...
2
votes
1answer
124 views

Push-forward of sum of two maps

Let $X=R^n$ and $Y=R^m$ are two Euclidean spaces with $m<n$. Let $\varphi$ and $\phi$ are two (smooth) maps from $X$ to $Y$ and $\mu$ is a probability measure on $X$. Is there any relationship ...
4
votes
1answer
100 views

variance of compound binomial distributions

The below is motivated by a problem I'm observing in my experimental data I have m boxes, where each box is supposed to contain k molecules of mRNA. The measurement process includes labeling all the ...
2
votes
2answers
275 views

Probability spaces involved in using Bayesian Inference

I am currently reading "Statistical and Inductive Inference by Minimum Message Length" by C.S. Wallace. In this, Wallace gives a fairly informal account of Bayesian Inference which, in the case ...
2
votes
1answer
606 views

For what nonnegative measures $\mu$ does $\mu*e^{-|\cdot|}\in L^{\infty}$?

I am trying to characterize all measures on $\mathbb{R}$ such that $$ \sup_{x\in\mathbb{R}} \: (\mu*f)(x)<+\infty, $$ where $f(x)$ is some specific integrable functions, such as $f(x)=e^{-|x|}$, ...
3
votes
0answers
66 views

Explicit formula for the moment problem with Carleman's conditions

Suppose that $\mu_j$ are real numbers obeying the Carleman condition: $\sum_{j=0}^\infty 1/\mu_{2j}^{2j}<\infty$. Then it is well-known that in case the $\mu_j$ are positive definite, there is a ...
1
vote
1answer
193 views

Threshold for perfect Matchings in Bipartite graph

Consider the random bipartite graph with vertex classes of size $n$ and each edge being present independently with probability $p(n)$. I know one way to prove the threshold of a perfect matching is ...
2
votes
1answer
278 views

Is there any result for upper bounding the tail of a sum of r.v.s by another tail (with a different threshold)?

Suppose $X_i$s are independent random variables. We can make assumptions about $X_i$, e.g., $X_i\in [0,1]$. Let $X=\sum_i X_i$ and $u=E[X]$. Is there any result of the following type (relating one ...
0
votes
0answers
45 views

What is the concentration of measure for Gaussian random variables which are independent, but are transformed?

This might be a too easy question for Mathoverflow, but Googling led to similar questions and answers here (though not the one I was looking for). The question is split into two: I have a matrix $X ...
1
vote
2answers
256 views

Expected matching in a bipartite graph

Consider a random bipartite graph constructed on vertex classes of size $n$ with each edge present independently with probability $p$. How could I go about calculating the size of the expected ...
0
votes
0answers
27 views

How to compute selection probability of balls in a range [closed]

I have a question about probability that need your help. I assume that I have balls that are numbered from 1 to 100. The probability selection each ball is followed uniform distribution. I divide ...
1
vote
1answer
201 views

Is there an analytic solution for this partial differential equation?

The Fokker-Planck equation for a probability distribution $P(\theta,t)$: \begin{align} \frac{\partial P(\theta,t)}{\partial ...
0
votes
0answers
94 views

A hypothesis test question [migrated]

Let $X_i$ (for all integer $i$)be Bernoulli random variables (which takes either value -1 or 1, with equal probability). Define a random variable $Y$ to be $Y=\sum_{i=1}^d{X_i}$, where $d$ is a hidden ...
2
votes
1answer
93 views

What is the distribution of the maximum nearest-neighbor distance of a point cloud sampled from a solid body like?

Let $\mathcal{B} \subseteq \mathbb{R}^n$ be an $n$-dimensional solid body. Assume that we sample $N$ points, say $S = \{ x_1, ..., x_N \}$, from $\mathcal{B}$ uniformly at random. Consider the ...
3
votes
1answer
308 views

Non-asymptotic large deviations for a convex set

Let $X_1,\dots,X_n$ be $n$ i.i.d random variables taking values in a Polish vector space $\mathcal{X}$ and with (Borel) probability distribution $\mu$. For any convex, compact $\Gamma \subset ...
2
votes
1answer
550 views

method of moments and Laplace transform from Shepp and Lloyd

Again from the Shepp and Lloyd paper "ordered cycle lengths in a random permutation", I found this puzzling equality. This one might require access to the paper itself since it's quite a mouthful: In ...
4
votes
0answers
98 views

Young Tableau Box Correlations

Let $T$ be a uniformly random Standard Young Tableau (SYT) of shape $\lambda=(\lambda_1,\cdots,\lambda_k)$ with $|\lambda|=n$. Let $T_{ij}$ denote the value in box $(i,j)$. I'm interested in what can ...
4
votes
3answers
1k views

Correspondence between Viterbi algorithm and Smith-Waterman

Viterbi is an algorithm for finding the maximum likelihood assignment to the hidden variables of an HMM, given the observed variables (we know the transition and emission probabilities of the HMM). ...
4
votes
2answers
201 views

Is $B(t-1)$ an Ito process?

Let $I(\cdot)$ be an indicator, and $B_{t}$ be an 1-dim standard Brownian motion in a nice filtered probability space $(\Omega, \mathcal{F}, P, \mathcal{F}_{t})$. We consider a random process $$Y_{t} ...
5
votes
1answer
318 views

How many random matrices does it take to generate a matrix algebra?

Let $\mathbb{F}$ be a finite field. Let $A\le \mbox{Mat}_n(\mathbb{F})$ be a matrix algebra. Is there a good bound on the number $k$ of random elements $a_1,\dots,a_k\in A$ that one needs to take ...
31
votes
2answers
859 views

Random sequence of integers in $\{1, 2, \dots, n \}$ which is “everywhere probably increasing” - how long can it be?

Let $D=(d_1,d_2,\dots,d_k)$ be a sequence of correlated random variables. $D$ is "everywhere $r$-probably increasing" if the event $d_j > d_i$ has probability $\geq r$ for all $j > i$. Fix $r ...
2
votes
1answer
97 views

Criterion for weak convergence of probability measures on S' or D'

Let $X_n$ in $S'$ and $\mu_n$, $\mu$ in $M(S')$. $S'$ is the space of tempered distributions. I'm looking for a reference that says if $< f, X_n >$ converges in distribution to $< f,X>$ ...
1
vote
1answer
115 views

Interchanging limits for doubly indexed random sequences

I've encountered the following problem which seems to be quite standard but for which I can't find any proper references (asking on mathematics SE didn't bring up any answers so I'm reposting my ...
24
votes
6answers
1k views

Random Alternating Permutations

An alternating permutation of {1, ..., n} is one were π(1) > π(2) < π(3) > π(4) < ... For example: (24153) is an alternating permutation of length 5. If $E_n$ is the number of ...
0
votes
1answer
689 views

A generalized urn-ball matching problem; Complicated combinatoric/probabilistic limit

I'm looking for a generalization to the urn-ball matching problem. As a reminder of what I've got in mind, here's the simple version: Randomly assign (with replacement) $N$ balls to $M$ urns. ...
18
votes
0answers
386 views

Human Knot game

In the popular game "Human Knot", a group of people stands in a circle and each person grabs another person's hands at random (one with the left hand and one with the right hand). The goal is to ...
1
vote
1answer
84 views

Probability of sub-sequence of exact length to occur

Let's suppose that I have a sequence of length $L$ of uniformly distributed random numbers on interval $(a,b)$. How can I calculate probability that increasing sub-sequence of length $M,M <L, $ ...