All Questions
8 questions
1
vote
1
answer
197
views
Probability distribution on Python-dictionary-like objects?
I would like to examine information-theoretical properties of random variables that take as values objects which are akin to dictionaries in the Python programing language.
That is, each sample of the ...
- 11
1
vote
1
answer
195
views
Concentration of a certain simple / well-structured random multilinear polynomial with growing degree
Let $k$ and $N_1$ be positive integers and set $N=kN_1$. Partition $[N] := \{1,2,\ldots,N\}$ $k$ disjoint from $G_1,\ldots,G_k$ of each of size $N_1$, and let $\mathcal T(k,N_1)$ be a transversal of ...
- 6,853
6
votes
1
answer
527
views
Can information be extracted more precisely using more random trials?
Write $n$ iid draws of $(x,y)$ as $(x^n, y^n)$. Fix $R\in (0,H(x))$. What is the min of $n^{-1}H(y^n|f(x^n))$ over maps $f$ with range $\lbrace 1,\dots,\exp nR\}$, taking $n\to \infty$?
2
votes
1
answer
150
views
Probability of collision of some family of hash functions
Given $x$ and $y$ in $\mathbb{R}$, and let $\mathcal{H} = \{ h \mid \mathbb{R} \to \mathbb{N} \}$ be a family of hash functions where $ h(x) = \left\lfloor x + \sum^C_{i=1} U_i \right\rfloor$ for some ...
- 321
0
votes
0
answers
347
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, ...
- 1
27
votes
3
answers
2k
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 $$\operatorname{...
user32786
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
4
votes
6
answers
751
views
Reconstructing an ordering of a multiset from its consecutive submultisets
We have a multiset $S$ of size $t$ with $r$ distinct elements, where $t$ is much larger than $r$. We want to reconstruct an ordering $s_1, s_2, ... s_t$ of the elements of $S$ given the values of $t$ ...
- 599