# Tagged Questions

**0**

votes

**1**answer

190 views

### two correlated processes

I apologize if this question is not placed in the right place. But I am having a hard time to figure it out. It would be greatly appreciated if some one could help me out.
Assume that there are two ...

**2**

votes

**1**answer

157 views

### Distribution of area of randomly placed circles

I've searched the web now for ages to try and find a paper on the asymptotic distribution of the area of the union of randomly placed discs on the plane. Ideally, I would be looking for the discs to ...

**3**

votes

**0**answers

87 views

### Convex hull of a discrete set of points

If i was to give an $n×n$ grid with each grid point having probability $p$ of being selected, would it be difficult to calculate distributions of various measures regarding the convex hull of all ...

**-2**

votes

**0**answers

35 views

### Random 0-1 matrices [migrated]

For $n,r∈N$, $1<r<n$, let $z(r,n)$ be the largest possible number of 0 entries in an $n×n$ matrix which has no $r×r$ submatrix whose entries are all $0$. (Here a submatrix is obtained by ...

**0**

votes

**0**answers

43 views

### Ratio of expected diameter and height of a conditioned Galton-Watson tree

A Galton-Watson tree is the family tree of a Galton-Watson process. Let $T_n$ denote a Galton-Watson tree conditioned on total population size $n$. The time of extinction is its height $H(T_n)$ and ...

**5**

votes

**1**answer

164 views

### Estimate the rank of a vector

Consider {0,1}-vectors $v$ with $n$ elements. For each $i\in[n]$ we are given $p_i = P(v_i = 1)$ and let us assume the $v_i$ are independent. We can therefore associate a probability to each of the ...

**3**

votes

**1**answer

296 views

### “the” random permutation

I recently looked at Permutations on the random permutation which seems to talk about the notion of random permutuation as a notion from logic rather than probability.
The random permutation is ...

**1**

vote

**0**answers

47 views

### Asymptotic results in unbalanced left $d$-regular expander graphs

Let $U = [n]$ and $V = [m]$ be sets of nodes with $n > m$ and $E = U\times V$ be a set of edges. Let $\mathcal{N}(S)$ be the set of neighbors of a subset $S$ from $U$ or $V$.
Call a graph $G = (U, ...

**5**

votes

**1**answer

207 views

### “strongly mixing” action on dimers?

In Local Statistics of Lattice Dimers we study a nice familiar object, domino tilings in the plane extending out to infinity.
His paper is going to discuss the frequency of various "motifs" in ...

**3**

votes

**3**answers

162 views

### Time-inhomogeneous Markov Chains

I'm trying to find out what is known about time-inhomogeneous ergodic Markov Chains where the transition matrix can vary over time. All textbooks and lecture notes I could find initially introduce ...

**4**

votes

**3**answers

563 views

### Analogy between Integers and Permutations

I am reading Andrew Granville's Anatomy of Integers and Permutations where it is argued the factorization of a permutation into disjoint cycles is analogous to the factorization of a number into prime ...

**7**

votes

**1**answer

128 views

### Distribution of entries of a doubly-sorted random matrix

Take an $n \times n$ random matrix whose entries are i.i.d. with uniform distribution in $[0,1]$. Look at the sums of the elements of each row and then permute the rows so that these sums form an ...

**11**

votes

**1**answer

209 views

### partition of infinite word onto permitted words

Consider words over binary alphabet $\{0,1\}$. Let $M$ be a set of finite words such that $M$ contains at least $c\cdot 2^n$ words of length $n$ for all large enough $n$ (for a constant $c$, ...

**2**

votes

**1**answer

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

**3**

votes

**1**answer

124 views

### Calculating the probability that all possible length $r$ subwords exists in a string, with or without overlaps allowed

Let $S$ be a length $L$ string, where each character in the string is chosen with uniform random probability over an alphabet with $q$ characters. For example, a binary string would imply $q = 2$, a ...

**1**

vote

**0**answers

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

**4**

votes

**2**answers

166 views

### Joint probability distribution as functions

Suppose $X$ and $Y$ are correlated random variables in a finite set ${\mathcal A}$, and let $f, g$ be functions that map elements from ${\mathcal A}$ to ${\mathcal B}$ for some finite set ${\mathcal ...

**3**

votes

**1**answer

100 views

### Proof for the emergence of a ranking with paired comparisons [closed]

Take a set {A, B, C, D, E}, and assume each of the set elements has a random real value attached to it between 0 and 1. For example, this gives us: {A, B, C, D, E} = {0.1, 0.9, 0.4, 0.6, 0.5}. Assume ...

**2**

votes

**0**answers

37 views

### Finding the number of leaf nodes at specific level of a random tree

Given a uniform recursive tree (URT) of size $N$ rooted at one node whereby the tree is generated as follows:
Starting with a root node, at each iteration, a new node is connected to one of the ...

**1**

vote

**0**answers

156 views

### An extrasensory perception strategy :-)

I asked this question at MSE some months ago
but I received only partial answers, so I put it here. The following sounds nice for me and I spent a good time during the investigation. But I am a ...

**0**

votes

**0**answers

193 views

### Sum over a product of binomial coefficients related to a collision problem

I am working on a certain collision problem. The probability of forming $j$ particles upon collision of $m$ and $n$ particles is given by the following equation:
...

**5**

votes

**2**answers

317 views

### Maximum distance between two consecutive points of N random points on a unit length line

I have encountered a seemingly simple question on distances of random points.
Place N points randomly and uniformly on the line segment [0..1].
How to derive the expectation (or the distribution) of ...

**0**

votes

**1**answer

303 views

### Pros and cons of probability model for permutations

I am studying probability model of random permetuation
Let $b(n; k)$ denote the number of permutations of {1,...,n} with precisely k
inversions ($inv(\pi)$). The analytic approach was considered by ...

**4**

votes

**0**answers

97 views

### Generating random weak k-bounded reverse plane partitions

Fix a partition $\lambda$. A weak reverse plane partition of shape $\lambda$ is a filling $0\leq \pi_{ij}$ of $\lambda$ with $\pi_{ij}\leq \pi_{kl}$ whenever $i\leq k$ or $j\leq l$. Note that ...

**1**

vote

**1**answer

219 views

### Sum of covariance matrix of products of dependent variables

Consider the sequences of random variables $\{X_i\}_{i=1}^n$ and $\{Y_i\}_{i=1}^n$, as well as the corresponding sequence of products, $\{X_i Y_i\}_{i=1}^n$. All $X_i$ share the same mean value, ...

**3**

votes

**1**answer

113 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**

votes

**1**answer

181 views

### An intutive reason why a “distance” metric may be a poor one for a procedure where we attempt to modify a string (mutating 0 OR 1 bits)

If I'm attempting to mutate one arbitrarily chosen binary string $s_a$, to another arbitrarily chosen binary string $s_b$, in the smallest number of steps (i.e. with the smallest number of mutations) ...

**6**

votes

**1**answer

183 views

### The time to drift a binary string from one state to another via deterministic selection of two possible random bit mutation procedures

I have some length $L$ binary string consisting of an ordered array of bits: $(b_1, b_2, ..., b_{L})$, where all bit values $b_i$ are originally set to zero. I'd like a particular set of $n$ bits to ...

**0**

votes

**1**answer

117 views

### Expected rank of players in a Bradley-Terry round-robin tournament

Let $[n]$=$\{1,\dots,n\}$ be a set of players in a round-robin tournament. Each player $i$ has an associated skill parameter, $\lambda_{i}$, and the probability that player $i$ defeats player $j$ is ...

**7**

votes

**2**answers

278 views

### Sets whose elements are mutually “weakly” coprime?

Fix $n$ and $k$. I want a set $S\subseteq\{1,\ldots,n\}$ with the property that for every $x\in S$,
$$\mathrm{gcd}\bigg(x,\prod_{y\in S\setminus\{x\}}y\bigg)<\frac{x}{k}.$$
How small should a ...

**4**

votes

**2**answers

310 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)$. ...

**6**

votes

**0**answers

137 views

### Uniformly sampling from the set of all simplicial maps

Let $K$ and $L$ be finite simplicial complexes that remain fixed throughout.
How does one efficiently sample (according to the uniform distribution) elements from the finite set of simplicial ...

**2**

votes

**1**answer

210 views

### Generalization on Coupon Collector's Problem

Player extracts card from the deck (which has infinite number of size) to obtain one of $k$ colors of cards. The possibility that the player pick a card with $i$th color is given by $p_i>0$. Of ...

**1**

vote

**1**answer

214 views

### Balls and bins: Exact probability

Suppose there are $m$ balls to be randomly thrown into $n$ bins ($m>n$). Let $X_i$ be the number of balls ending up in bin $i$.
Let $X_{max}$ be the heaviest bin and $X_{min}$ be the lightest bin. ...

**5**

votes

**2**answers

209 views

### Anticoncentration of the convolution of two characteristic functions

Edit: This is a question related to my other post, stated in a much more concrete way I think.
I am interested in anything (ideas, references) related to the following problem:
Suppose that $A ...

**3**

votes

**2**answers

223 views

### Cardinality of intersection of a random subset with a fixed subset

How can I simply prove the following fact:
Let $A := \{1, \dots n \}$ and $B := \{1, \dots, \lfloor \frac{n}{4} \rfloor \}$. Let $d \in (0,1)$ and let $R$ be a randomly choosen (with uniform ...

**7**

votes

**0**answers

126 views

### Generalised Polya's urn with i.i.d. replacement

Let $\mu$ be a fixed measure (possibly with moment conditions) on $\mathbb N$ and $X_1,X_2,\dots$ be i.i.d. samples from $\mu$. Start with one white and one black ball in the urn. At the $n$-th step, ...

**1**

vote

**1**answer

75 views

### Probability of seeing m nonzero bits in off any d consecutive bits in a circle of n bits

Suppose n bits are arranged circularly with given condition that random k of them are 1 and rest 0, and all possible d consecutive bits (total n possibilities) are looked at, what is the probability ...

**2**

votes

**1**answer

125 views

### Number rank-k 0-1 matrices (characteristic 0)

What is the number of $n\times n$ 0/1-matrices with rank $k$?
(The rank is taken over the rationals.)

**24**

votes

**3**answers

583 views

### What is the probability two random maps on n symbols commute?

It is well known that two randomly chosen permutations of $n$ symbols commute with probability $p_n/n!$ where $p_n$ is the number of partitions of $n$. This is a special case of the fact that in a ...

**12**

votes

**2**answers

554 views

### Laws of Iterated Logarithm for Random Matrices and Random Permutation

The law of iterated logarithm asserts that if $x_1,x_2,\dots$ are i.i.d $\cal N(0,1)$ random variables and $S_n=x_1+x_2+\cdots+x_n$, then
$$\limsup_{n \to \infty} S_n/\sqrt {n \log \log n} = \sqrt 2, ...

**7**

votes

**2**answers

277 views

### How to efficiently sample uniformly from the set of p-partitions of an n-set?

Let $n,p \in \mathbb{N}_+$ with $p \leq n.$ Let $\mathcal{P}$ denote the set of partitions of $\{1, \ldots, n\}$ into $p$ nonempty sets. How can I efficiently sample uniformly from $\mathcal{P}$?

**0**

votes

**1**answer

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

**9**

votes

**3**answers

933 views

### The probability for a streak when tossing a coin

I'm trying to solve the following problem:
Let's say I'm tossing a coin $N$ times. The coin is not fair, such that the probability for heads is $p_0$ and for tails is $1-p_0$.
What is the ...

**5**

votes

**0**answers

180 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)$.
...

**10**

votes

**1**answer

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

**5**

votes

**1**answer

250 views

### A colorful fractal structure on a graph provided by Wilson's algorithm: any explanation?

Consider a big finite rescaled piece of $\mathbb{Z}^2$, i.e. consider a unit square with a thick grid. Famous Wilson's method allows to generate a colored spanning tree of such a graph in a uniform ...

**1**

vote

**2**answers

240 views

### How many boxes so that there is $k$ of same of color from $n$ different colors?

Say you have $m$ boxes each of which is colored with one of $n$ colors. What should $m$ be so that the probability that there is atleast $k$ boxes with one same color is strictly greater than ...

**4**

votes

**0**answers

182 views

### Balls and bins — concentration bounds pertaining to the minimal load bin

Consider the standard balls and bins process, where $m$ balls are thrown uniformly at random into $n$ bins. Previous work has been done on estimating the value of the maximum load (i.e., the number of ...

**5**

votes

**0**answers

130 views

### Is there an Arctic Circle phenomenon for Amman-Beenker tilings?

I found some slides on tilings and one of them pertained to Amman-Beenker tilings. It looks like there is an Arctic Circle phenomenon similar to that for dominos or lozenges. Is there any ...