All Questions
Tagged with pr.probability co.combinatorics
802 questions
15
votes
2
answers
547
views
Random graphs in $\mathbb R^2$ (or random rays from $\mathbb Z^2$)
The model:
Suppose that for each lattice point in $\mathbb Z^2$ we pick a random direction uniformly and independently. At time $t=0$ we start drawing rays starting from each lattice point in the ...
- 85.6k
3
votes
3
answers
3k
views
Expected Number of Bernoulli trials before you get N more heads than tails
Hello,
I'd like to find the expected number of Bernoulli trials that I'll need before I will get exactly n more heads than tails, given a coin which gets a heads with probability p.
My approach ...
23
votes
3
answers
2k
views
Zeroes of the random Fibonacci sequence
Let $X_n$ be the "random Fibonacci sequence," defined as follows:
$X_0 = 0, X_1 = 1$;
$X_n = \pm X_{n-1} \pm X_{n-2}$, where the signs are chosen by independent 50/50 coinflips.
It is known ...
- 19.2k
2
votes
4
answers
512
views
Statistical computation in matrix. Rows before columns? riddle..
First I'll phrase the question as a riddle, and than as a general math problem.
We have 12 lettered vases $(A,B,...,L)$, in each vase there are 30 numbered balls (1-30). In each ball there is some ...
- 23
21
votes
1
answer
32k
views
How to compute KL-divergence when PMF contains 0s?
From the Wikipedia page on Kullback-Leibler divergence, the way to compute this metric is to utilize the following formula:
The way I understand this is to compute the PMFs of two given sample sets ...
- 439
18
votes
2
answers
1k
views
In an Erdős–Rényi random graph, what is the threshold for the property "every edge is contained in at least one triangle"?
Let $G(n,p)$ denote the Erdős–Rényi random graph, where $n$ is the number of nodes and $p$ is the probability for each edge. I'm interested in precisely what range of $p$ the random graph has at least ...
- 7,857
1
vote
1
answer
230
views
Combinatorics for a stochastic dynamics problem
Suppose we have a circular arrangement (periodic boundaries) with $M$ sites and we want to distribute $N$ particles over these sites such that there are occupation numbers $n_m$ that respect $\sum_m ...
- 91
1
vote
3
answers
501
views
Operator probability in a RPN string
Consider the set $S_n$ of all strings of length $n$ ($n$ integer, $n \geq 3$)
representing an expression in RPN
( http://en.wikipedia.org/wiki/Reverse_Polish_notation. )
Assumptions (to simplify):
...
- 31
11
votes
1
answer
919
views
Average over Random Permutations
Consider $S_{n}$ the symmetric group and for each $\sigma\in S_{n}$ let $U_{\sigma}$ be its $n\times n$ permutation matrix. Let $A$ be an Hermitian $n\times n$ matrix. I'm interested in computing the ...
- 3,626
13
votes
1
answer
2k
views
Counting subtrees of a random tree ("random Catalan numbers")
Given a rooted tree $T$ and an integer $k \geq 1$, let $N_k(T)$ be the number
of subtrees of $T$ containing the root and having exactly $k$ nodes (take $N_k(T)=0$ if $T$ has less than $k$ nodes).
...
- 4,922
8
votes
4
answers
1k
views
A Pascal's-triangle -like random process
I was exploring Pascal's triangle on a cylinder when I encountered this puzzle-like problem.
It is surely elementary, but perhaps weekend-entertaining.
Start with a permutation of $(1,2,3, \ldots, n)$...
- 151k
1
vote
1
answer
1k
views
Average Hamming distance between strings after some number of random substitutions in a population of initially identical elements
Let's say I have a set $S$, $(s_1, ..., s_i, ..., s_P) \in S$, of $P$ identical strings over a $k$-letter alphabet, each of length $|s_i| = L$. With uniform random probability across all strings in $...
- 309
21
votes
3
answers
2k
views
what is the cycle length of the maximum normalized cycle in the directed complete graph?
Consider the complete, directed graph on $n$ vertices. Let the edge lengths $\{X_{ij}: 1 \leq i, j \leq n\}$ be i.i.d standard normal, with the constraint $X_{ij} = -X_{ji}$. The value of a normalized ...
- 1,010
3
votes
2
answers
421
views
Sufficiently random sample
Let $d$ be an integer $\geq 2$, and let $\Omega = \lbrace 0,1 \rbrace^d$, $A \subseteq \lbrace 0,1 \rbrace^2 $ and $i,j$ integers with $1 \leq i < j \leq d$. If we select an element $(x_1,x_2, \...
- 3,595
7
votes
2
answers
417
views
Dynamics of a random "quadratic" directed graph
Let G be a directed graph on N vertices chosen at random, conditional on the requirement that the out-degree of each vertex is 1 and the in-degree of each vertex is either 0 or 2. The "periodic" ...
- 19.2k
27
votes
5
answers
7k
views
Probability of a Random Walk crossing a straight line
Let $(S_n)_{n=1}^{\infty}$ be a standard random walk with $S_n = \sum_{i=1}^n X_i$ and $\mathbb{P}(X_i = \pm 1) = \frac{1}{2}$. Let $\alpha \in \mathbb{R}$ be some constant. I would like to know the ...
- 733
5
votes
1
answer
688
views
Probability of having a bounded ratio of two types of balls in each of 'S' bins after random partitioning of a fixed number of balls
Let's say I have a bag with $A$ red balls, $B$ blue balls, and a total number of balls $N = A + B$. With uniform probability, and sampling without replacement from the $N$ balls, I fill an integer ...
1
vote
2
answers
242
views
Number of required trials to sample all possible states of a 'd'-sided loaded die
Let's say that I have a loaded $d$-sided die where the relative probabilities for the die landing on a particular side, $(p_1, ..., p_d)$, are known. How many times must I roll the die to, on average,...
- 309
11
votes
3
answers
2k
views
Probability of unique elements in each of 'S' multisets sampled with uniform probability
Assume I have some set $P$ with $||P|| = N$ unique elements. I also have $S$ multisets, $(m_1, ..., m_S)$, of cardinality $L$, consisting of elements in $P$ chosen with uniform probability. We call ...
57
votes
4
answers
15k
views
Connectivity of the Erdős–Rényi random graph
It is well-known that if $\omega=\omega(n)$ is any function such that $\omega \to \infty$ as $n \to \infty$, and if $p \ge (\log{n}+\omega) / n$ then the Erdős–Rényi random graph $G(n,p)$ is ...
- 7,857
10
votes
0
answers
779
views
Faa di Bruno and Free Probability?
It is possible to glean many combinatorial identities using Faa di Bruno’s formula for the coefficients of higher derivatives of a composite function. For many examples, see David Vella’s paper. The ...
- 7,067
4
votes
3
answers
439
views
Probability estimates for "beans & boxes"
From a discussion with some friends, this apparently easy problem has come out; I decided to post it here, because I believe that the answer is non-trivial and the maths beneath interesting. Partial ...
- 418
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 ...
- 24.7k
7
votes
2
answers
2k
views
Assigning positive edge weights to a graph so that the weight incident to each vertex is 1.
Let $\Gamma=(G,E)$ be a connected undirected graph, with no loops or multiple edges. $G$ is finite or countably infinite. For each edge $e=\{x,y\}\in E$, we assign a positive, symmetric edge weight $...
- 269
0
votes
1
answer
292
views
Probability of preserving connectivity between pair of vertices in weighted graph
Let $G=(V,E)$ be an undirected graph and $p \colon E \mapsto (0,1]$ defines weights of its edges.
Let's fix two connected vertices $v_1, v_2 \in V$.
Random graph $G'=(V,E')$ is obtained from $G$ by ...
- 3
5
votes
1
answer
2k
views
Random points in a rectangular grid defining a closed path
Suppose we have a $n\times m$ rectangular grid (namely: $nm$ points disposed as a matrix with $n$ rows and $m$ columns).
We randomly pick $h$ different points in the grid, where every point is ...
- 51
5
votes
1
answer
394
views
Product of coordinates of a random point from Hamming sphere
Let us consider a boolean hypercube $C = \{-1, 1\}^n$. Let $S = \{x \in C \mid |\{i \mid x_i = -1\}| = \varepsilon n\}$ be a Hamming sphere in $C$ (here $\varepsilon$ stands for the fixed parameter ...
- 1,791
9
votes
1
answer
695
views
Probability of return vs. probability of return in minimal number of steps
Consider a random walk on a connected graph $G=(V,E)$. That is, associate to each neighbouring nodes $a,b\in V\ $ transition probabilities $\mathbb{P}(a\rightarrow b), \mathbb{P}(b\rightarrow a) $ ...
- 965
3
votes
1
answer
1k
views
Cumulative distribution function of hypergeometric distribution
Does anyone know a closed form or a good approximation of the cumulative distribution function of hypergeometric distribution?
- 177
24
votes
1
answer
2k
views
A puzzle about finding three points $(x,y)$, $(x,z)$ and $(y,z)$ in a subset of a square.
I was asked (by myself) to give a proof of the following seemingly simple geometric statement, but after thinking a little I now suspect it could be less elementary than I thought (or am I being silly?...
- 60.5k
6
votes
2
answers
729
views
Has the following kind of (minimum degree $d$) random graph been studied?
The following random construction is simple enough that I am guessing it must have been studied. Fix $d \ge 3$, and let $n > d$. For each of the $n$ vertices, pick exactly $d$ other vertices to ...
- 7,857
9
votes
1
answer
860
views
Random walk on a simple finite network
Consider a graph $\Delta_N = \lgroup (x,y)\in\mathbb{Z}^2| x+y\leq N-1, x\geq 0,\ y\geq 0 \rgroup$ (set of edges is defined in a natural way): see here ).
Take a random walker that wonders around ...
- 965
6
votes
4
answers
452
views
Counting card distributions when cards are duplicated
If we have a deck of $48$ different cards and $4$ players each get $12$ cards, it is well known how to calculate the number of possible distributions: $\frac{48!}{12!12!12!12!}$
In a german card came (...
11
votes
5
answers
2k
views
Coin flipping and a recurrence relation
How can one solve the following recurrence relation?
$f(n) = 1 + \frac{1}{2^n} \sum_{k = 0}^n {{n}\choose{k}} f(k)$
$f(0) = 0$
As it happens, I can show $f(n) = \Theta(\log n)$ through other means (...
- 501
4
votes
2
answers
1k
views
Balls-and-bins type problem
Suppose I have an n-by-n array of bins, and I want to choose k (k >= n) bins from these n^2 bins such that each row of the array has at least one bin chosen. How many ways are there of doing this?
...
- 57
23
votes
2
answers
910
views
Random permutations of Z_n
In "The maximum number of Hamiltonian paths in tournaments" by Noga Alon, the author states the following without proof (equation 3.1):
"Consider a random permutation $\pi$ of $\mathbb{...
- 375
4
votes
1
answer
2k
views
Square of Binomial Coefficient
Background
I'm modeling Genetic Algorithm(GA) with Markov chains and deriving the expression for the expectation of the first hittig time in the MC with 1 absorbing state and $l-1$ transient states. ...
- 345
5
votes
1
answer
1k
views
Self Avoiding Walk Enumerations
Let $c(n)$ be the number of Self avoiding walks (SAW) of length $n$ on an infinite lattice $L$. Are there any known non-geometric interpretations of $c(n)$?. For example, is there a number theoretic ...
- 4,952
15
votes
1
answer
1k
views
Has the technique of "sprinkling" been used in studying random matrices?
In 1982, while studying the component sizes of random subgraphs of a hypercube, Ajtai, Komlós, and Szemerédi introduced a technique that came to be known as sprinkling. In this technique, the edges of ...
- 4,922
6
votes
2
answers
615
views
Optimally directing switches for a random walk
If you are sometimes called upon directing a random walk in a directed graph, how should you direct it so as to maximize the probability it goes where you want?
Formal statement
More specifically, ...
- 4,994
4
votes
0
answers
580
views
Monotonic properties of harmonic functions on graphs
I have a question concerning monotonic properties of "generalized harmonic functions" on graphs. I am a physicist and I didn't take any separate courses in neither graph theory nor discrete harmonic ...
- 965
9
votes
1
answer
1k
views
A Game of Knights and Queens
Let $m,n,u,v \in \mathbb{N}$ be parameters with $m,n \geq 3$. Suppose two players play a game on a $m \times n$ chess board and we denote the squares of the board by the set of points $ (i,j) $ such ...
- 26.9k
11
votes
2
answers
880
views
Covering a random graph with spanning trees.
Let $G=(V,E)$ be a connected graph, say $V=\{1,\ldots,n\}$. Let $F=(V,E')$ be a uniformly random forest in $G$. (In other words, $E'$ is a subset of edges $E$ not containing a cycle, and it is ...
- 4,922
0
votes
0
answers
319
views
Estimating a multinomial sum
I have the following sum
\begin{equation}
\sum_{r_1=q+1}^{\tau}\dots\sum_{r_\lambda=q+1}^{\tau}{\tau\choose r_1,\dots,r_\lambda,\tau-r_1-\dots -r_\lambda} (\Lambda-\lambda)^{\tau-r_1-\dots-r_\lambda}
\...
10
votes
2
answers
602
views
What is the probability that every pair of students is at some point in the same classroom?
A cohort in a school consists of 75 students who study for 6 years. Each year, the students are randomly distributed into 3 classrooms of 25 students each. What is the probability that, after 6 years, ...
- 226
2
votes
2
answers
391
views
linear ordering of color balls
Suppose that $n+m$ balls of which $n$ are red and $m$ are blue, are arranged in a linear order, we know there are $(n+m)!$ possible orderings. If all red balls are alike and all blue ball are alike, ...
- 123
21
votes
7
answers
14k
views
A balls-and-colours problem
A box contains n balls coloured 1 to n. Each time you pick two balls from the bin - the first ball and the second ball, both uniformly at random and you paint the second ball with the colour of the ...
- 1,269
3
votes
3
answers
942
views
implementations of domino shuffling algorithm
Are there many implementations of the "domino shuffling" algorithm as found in William Jockusch, James Propp amd Peter Shor's Random Domino Tilings and the Arctic Circle Theorem math.CO/...
- 22.8k
21
votes
11
answers
4k
views
What are some good examples of non-monotone graph properties?
It seems that many, if not almost all, of the properties studied in graph theory are monotone. (Property means it is invariant under permutation of vertices, and monotone means that the property is ...
- 7,857
3
votes
7
answers
4k
views
How to tell if two random polynomials are identical
Let t be a positive real number. Let P(x) and Q(x) be two random polynomials with integer coefficients. If P(t) = Q(t), then what is the probability that P(x) is not identical to Q(x)?
Will it make a ...
- 179