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,027 questions
0
votes
1
answer
4k
views
Calculate the probability of winning for a selected tic-tac-toe player
I am not a mathematician, I am a programmer. Sorry, if formulation of the problem is inexact.
I want to calculate the probability of winning for a selected tic-tac-toe player.
I have a directed graph ...
- 73.2k
1
vote
1
answer
484
views
A set of positive-measure not being a countable union of cylinder sets and zero-measure sets?
Let $(A^\mathbb{N}, \mathcal{B}(A^\mathbb{N}), \mu)$ be a measure space, where $A^\mathbb{N}$ is a set of one-sided sequences over a finite alphabet $A \subset \mathbb{N}$, $\mathcal{B}(A^\mathbb{N})$ ...
- 6,206
1
vote
0
answers
186
views
Shrinkage (or Stein's phenomenon) in low dimensions, discrete contexts
I am trying to understand shrinkage, or the Stein phenomenon. As someone without a statistics background, the focus in most introductory presentations on normal distributions and squared error loss ...
- 203
0
votes
1
answer
89
views
Is a $CD(K,\infty)$ space a length space?
Let $(X,d)$ be a complete and separable metric space endowed with a nonnegative Borel measure $\mu$ with support $X$ and satisfying
\begin{eqnarray}
\mu(B(x,r))<\infty,\quad\mbox{for every }x\in X\...
- 14.4k
1
vote
0
answers
190
views
Nontransitive dice: the least number of faces?
Here is an introduction to nontransitive dice. The question is: given $n$-player with a $m$-sided dice each one, the what is the minimum of $m$ for a fixed $n$ to produce nontransitivity?
Here is ...
CommunityBot
- 1
13
votes
1
answer
3k
views
random walk and Brownian motion on Riemannian manifold
As we know, the random walk on $\mathbb{Z}/n$ will converge(in some sense) to the Brownian motion on $\mathbb{R}$ when $n\to\infty$. I would like to know is there some higher dimensional analogy ...
CommunityBot
- 1
4
votes
1
answer
280
views
Approximation of an integral over the unit ball of L_1
For every $\varepsilon>0$ find a piecewise continuous function $q:[0,1]\rightarrow \mathbb{R}$ such that $\int_0^1 q(x)dx=1$ and
$$\int_{0}^1 \int_{0}^{s} \left|\frac{q(s)q(t/s)}{s}- \frac{q(t)q((s-...
- 9,486
1
vote
1
answer
276
views
A measure of closeness to a discrete set in a metric space
Consider a metric space $(M,d)$ and consider a collection of points $X_n := \{x_1,\dots,x_n\} \subset M$. Let
$$
N_\epsilon(y;X_n) := | \{ x \in X_n: d(x,y) \le \epsilon \}|
$$
where the RHS is ...
- 10.3k
3
votes
1
answer
784
views
Expected number of random binary vectors so that the form a basis
I would like to compute the expected number of vectors in $\mathbb{F}_2^n$ we need to draw (following a uniform distribution) so that they form a basis of $\mathbb{F}_2^n$, i.e., that we have $n$ ...
- 28k
6
votes
1
answer
273
views
Proof of a statement from Steele's "Probability theory and combinatorial optimization"
I am reading "Probability theory and combinatorial optimization" by J.M. Steele and am hung up on a statement made in Section 2.2 of Chapter 2, "Easy size bounds", in which it is stated (paraphrasing ...
- 96.4k
2
votes
1
answer
121
views
Expected length of a certain kind of nearest-neighbor graph
Suppose I have sets of points $Z_1,\dots,Z_N$, such that $|Z_i|=m$ for all $i$, and where all $m\times N$ points are independently distributed uniformly at random in the unit square. Can someone give ...
- 6,210
7
votes
2
answers
649
views
What's the standard name for sets of a given size with maximal probability (or a given probability and minimal size)?
The definition I'm going to give isn't quite the concept I really want, but it's a good approximation. I don't want to make the definition too technical and specific because if there's a standard name ...
- 833
5
votes
1
answer
492
views
Coupling of non-probability/sub-probability measures
A coupling of two probability measures $P,\tilde P$ on a Borel space $X$ is any probability measure on $X^2$ whose one-dimensional marginals are $P$ and $\tilde P$. In particular, for any such ...
- 12.7k
30
votes
4
answers
3k
views
Distribution of roots of complex polynomials
I generated random quadratic and cubic polynomials with coefficients in $\mathbb{C}$
uniformly distributed in the unit disk $|z| \le 1$. The distribution of the roots of 10000
of these polynomials are ...
CommunityBot
- 1
2
votes
1
answer
132
views
Computation of the mean of a random variable to estimate algorithm complexity
I made an incremental algorithm which I would like to evaluate the complexity. The algorithm works with a sliding window of size n.
To study the complexity, the window is considered full and the data ...
- 456
5
votes
0
answers
215
views
Asymptotics of a Splitting Process
Consider $p(n)$ defined recursively by $p(1)=1$ and
$\displaystyle p(n)=\frac{1}{(n-1)^n}\sum_{i=1}^{n-1}\left\{\sum_{j=i}^{n-1}(-1)^{j-i}{n \choose j}{j\choose i}(n-j)^j(n-j-1)^{n-j}\right\}p(i)$.
...
CommunityBot
- 1
4
votes
0
answers
284
views
Markov operators and existence of ergodic measures
My question refers to the yesterday's question (see here)
of John Learner and goes as follows:
Can we deduce the existence of an ergodic measure if we know that an invariant measure exists, but the ...
CommunityBot
- 1
7
votes
1
answer
512
views
Random walk over a function
Let $\{X_n\}_{n\geq 0}$ be a random walk. Let us assume that $\mathbb{E}X_1 =0$ and $\mathbb{E}X_1^2=1$. Let also $\mathbb{E}\exp(c|X_1|)<+\infty$ for some $c>0$ and $X_1$ has a law with ...
- 1,491
2
votes
0
answers
74
views
iterated mutinomial and hitting time
Let $N,k \geq 1$ be two integers and consider the following Markov chain on $[0,k\times N]^k$. It starts at $X^0=(N, N, \ldots, N)$ and $X^{n+1}$ is the realisation of a multinomial distribution with $...
- 2,133
3
votes
1
answer
403
views
Is there a probability density function providing the least expected value?
Fix constant reals $A>1$ and $D>0$. Let $f:\mathbb{R}\to[0,\infty)$ be a probability density function on $\mathbb{R}$, i.e. $\int_{-\infty}^\infty f(x)\, dx=1$, that is continuous almost ...
- 10.3k
3
votes
0
answers
474
views
What is the expected Cheeger constant of a random graph?
Recall that the Cheeger constant (AKA isoperimetric constant) of a graph $G$ is the infimum of $\frac{\partial S}{vol S}$ over all subsets $S$ of $G$ with volume no larger than $vol(G)/2$. I would ...
- 29.2k
18
votes
1
answer
3k
views
Let a function f have all moments zero. What conditions force f to be identically zero?
Throughout, let $f$ be a Lebesgue measurable function (or continuous if you wish, but this is probably no easier). (Questions with distributions etc. are possible also but I want to keep things simple ...
- 19.3k
1
vote
1
answer
761
views
On polynomial functions of random variables and independence
Suppose $Y_1, Y_2$ are independent real-valued random variables and whose distributions have a density with respect to the Lebesgue measure. Assume that all moments $\mathbb{E}Y_1^a, \mathbb{E}Y_2^b$ ...
- 6,711
4
votes
1
answer
904
views
distribution of the number of empty bins in a multinomial setting
Let $(X_1,X_2,\ldots,X_k)$ be a multinomial random vector with parameters $n, p_1, p_2, \ldots, p_k$ (i.e., we throw randomly $n$ balls into $k$ bins, so that for each ball, the probability of landing ...
- 19.3k
3
votes
1
answer
275
views
Conditional probabilities for all pairs of subsets in $\mathbb R^2$?
Parikh and Parnes showed that one can define a isometry-invariant finitely-additive conditional probability for all pairs of subsets of the interval. Can one extend this result to bounded subsets of $...
- 2,555
4
votes
1
answer
214
views
The d-dimensional matrix with columns (1,0,0…), (1/2,1/2,0,…), (1/3,1/3,1/3,0,…),…, (1/d,1/d,…,1/d)
During the course of physics research on nonequilibirum statistical mechanics involving the theory of majorization, I have come across a linear transformation on a d-dimensional vector space that I ...
- 28.6k
2
votes
0
answers
341
views
Marginalizing multivariate normal over defined interval
Hello everyone,
I am trying to obtain an analytic expression for the following Gaussian integral
$$\frac{1}{\sqrt{(2 \pi)^n |\Sigma|}} \int \kern-0.2em \cdots \kern-0.2em \int d\mathbf{x}_{\sim i} \;...
- 101
10
votes
2
answers
1k
views
Why do we want maps to be measurable (in countably-additive setting)
When I have to explain things that I am doing to people who did not do (or even did not learn) measure-theoretical probability, I think of getting a question in the title, and I am not sure I have ...
- 1,655
6
votes
0
answers
295
views
Is there an idempotent measure on the free LD system?
This is a follow up question to MO question "Idempotent measures on the free binary system?".
Let $(A,*)$ be the free binary operation on one generator which satisfies the left self distributive law:
...
CommunityBot
- 1
13
votes
1
answer
736
views
Idempotent measures on the free binary system?
Let $(S,*)$ be the free (non associative) binary system on one generator (so $S$ is just the set of terms in $*$ and $1$). There is an extension of $*$ to the space $P(S)$ of finitely additive ...
- 19.3k
2
votes
1
answer
788
views
Function of independent random variables cannot be independent of each variable?
Suppose $Y_1,Y_2,\ldots, Y_n$ are independent, where $Y_i$ is a continuous valued random variable with a density $p_{Y_i}(y_i)$ on its domain $\mathcal{D}_i\subseteq \mathbb{R}.$ Can one show that for ...
CommunityBot
- 1
9
votes
1
answer
642
views
Twisted random walks
Suppose the points of two random walks in $\mathbb{R}^2$ are given the
step number (or time) as a third coordinate, so that they become paths in $\mathbb{R}^3$.
Here are several pairs of walks of $n=...
- 151k
5
votes
6
answers
2k
views
Are all probabilities conditional probabilities? [closed]
We know that $P(A\mid B) = \frac{P(A \cap B)}{P(B)}$. So $P(B) = P(A\mid B)P(A \cap B)$. Thus are all probabilities conditional probabilities? Can one make a probability more accurate by introducing a ...
- 3,709
2
votes
0
answers
865
views
fourier decomposition of white noise
I found in some lecture notes that Brownian motion is defined by its Fourier series:
$$ B(t) = \sum_{m \in \mathbb{Z},\; m \neq 0} \frac{a_m}{m} e^{2\pi i \,mt} $$
Then I would get that its ...
0
votes
1
answer
599
views
A basic question on necessary and sufficient condition for positive recurrence
If state $j$ is recurrent and the following holds can it be called as positive recurrent ?
$$\lim_{n -> \infty}\frac{1}{n}\sum_{k=1}^{n}p_{jj}^{(k)} > 0$$
I know that this a necessary ...
5
votes
1
answer
421
views
Memory of Uniformly Random Dyck Paths
Let $D$ be the set of all Dyck paths on square grid of size $n\times n$. For any particular Dyck path, let $S(t)=X_1+X_2+\ldots +X_t$ store the path, where $X_i=\pm 1$. Being a Dyck path, we have $S(0)...
CommunityBot
- 1
4
votes
1
answer
2k
views
Probability of two vertices being connected in a random graph
Consider a random directed graph with $N$ vertices where each vertex $v$ has exactly one link to some vertex (maybe to itself) $u$ with known probability $a_{vu}$. What is the probability of ...
- 655
11
votes
1
answer
636
views
A simple proof for a theorem of Szekeres and Turán
Szekeres and Turán found in 1937 a formula for the sum of the squares and the sum of the fourth powers of determinants of all $n$ by $n$ matrices with $\pm 1$ entries. (The sum of squares case follows ...
- 1,343
6
votes
1
answer
396
views
Does a metric refine the weak-* topology on a dual space?
Let $X$ be a topological affine space over $\mathbb C$, with no additional assumptions. Let $X^*$ denote its dual space of continuous affine functionals $X \to \mathbb C$, equipped with the weak-$*$ ...
- 3,584
1
vote
1
answer
479
views
Distance between the product of marginal distributions and the joint distribution
Given a joint distribution $P(A,B,C)$, we can compute various marginal distributions. Now suppose:
\begin{align}
P1(A,B,C) &= P(A) P(B) P(C) \\
P2(A,B,C) &= P(A,B) P(C) \\
P3(A,B,C) &= P(...
- 49
5
votes
1
answer
765
views
Measure concentration for weakly dependent random variables
For an application quite alien to probability theory, I'd like to have a kind of measure concentration estimate, in the following spirit. Suppose that to every $1\le i,j\le n$ there corresponds a zero-...
CommunityBot
- 1
7
votes
1
answer
3k
views
What is characteristic function of maximum of i.i.d. random variables?
Is is possible to get characteristic function of maximum of i.i.d. random variable sequence? Such as $X_1, X_2$ are two i.i.d random variables, then what is characteristic function of $X=\max(X_1,X_2)$...
- 3,993
1
vote
0
answers
416
views
When does a proper Zariski closed set have measure zero with respect to a conditional measure?
Assume we have a probability measure $\mu$ over $\mathbb{R}^d$ that is absolutely continuous with respect to Lebesgue measure.
Given $m$ polynomials $p_1,\ldots,p_{m}\in \mathbb{R}[x_1,\ldots,x_d]$ ...
- 6,210
0
votes
2
answers
174
views
Joint distribution with specified marginals
Suppose we are given a probability distribution over a finite discrete product space $p(x,y)$ with marginals $p(x), p(y) > 0$ for each $x,y$ respectively. We are given two more marginal ...
- 37.7k
4
votes
2
answers
882
views
The probability distribution for vertex degree in a unit disc graph generated from random points on a plane
Imagine I cover an arbitrarily large plane with randomly placed points at some density $\rho$ s.t. the number of points in any randomly sampled area $A$ (of arbitrary shape and size) is $\approx A*\...
3
votes
1
answer
263
views
Extending Tarski's Theorem on invariant measures
Tarski's Theorem says that if $G$ acts on $X$ and $E$ is a non-$G$-paradoxical subset of $X$, then there is a finitely additive $G$-invariant measure $\mu:2^X\to[0,\infty]$ with $\mu(E)=1$.
I am ...
- 352
1
vote
2
answers
220
views
How to choose two random variables taking values in a finite space, with given distributions, such that probability that they are equal is maximized?
Let $A = \{1, 2,\dots, n\}$, and let $X$ and $Y$ be two random variables on the same space, taking values in $A$, and distributions given by:
$P(X = i) = p_i$, and $P(Y = i) = q_i$, for any $i\in\{1,2,...
- 14.4k
3
votes
1
answer
1k
views
Probability Density Optimization
I am working on an optimization problem which I am stuck on towards the end.
Essentially, I have two probability density functions in $\mathbb{R}^2$, call them $q(x,y)$ and $p(x,y)$, now I define ...
CommunityBot
- 1
1
vote
0
answers
1k
views
Expected value of the log of the factorial of a poisson distribution
I found the expression for the expected value of the falling factorial of a Poisson distribution ($\lambda^n$) from - http://en.wikipedia.org/wiki/Factorial_moment. Is there a similar expression for ...
- 6,210
1
vote
1
answer
613
views
Anyone has Kushner's book "Introduction to stochastic control" 1971? I need a theorem from it
In a paper I'm reading, it refers to Theorem 8, Page 217 of the book
"Introduction to Stochastic Control" H. J. Kushner, New York: Holt, Reinhart, and Winston 1971. Unfortunately I don't have it and ...
- 5,432