All Questions
13 questions with no upvoted or accepted answers
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
9
votes
0
answers
1k
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 ...
- 201
8
votes
0
answers
181
views
Self-avoiding walks on strips
A strip is a locally finite graph which admits a quasi-transitive (i.e. finitley many orbits on vertices) action of $\mathbb Z$. A self avoiding walk is a walk which visits no vertex more than once.
...
- 2,671
7
votes
0
answers
171
views
What is known about the distribution of lengths of the cycle you get by adding an edge to a uniform spanning tree?
Let $G$ be a finite, connected graph. Let $T$ be a uniform spanning tree, and let $e$ be a uniformly random edge not in $T$. When we add $e$ to $T$, we get a subgraph with a unique cycle, $C$. I am ...
- 1,462
6
votes
0
answers
105
views
Long loops in critical random graphs
A simple calculation seems to show that the expected number $X_k$ of loops of length $k$ in a critical Erdös-Renyi random graph $G(n,n^{-1})$ is approximately given by
$$ \mathbb{E} X_k=\frac1{2k}{e^...
5
votes
0
answers
215
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)$.
...
- 667
5
votes
0
answers
227
views
Number of times lead changes in a multi-candidate election (reference-request)
In a two candidate election where votes are distributed uniformly at random between the candidates, the probability that the lead changes when tallying the $i$-th vote is the same as the probability ...
- 51
4
votes
0
answers
188
views
Distributions over permutation groups $\mathcal{S}_n$
Partly inspired by recent developments in enumeration of pattern avoiding permutations, which is known to be connected with Brownian excursions [Hoffman&Rizzolo]. The exciting milestone is the ...
- 8,071
3
votes
0
answers
303
views
Exchangeable or iid random variables and linear conditioning
Let $X_1,\ldots ,X_N$ be independent identically distributed random variables (or, more generally, exchangeable random variables,
but let's assume independence for simplicity). Then
$$
E(X_i\mid X_1+\...
- 1,765
2
votes
0
answers
91
views
Semigroups of nondecreasing functions
Consider some partially ordered set $(E,\leq)$. Assume either that it is countable with the discrete topology, or that it has some topology compatible with the order, preferably one that makes it into ...
1
vote
0
answers
91
views
Large deviation inequalities for number of coupon types collected by a coupon collector with fixed budget
In the generalized Coupon Collector's Problem, there are $N$ types of coupon, and for any $i \in [N] := \{1,2,\ldots,N\}$, $p_i \ge 0$ is the probability of obtaining a type-i coupon on any trial. ...
- 6,853
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 ...
- 5,409
0
votes
0
answers
55
views
Modeling player interactions in multi-dimensional rating systems
In traditional rating systems (such as Elo), a player's strength is represented by a single scalar value, which is assumed to be consistent across different opponents. However, in some games, the ...
- 1