All Questions
31 questions
4
votes
1
answer
261
views
What is the convergence rate of this "infinite monkey"-type probability?
Cross-posted from Math Stack Exchange, where it hasn’t received an answer yet:
Let $S$ be a finite set and $n,m\in\mathbb N$. Consider the process $R=(R_i)_{i\in\mathbb N}$ where all $R_i$ are iid ...
- 141
0
votes
1
answer
335
views
How far does a random walker travel before returning to the origin?
Consider a (continuous time) simple symmetric random walk on $\mathbb Z$, starting from the origin. Let us denote this random walk by $\{X_t: t\geq 0\} $. It is well known that this random walk is ...
- 59
3
votes
0
answers
54
views
Multi-type Galton-Watson-like process where only majority-type is allowed to reproduce
Are you aware of any research papers that have explored a multi-type Galton-Watson process in which only particles of the majority type are permitted to reproduce in each generation?
I've been unable ...
- 56
2
votes
1
answer
115
views
Randomly chosen walk of fixed length
Let $G=(V, E)$ be the graph on vertices $V = \{0, \cdots, k\}^n$, where vertices $(v_1, \cdots, v_n)$ and $(w_1, \cdots, w_n)$ share an edge iff $\lvert v_i - w_i\rvert \leq 1$ for all $i$.
A walk of ...
- 138
6
votes
1
answer
355
views
Probabilistic problem on random spanning trees
Let $G(V,E)$ be a connected simple graph, where $V$ and $E$ denote respectively its vertex and the edge set respectively. Let $f: V\to \{-1,1\}$ a function mapping each vertex to a value in $\{-1,1\}$....
- 1,677
1
vote
1
answer
199
views
Rademacher complexity for a family of bounded, nondecreasing functions?
Let $\{\phi_k\}_{k=1}^K$ be a family of functions mapping from an interval $[a, b]$ to $[-1, 1]$.
That is, $\phi_k \colon[ a,b] \to [-1, 1]$ are nondecreasing maps on some finite interval $[a, b] \...
- 410
3
votes
1
answer
266
views
A linearly distributed version of the balls into bins problem
Some years ago, I found a paper with all the formulas for the balls into bins problem when the "areas" (i.e., probabilities to capture a ball) of the bins are all different. However, the ...
- 1,677
3
votes
0
answers
190
views
Probabilistic optimization problem on tree vertex selection without replacement proportional to the degree
We are given a tree $T(V,E)$ with $|V|=n$ vertices, where $V=\{v_1,v_2,\ldots, v_n\}$. We denote by $d_i$ the degree of vertex $v_i$ for all $i\in\{1,2,\ldots,n\}$.
In a sequential fashion, we select ...
- 1,677
2
votes
0
answers
103
views
Optimization problem on randomly selecting subintervals from a given interval with combinatorial constraints
We select uniformly at random $k$ pairwise disjoint intervals from a given interval $[0,s]$ with length respectively equal to $\ell_1, \ell_2, \ldots, \ell_k\ $, i.e., we select uniformly at random $k$...
- 1,677
1
vote
0
answers
663
views
The distribution of hitting time in 2D-lattice random walk [closed]
Assume a particle at $(0,0)$ with the same possibility of $1/4$ for moving up/down/left/right (i.e. random walk in 2D lattice). We define the stopping time 𝑇𝑐 as it hits $(a,b)$. How can we get the ...
3
votes
0
answers
516
views
The distribution of collision stopping time in 2D random walk
Assume two particles A at $(0, 0)$ and B at $(a, b)$ in 2D discrete grid, both of them have the same possibility of $\frac{1}{4}$ for moving up/down/left/right (i.e. 2D random walk). We define the ...
5
votes
3
answers
601
views
Convergence speed of a random dyadic rational generator
We are given a multiset $M$ of real numbers which initially is equal to $\{0,1\}$. In a sequential fashion, at each round $r\in\mathbb{N}$
two distinct instances $x_r$ and $y_r$ of $M$'s numbers are ...
- 1,677
5
votes
0
answers
130
views
Random process on a sequence of rolls of an $n$-sided die
Let $\ X:=X_{k\,n}\ $ be a random variable of a $n$-sided die where $\Pr(X=i)=\frac{1}{n}$ for each $i\in\{1,2,\ldots,n\},\ $ where $\ k\in\{1, 2, \ldots,n\}\ $ and $\ n\ $ are fixed. Let $t$ be a ...
- 83
2
votes
1
answer
195
views
Average number of elements of a subset S of a matrix A after inducing the rows and columns of m randomly selected elements from subset S
Let $A_{N{\times}N}$ be an $N{\times}N$ matrix and $\mathcal{S_{k}}$ be a subset of elements in $A$ such that exactly $k$ elements from every row and column in $A$ are in $\mathcal{S_{k}}$. Thus, $\...
1
vote
1
answer
107
views
Concentration of maxima of a random polynomial with Rademacher coefficients
Let $X_1,\ldots, X_n$ be independent Rademacher random variables (i.e. $\mathbb{P}(X_i=\pm 1)=1/2$). Consider the random polynomial $$P_{n}(t)=c+X_{1}t+X_2t^2+\cdots+X_{n}t^n.$$
Is it well known how ...
- 2,288
0
votes
1
answer
171
views
Closed form solution for a binomial coefficient relation?
In following, $x_{n}$ is a set of given numbers, n = 0, 1, 2, ...,
$y_{n}$ is defined by the following recursive relation of $x_{n}$:
For example:
${\displaystyle {x_{1}=x_{0}y_{1} }}.$
${\...
- 127
4
votes
1
answer
839
views
A balls into bins problem with combinatorial constraints
We are given $m$ balls and $n$ bins, with $m \ge n$. Each bin can contain at most $c$ balls (we assume that $c$ is an even integer). In a sequential fashion, at each time step, one ball is placed into ...
- 1,677
3
votes
0
answers
330
views
Random walk on $\mathbb{R}$ with "sticky" origin
Let $P_i$, $N_i$, and $Z_i$, $i\in\mathbb{N}$ be r.v.'s with the $P_i$, $N_i$, and $Z_i$ being identically distributed with known pdf's $f_P$, $f_N$, and $f_Z$, respectively; and with no dependence ...
- 313
6
votes
1
answer
224
views
A Markov consensus
Consider the following process. You start with $n$ nodes in different colors $c=c1,c2,...$ (representing an opinion). Say, $n=5, c=1,2,3,4,5$. Now each node checks which colors have weak majority (...
- 4,829
1
vote
1
answer
357
views
Does CLT hold for joint distribution of two dependent binomial variables?
Let $S_n$ and $T_m$ be two binomial variables satisfying $S_n\sim B(n,\frac12)$ and $T_m\sim B(m,\frac12)$. Define $\tilde{S}_n=\frac{2S_n-n}{\sqrt{n}}$ and define $\tilde{T}_m$ similarly. For any ...
- 111
0
votes
0
answers
87
views
Variation on stones in buckets
This is a spinoff, see Collecting stones in n buckets. Frankly speaking my only motivation is that I became curious: what happens if one redistributes the stones into the same buckets?
More ...
- 18.4k
4
votes
1
answer
299
views
Collecting stones in n buckets
There are $n$ stones distributed in $n$ buckets (initially one stone in each bucket). At each step the content of each bucket is put in a random bucket, chosen independently out of a set of $n$ new ...
- 1,269
4
votes
1
answer
421
views
Order statistic of Markov chain sample path and related probabilities
Consider a one dimensional sample path, denoted as $\{X(1), ..., X(t), ..., X(n)\}$, generated from a discrete time finite state (time homogeneous) Markov chain over states $\{1,...,m\}$, with ...
- 1,538
1
vote
1
answer
420
views
Poisson approximation of random sub-graphs
I add the edges of $G(n)$ the complete graph on $n$ vertices one by one, at random and without replacement, and denote by $G(n,m)$ the resulting Erdos Renyi random graph process. At step $m$ in the ...
- 468
2
votes
0
answers
143
views
Arctic Circle Theorems and the Wave Equation
I've seen the following remark in a number of papers but don't know what to make of it. In this paper by Cohn, Elkies and Propp, it is mentioned that the normalized average Height function $\mathcal{H}...
- 4,952
3
votes
1
answer
179
views
Domino Shuffling and Warren's process
In this paper by Nordenstam, it is shown that a certain interlacing particle process that arises from uniformly random Aztec diamond tilings is amazingly similar to Warren's process. One of the ...
- 4,952
4
votes
2
answers
356
views
Ruin time for a two-input "risk only" slot machine
Imagine a "risk only" slot machine that takes 'coins' corresponding to some real number fraction of a dollar $p$, returns the coin with probability $p$, and eats the coin with probability $(1-p)$. ...
- 41
18
votes
2
answers
1k
views
Random Walk on $\mathbb{R}$ with Uniformly Distributed Steps and "Reflective" Boundary at Origin
A particle lies on the real number line at the origin. For each step taken, the particle moves from its current position a distance (and direction) chosen equi-probably from range $[-1,r]$. However, ...
- 313
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)...
- 4,952
2
votes
1
answer
134
views
Completion time of a process on a tree
Given is a constant degree rooted tree of depth $D$. It is also known that the total number of nodes in the tree is at most $D^2$. There is a probabilistic process with discrete time steps on the ...
- 501
7
votes
4
answers
1k
views
Recent impressive combinatorial developments in probability theory
In the preface to the second edition of Daniel Stroock's book "Probability Theory: An Analytic View", there is this striking claim (on p. xv)
... I suspect that, for at least a decade, the most ...
- 1,302