All Questions
Tagged with pr.probability co.combinatorics
802 questions
5
votes
3
answers
456
views
Probability that a sum of intependent random variables hits a point
Let $X_1,\ldots,X_n$ be independent random elements of a normed space $X$. Suppose that $\sup_{x\in X}\mathbb{P}(X_i=x)=p_i$. What is the best known upper bound for
$$\sup_{x\in X} \mathbb{P}(X_1+\...
- 19k
4
votes
0
answers
220
views
Navigation in a graph
The problem
Let $G=(V,E)$ be a graph. $k = O\left(\log(|V|)\right)$ distinct vertices are picked randomly from $V$. We call the set of chosen $k$ vertices $T$.
Assumptions about the graph: You may ...
- 323
2
votes
1
answer
312
views
Probability of a contiguous sub-sequence with different elements
Let $a$ and $b$ be two positive integers, and say $b\gg a$. Let $S$ be a random sequence with $ab$ elements, whose entries are all integers from $1$ to $a$, such that each number from $1$ to $a$ ...
- 24.8k
3
votes
0
answers
231
views
On a problem of sphere-packing for Reed-Solomon codes
Suppose we have an $[n, k+1, n-k]$ Reed Solomon code $\mathcal C$ over $\mathbb F_q$, where $n-k=d$ is the minimum distance, and suppose that $d=2t+1$. We know that for every $r \in \mathbb F_q^n$ the ...
- 307
0
votes
1
answer
71
views
Monotonicity of the gap of permutated sequence
Let $a$ be an arbitrary sequence and denote by $\mbox{gap}_k(a) = a_{(k)} - a_{(k+1)}$, where $a_{(k)}$ is the $k$th largest component of $a$. Of course, $k+1$ should be no larger than the length of $...
- 23.7k
5
votes
2
answers
372
views
Random Vornoi Diagrams (particular measures)
This is my second question about Random Voronoi diagrams, in my first question was given some excellent advice but i was not clear in explaining what i was looking for.
I'm interested to know ...
CommunityBot
- 1
10
votes
2
answers
1k
views
Random Voronoi Diagrams
I'm interested in what research has already been done with regards to the statistics of random voronoi diagrams. I have had a look on google scholar and results are a little inconclusive. I'm ...
- 151k
3
votes
1
answer
219
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 $u ...
- 638
1
vote
1
answer
608
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 ...
- 54.2k
-1
votes
1
answer
364
views
Basketball shots and stopping rule [closed]
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 ...
- 1,902
24
votes
1
answer
615
views
Permutations, stopping times, Bessel functions, hook formula and Robinson-Schensted
For given counting number $n$, consider all permutations $\pi$ of {$1,\ldots,n$}, generate for every $\pi$ its Robinson-Schensted pair of standard tableaux $(P_\pi,Q_\pi)$ and average together all the ...
- 15.8k
13
votes
4
answers
4k
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 ...
- 24.8k
3
votes
1
answer
333
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 ...
- 406
5
votes
2
answers
1k
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 ...
- 54.2k
1
vote
1
answer
269
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}.$
...
- 24.2k
0
votes
1
answer
227
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 ...
CommunityBot
- 1
7
votes
2
answers
3k
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 ...
- 656
2
votes
1
answer
305
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 ...
- 6,210
4
votes
0
answers
492
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 ...
- 903
5
votes
1
answer
224
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 $...
- 8,501
4
votes
1
answer
581
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 the ...
CommunityBot
- 1
2
votes
0
answers
83
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, ...
- 409
5
votes
1
answer
348
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 ...
CommunityBot
- 1
5
votes
3
answers
938
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 ...
- 456
1
vote
1
answer
918
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 L....
CommunityBot
- 1
8
votes
1
answer
227
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 ...
- 7,514
0
votes
1
answer
219
views
A square-squareroot integer race sequence involving primes
I wonder what is the expected behavior of this process?
Let
$f^2_{\mathrm{next}}(n) =$ the next prime after $n^2$.
$g_{\mathrm{sqrt}}(n) = \lfloor \sqrt{n} \rfloor$.
Now iterate as follows, ...
- 1,671
3
votes
1
answer
242
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 ...
- 24.8k
4
votes
2
answers
380
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 B}...
- 8,501
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
114
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 ...
- 4,589
2
votes
0
answers
186
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 ...
- 355
1
vote
0
answers
255
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 ...
CommunityBot
- 1
4
votes
0
answers
133
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 $\pi_{ij}...
- 4,952
0
votes
0
answers
257
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:
$$R\left(n,m,j\right)=\sum_{k=0}^{n}...
- 1
11
votes
2
answers
608
views
Covariance of INID order statistics [closed]
In the IID case, it is known that all order statistics are positively correlated.* Thus, we know that $$\text{Cov}(X_{(i)},X_{(j)}) \geq 0.$$ Is this known in the INID (independent, non-identically ...
CommunityBot
- 1
12
votes
1
answer
1k
views
Entropy of edit distance
The edit or Levenshtein distance between two strings is the minimum number of single character insertions, deletions and substitutions to transform one string into another. If we take random binary ...
- 24.8k
1
vote
1
answer
2k
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, $\...
- 965
4
votes
0
answers
1k
views
Matula-Goebel ordering of rooted trees intrinsic?
I was somewhat recently introduced to the Matula-Goebel bijection between rooted trees and natural numbers. (nicely illustrated here http://keithbriggs.info/matula.html) Looking through them, I ...
- 3,587
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 ...
CommunityBot
- 1
5
votes
1
answer
241
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) ...
CommunityBot
- 1
7
votes
1
answer
309
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 ...
- 1,299
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)$. ...
CommunityBot
- 1
0
votes
1
answer
221
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 $\...
- 28k
8
votes
2
answers
379
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 ...
- 43.7k
6
votes
0
answers
172
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 maps ...
- 15.5k
19
votes
1
answer
1k
views
Horst Knörrer's Permutation Cancellation Problem
The Problem:
The following question of Horst Knörrer is a sort of toy problem coming from mathematical physics.
Let $x_1, x_2, \dots, x_n$ and $y_1,y_2,\dots, y_n$ be two sets of real numbers.
We ...
CommunityBot
- 1
5
votes
2
answers
516
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 \...
- 696
3
votes
2
answers
946
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 ...
- 5,781
5
votes
1
answer
839
views
An optimization problem involving sum of binomial coefficients upto some value
I would like to minimize $f(s, n, \epsilon)$ with respect to $s$ where
$$f(s,n,\epsilon) = \left( 1 + \frac{n}{2^s} \right)\frac{1}{s} \sum_{k=0}^{\lfloor s\epsilon \rfloor} {s \choose k}~.$$
Note ...
- 362