3
votes
1answer
78 views

Uniformly permutation and the length of a size biased cycle

The cycle containing $1$ of a uniform permutation has length which is uniformly distributed. I was wondering if the converse is true: Suppose $\sigma$ is a permutation on $\{1,\dots,n\}$ and let ...
5
votes
0answers
120 views

Operator connected with Hermite polynomials

For $n \geq 1$, define the following operator $M_n$ on the ring of all polynomials with real coefficients. $$M_n P(x) = nP(x)^2 - x \int_0^x (P'(t))^2 \, \mathrm{d}t$$ Monomials $x^k$ are mapped to $n ...
0
votes
1answer
75 views

Probability of k overlapping subsets in N trials

Ok, here is what I am attempting to find an answer to: I draw M uniformly random subsets of size K from the set of numbers $\Omega=\{1, \dots, N\}$ (where uniformly random means that each unique ...
0
votes
1answer
288 views

Basketball shots and stopping rule

Moved over from StackExchange. You are taken to play a basketball game where you can shoot basketballs at n slots using a machine that is equally likely to shoot the balls into those n slots. You can ...
7
votes
3answers
624 views

A conjecture about the entropy of matrix vector products

Consider a random $n$ by $n$ circulant matrix $M$ whose entries are chosen independently and uniformly from $\{0,1\}$. Let $M'$ be the $m$ by $n$ matrix which is formed by taking the first $m$ rows of ...
1
vote
1answer
187 views

A problem in symbolic dynamics

I got a fun problem. Define the alphabet $\mathcal{A}=\{0,1,2\}$ and the set $\mathcal{A}^{\leq n}=\{ x_1x_2\ldots x_n: x_i\in \mathcal{A}\}$ of words of length $n,$ for each $n\in\mathbb{N}.$ ...
5
votes
2answers
248 views

Balls and bins with color

Say I have $n$ balls each of $k$ different colors (i.e. $nk$ balls altogether), and I throw these balls independently into $N$ bins. Is there anything that can be said (in expectation, limits with ...
0
votes
1answer
203 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
1answer
168 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
0answers
102 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 ...
1
vote
1answer
93 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
1answer
175 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
1answer
307 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
0answers
52 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
1answer
213 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
3answers
196 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
3answers
575 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
1answer
137 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 ...
15
votes
1answer
314 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$, ...
1
vote
1answer
370 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
1answer
132 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
95 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
174 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
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
0answers
42 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
158 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
198 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
2answers
360 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
310 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
0answers
99 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
229 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
118 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
183 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
186 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
118 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
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
2answers
312 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
139 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
235 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
222 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
212 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
229 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
130 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
77 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
1answer
127 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
3answers
602 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
569 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
289 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
462 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 ...
10
votes
4answers
1k 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 ...