0
votes
0answers
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
0answers
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
1answer
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
0answers
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
2answers
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
2answers
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
2answers
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
0answers
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
1answer
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
1answer
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
2answers
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
2answers
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
0answers
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
1answer
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
1answer
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
3answers
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
2answers
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
2answers
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
1answer
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
3answers
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
0answers
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
1answer
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
1answer
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
2answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
3answers
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
0answers
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
7answers
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
2answers
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
1answer
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
0answers
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
1answer
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
0answers
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
2answers
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 ...