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.
9,022 questions
2
votes
2
answers
2k
views
Question about Banach's matchbox problem.
Hi,
I've been struggling with this for awhile ( http://en.wikipedia.org/wiki/Banach%27s_matchbox_problem)
and I put together this little bit of Python code
...
- 1,116
8
votes
2
answers
655
views
Random walks on graphs: Cover time and blanket time
Winkler and Zuckerman conjectured that the blanket time is within a constant factor of the cover time. The conjecture was recently proved. The cover time $C$ is the expectation of the first time $t$ ...
CommunityBot
- 1
7
votes
1
answer
804
views
Random, Linear, Homogeneous Difference Equations and Time Integration Methods for ODEs
Most methods (that I know of) of numerically approximating the solution of ODEs are "general linear methods". For this type of method, the so-called 'linear stability' is examined by applying the ...
CommunityBot
- 1
11
votes
6
answers
5k
views
Secret Santa (expected no of cycles in a random permutation)
In a Secret Santa game, each of $n$ players puts their name into a hat and then each player picks a name from the hat, who they buy a Christmas present for. Obviously, if someone picks their own name ...
- 28k
3
votes
3
answers
2k
views
Statistics of a simple Markov chain
Imagine a two-state Markov chain which hops between the states $\pm 1$ with probability $p<1/2$, so that the autocorrelation function after $k$ steps is
$\rho_k = (2p-1)^k$
If I take an ...
- 2,135
4
votes
2
answers
744
views
Properties of a continuous-time semi-Markov process as t -> \infty
I am interested in calculating properties of a continuous-time random walk problem which I believe is a type of semi-Markov process.
I have states of the form $n_\pm \in \mathbb{Z} \times \{ +, -\}$. ...
- 61.9k
9
votes
1
answer
1k
views
A Game of Knights and Queens
Let $m,n,u,v \in \mathbb{N}$ be parameters with $m,n \geq 3$. Suppose two players play a game on a $m \times n$ chess board and we denote the squares of the board by the set of points $ (i,j) $ such ...
CommunityBot
- 1
0
votes
1
answer
578
views
One-Variable Optimization Problem
$W_{opt}=\arg \{\max(\pi_0 F_{L_0}(W)-\frac{\pi_1}{W}\int_0^W F_{L_1}( \alpha )d \alpha )\}$
subject to $\quad \int_0^W F_{L_0} (\alpha)d\alpha <\xi$
We should find analytically the optimal $...
- 23
11
votes
3
answers
743
views
Rainbow matchings (in random graphs)
Suppose we have an $(n,n)$-bipartite graph with edges colored with $k$ colors. Is anything known about the existence of rainbow matchings (i.e. a matching that uses each color exactly once, for $k=n$) ...
- 6,342
4
votes
0
answers
580
views
Monotonic properties of harmonic functions on graphs
I have a question concerning monotonic properties of "generalized harmonic functions" on graphs. I am a physicist and I didn't take any separate courses in neither graph theory nor discrete harmonic ...
- 965
1
vote
0
answers
265
views
"Lift and project" procedure for matrices
Definition. Let us call $n\times n$ matrix with non-negative entries good if sum of every row and column is equal to $1/n$.
Suppose we have a good matrix $A$. Let us consider the following strange "...
- 1,791
3
votes
2
answers
919
views
a point process is characterized by its void probabilities
Consider a planar point process $X$ and call $N_A = \text{Card}\big( X \cap A\big)$ the number of points inside the subset $A \subset \mathbb{R}^2$. If one knows the law of $(N_{A_1}, \ldots, N_{A_r})$...
- 113
16
votes
2
answers
4k
views
Is the space of continuous functions from a compact metric space into a Polish space Polish?
Let $K$ be a compact metric space, and $(E,d_E)$ a complete separable metric space.
Define $C:=C(K,E)$ to be the continuous functions from $K$ to $E$ equipped with
the metric $d(f,g)=\sup_{k\in K}\ ...
- 11
4
votes
1
answer
782
views
A simple problem in markov chains
I'm trying to understand a 1954 paper of Kubo intitled "Note on the stochastic theory of resonance absorption". The specific problem can be stated mathematically as follows: let $X(t)$ be a random ...
- 5,721
3
votes
0
answers
696
views
Expectation, multinomial distribution, and monotonicity (A conjecture)
Let $n$ and $k$ be two positive integers. Let $S = \{ \mathbf{p} \in \mathbb{R}^k : \mathbf{p} \geq 0, \sum_{i=1}^k p_i = 1 \}$ (i.e., a simplex).
Consider a function $\mathbf{f}:\mathbb{Z}^k \...
- 117
5
votes
4
answers
629
views
Process equivalent to conditional probability
Hi,
Having a random variable $X$ I am trying to find a stochastic process $Z_t$ such that:
$$P[Z_t>T] = P[X > T | X > t]$$
for all $T>t$, or a proof that such a process does not exist.
...
CommunityBot
- 1
2
votes
0
answers
1k
views
Can we pass to the limit in Poincaré-Jaynes-Bretthorst interpolation and deconvolution?
In Science and Hypothesis, chapter XI, The calculus of probabilities, Henri Poincaré deals informally with the fundamental problem of interpolation. He concludes (see http://ia600308.us.archive.org/21/...
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?...
- 549
2
votes
1
answer
4k
views
Random variables with same distribution
Consider probability space W with pair of random variables having same distribution. On how much this variables distinct in terms of W symmetries? Namely, let's talk about automorphism as measure-...
- 17k
6
votes
1
answer
819
views
Birkhoff ergodic theorem for dynamical systems driven by a Wiener process
At the risk of asking a stupid question I have the following problem.
Suppose I have a measure preserving dynamical system $(X, \mathcal{F}, \mu, T_s)$, where
$X$ is a set
$\mathcal{F}$ is a sigma-...
- 23.2k
5
votes
1
answer
781
views
Does a log-concave function on a convex set extend continuously to the boundary?
Let $U$ be an open convex set in a locally convex space $X$, and let $f : U \to [0,1]$ be a log-concave function on $U$ (i.e., bounded and real-valued). Under what conditions does $f$ have a ...
- 5,743
16
votes
4
answers
3k
views
"Uniform probability" on a set of naturals
It's an obvious and well-known fact that there is no uniform probability measure on a set of natural numbers (i.e. the one that gives the same probability to each singleton).
On a recent probability ...
- 9,756
5
votes
1
answer
623
views
For which values of $N$ is known the Lieb-Simon Inequality for $Z_N$ Models ?
Background:
Let $\mathbb Z^d$ denote the $d$-dimensional integer lattice with norm $|x|=\sum_i|x_i|$.
For each $x\in\mathbb Z^d$ we associate a spin variable, $\sigma_x$ taking values on the set
$\{...
CommunityBot
- 1
8
votes
2
answers
2k
views
How does a tournament's structure affect the likelihood that the best player will win?
Background
The origin of this question is a conversation I had with some friends a few years ago. At the time, Roger Federer and Tiger Woods were dominating professional tennis and golf, respectively,...
CommunityBot
- 1
11
votes
2
answers
880
views
Covering a random graph with spanning trees.
Let $G=(V,E)$ be a connected graph, say $V=\{1,\ldots,n\}$. Let $F=(V,E')$ be a uniformly random forest in $G$. (In other words, $E'$ is a subset of edges $E$ not containing a cycle, and it is ...
- 173
3
votes
2
answers
2k
views
Why is Beta the maximum entropy distribution over Bernoulli's parameter?
Why is Beta(1,1) the maximum entropy distribution over the bias of a coin expressed as a probability given that:
If we express the bias as odds (which is over the support $[0, \infty)$), then Beta-...
- 1
5
votes
1
answer
1k
views
Concentration of Measure for Power Law
I have a power law distribution $X$ with exponent $c$: $$p(X=t) = \left\\{\begin{array}{cl}(c-1)/t^{c} & t \geq 1 \\\\ 0 & t < 1\end{array}\right.$$
From $X$ I take $n$ independent samples ...
CommunityBot
- 1
4
votes
1
answer
799
views
Results for Hitting Times of (Not Stationary) Ito Processes
Let $W_t$ denote the Wiener process and let
$$
dX_t = a(t, X_t) dt + b(t, X_t) dW_t
$$
be an one dimensional Ito SDE (stochastic differential equation, see Ito stochastic calculus).
A hitting time $...
- 22.3k
10
votes
2
answers
1k
views
Continuity of the mutual information
The mutual information $I(\mathfrak A_1;\mathfrak A_2)$ of two complete $\sigma$-algebras $\mathfrak A_1$ and $\mathfrak A_2$ in a Lebesgue probability space $(X,m)$ is the integral of the logarithm ...
- 17k
8
votes
2
answers
4k
views
Infinite sum of random variables: subtle convergence question?
I have a sequence Xj of random variables, each of which individually is uniformly distributed on the unit circle in the complex plane, and a corresponding sequence cj of positive coefficients. My ...
CommunityBot
- 1
10
votes
2
answers
2k
views
How to sample pairwise independent gaussians
If $X_1, \ldots , X_k$ are i.i.d normal random variables with mean $0$ and variance $1$, then is there a way to sample $Y_1, \ldots , Y_m$ for $m=\omega(k)$ such that each of the $Y_i$'s is a normal ...
- 1,468
7
votes
1
answer
1k
views
If $H$ is a separable Hilbert space, is $L^2(H)$ separable?
Let $H$ be a separable Hilbert space, and let $\gamma$ be a Radon probability measure on $H$ with mean zero and covariance operator the identity $I$.
Is the Hilbert space $L^2(H,\gamma)$ separable?
CommunityBot
- 1
0
votes
1
answer
801
views
Information criteria for ridge regression
Hi -- is there any analogue or adjustment of, say, Schwartz Bayesian (or other) information criterion that would be applicable to model selection in ridge regression with a given ridge parameter $\eta$...
- 2,791
3
votes
2
answers
833
views
Two geometric probability questions (one answered, one more to go)
Given $n$ independent uniformly distributed points on $S^2$, what's the distribution of the distance between two closest points?
Consider $n$ iid uniform points on $S^1$, $Y_1, \ldots, Y_n$, in ...
- 1,533
1
vote
1
answer
294
views
Stability of discrete queue (new twist)
Hi, I am new to queueing theory. I am interested in a question that I feel should be fairly basic, yet I haven’t really found a clear solution to it. Hopefully somebody here can help me.
We have a ...
- 501
1
vote
4
answers
2k
views
How is a permutation taken as an equivalent of a hash function in MinWise independent permutations?
In the paper on MinWise independent permutations (MinWise independent permutations), the authors say that it is often convenient to consider permutations rather than hash functions (Pg-3).
While I ...
- 2,401
0
votes
0
answers
293
views
Open Jackson network with deterministic arrivals.
Dear Friends,
Is there any known Jackson-like theorem for an open Jackson network with deterministic arrivals?
Thanks,
Michael.
- 85
14
votes
5
answers
4k
views
Is there an extension of the Arzela-Ascoli theorem to spaces of discontinuous functions?
The Arzela-Ascoli function basically says that a set of real-valued continuous functions on a compact domain is precompact under the uniform norm if and only if the family is pointwise bounded and ...
- 279
1
vote
2
answers
237
views
Strongly correlated? Terminology question
Suppose $X$ and $Y$ are jointly distributed real-valued random variables and for all outcomes $\omega_1$, $\omega_2$, we have
$$
X(\omega_1)\le X(\omega_2)\quad\Longrightarrow\quad Y(\omega_1)\le Y(\...
- 24.8k
7
votes
1
answer
357
views
maximal coordinate on a sphere
What is the easiest (preferably without calculations) way to see that the mean value of $\max(x_1,x_2,\dots,x_n)$ on the sphere $\mathbb{S}^{d-1}= \{ (x_1,\dots,x_n):\ x_1^2+\dots+x_n^2=1 \}$ behaves ...
- 1,302
0
votes
0
answers
319
views
Estimating a multinomial sum
I have the following sum
\begin{equation}
\sum_{r_1=q+1}^{\tau}\dots\sum_{r_\lambda=q+1}^{\tau}{\tau\choose r_1,\dots,r_\lambda,\tau-r_1-\dots -r_\lambda} (\Lambda-\lambda)^{\tau-r_1-\dots-r_\lambda}
\...
15
votes
3
answers
2k
views
Wiener process related counterexample
The Wiener process is defined by the three properties:
1. $W(0) = 0$,
2. $W(t)$ is almost surely continuous, and
3. $W(t)$ has independent increments with $W(t) - W(s) \sim N(0, t-s)$ (for $0 ≤ s &...
CommunityBot
- 1
2
votes
1
answer
186
views
scalar diffusions are reversible
It is well known that under mild assumptions a scalar diffusion $dX_t = a(X_t) dt + \sigma(X_t) dW_t$ with invariant probability distribution $\pi$ is reversible. This is indeed not true for ...
- 17k
1
vote
1
answer
356
views
Statistical inequality
Let $X$ be a finite discrete variable and $X\ge0$. Is it true that
$$16\operatorname{Var}(X) \le \left[8{\mathbb E}(X) + \operatorname{Range}(X)\right]\operatorname{Range}(X)$$
where $\operatorname{...
- 303
10
votes
2
answers
602
views
What is the probability that every pair of students is at some point in the same classroom?
A cohort in a school consists of 75 students who study for 6 years. Each year, the students are randomly distributed into 3 classrooms of 25 students each. What is the probability that, after 6 years, ...
CommunityBot
- 1
2
votes
2
answers
391
views
linear ordering of color balls
Suppose that $n+m$ balls of which $n$ are red and $m$ are blue, are arranged in a linear order, we know there are $(n+m)!$ possible orderings. If all red balls are alike and all blue ball are alike, ...
- 32.1k
0
votes
2
answers
294
views
Relationship between these two probability mass functions.
If I have two different discrete distributions of random variables X and Y, such that their probability mass functions are related as follows:
$P(X=x_i) = \lambda\frac{P (Y=x_i)}{x_i} $
what can ...
CommunityBot
- 1
19
votes
5
answers
8k
views
What is the probability that two random walkers will meet?
It is a well known result that a random walk on a 2D lattice will return to the origin see Polya's random walk constant. Based on this, it is not a big stretch to conclude that the random walk will ...
- 11
21
votes
0
answers
578
views
Density of first-order definable sets in a directed union of finite groups
This is a generalization of the following question by John Wiltshire-Gordon.
Consider an inductive family of finite groups:
$$
G_0 \hookrightarrow G_1 \hookrightarrow \ldots \hookrightarrow G_i \...
CommunityBot
- 1
0
votes
2
answers
339
views
Efficient Method for Calculating the Probability of a Set of Outcomes?
Let's say I'm playing N different independent "games". For each game, I know the probability of winning, the probability of tying, and the probability of losing.
From these values, I've also ...
- 29.8k