# Tagged Questions

**0**

votes

**0**answers

55 views

### Probability of differently loaded dice summing to a value

I have a real world problem that boils down to the following:
I'm playing dice. I have $n \approx o(10)$ differently biased die. The probability of the $i^{th}$ die showing $x_i$ is given by ...

**1**

vote

**0**answers

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

**2**

votes

**1**answer

108 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

84 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

152 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

96 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

34 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

150 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

190 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:
...

**4**

votes

**1**answer

187 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

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

**3**

votes

**0**answers

88 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

206 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

106 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

175 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

175 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

113 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

271 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

306 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

135 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

176 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

200 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

202 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

204 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

120 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

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

**3**

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

**25**

votes

**3**answers

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

**13**

votes

**2**answers

522 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

256 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

361 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

866 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

175 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

347 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

246 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

238 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

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

**4**

votes

**0**answers

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

**1**

vote

**1**answer

134 views

### Limiting probability question [closed]

Let $X$ denote an $m\times n$ matrix and suppose that each value $x_{ij}$ is an integer that is selected uniformly at random from ${1,\dots,n}$, independently of all other values. If we fix $m$ and ...

**11**

votes

**0**answers

488 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, ...

**3**

votes

**1**answer

124 views

### Random RSK and Plancherel Measure

Let $(X_1,X_2,\ldots)$ be a sequence of i.i.d. random variables. It is known that if these random variables are distributed uniformly on the unit interval, then applying the RSK algorithm to this ...

**33**

votes

**3**answers

2k views

### the following inequality is true，but I can't prove it

The inequality is
\begin{equation*}
\sum_{k=1}^{2d}\left(1-\frac{1}{2d+2-k}\right)\frac{d^k}{k!}>e^d\left(1-\frac{1}{d}\right)
\end{equation*}
for all integer $d\geq 1$. I use computer to verify ...

**1**

vote

**0**answers

83 views

### The balls and bins model: bounding the marginal contributions in the m>>n regime

Consider the standard balls and bins process, where $m$ balls are thrown into $n$ bins, and consider the case where $m >> n$. Denote the load on bin $i$ by the RV $L_i$.
Given a set $S ...

**36**

votes

**7**answers

3k views

### Conway's game of life for random initial position

What is the behavior of Conway's game of life when the initial position is random? -- We can ask this question on an infinite grid or on an $n$ by $n$ table (planar or on a torus). Specifically ...

**16**

votes

**2**answers

2k views

### Boys and Girls Revisited

Consider a country with $n$ families, each of which continues having children until they have a boy and then stop. In the end, there are $G$ girls and $B=n$ boys.
Douglas Zare's highly upvoted answer ...

**0**

votes

**1**answer

149 views

### n balls, k colors, expected color change problem [closed]

I was asked this question during my interview recently and despite the amount of thinking i put into this, I am yet to figure it out:
Given $n$ balls which are painted by $k$ colors. Let $s_i$ ...

**0**

votes

**0**answers

145 views

### An interesting version of the problem “balls into bins”

Consider n people, each has k identical balls. Each people choose k different bins from m bins, constrained by the condition that there are no two people choose exactly the same k bins. For instance, ...

**2**

votes

**1**answer

257 views

### A Johnson-Lindenstrauss lemma for finite fields?

Given $m$ points in $\mathbb{R}^N$, the Johnson-Lindenstrauss lemma guarantees the existence of a linear operator $\mathbb{R}^N\rightarrow\mathbb{R}^n$ that nearly preserves pairwise distances between ...

**0**

votes

**0**answers

73 views

### Pruning copies of an element from a multiset via a uniform random selection process - does vigilance matter?

This is an extension of a previous question of mine (nicely answered by Douglas Zare): Filling a bin with one type of element when uniformly selecting from a set of two (with bias)
Say I fill a ...

**17**

votes

**2**answers

832 views

### Expected edit distance

The edit or Levenshtein distance between two strings is the minimum number of single symbol insertions, deletions and substitutions to transform one string into another. For example ...