All Questions
Tagged with computer-science pr.probability
36 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 ...
CommunityBot
- 1
1
vote
1
answer
284
views
Rate of convergence to uniform distribution
Let $p=(p(1),\ldots,p(N))$ be a discrete distribution on $[N]:=\{1,2,\ldots,N\}$ with full support (i.e all the $p(i)$'s are strictly positive and sum to $1$). Let $i_1,i_2,\ldots,i_T$ be an iid ...
CommunityBot
- 1
5
votes
1
answer
2k
views
Mathematics research relating to machine learning
What branch/branches of math are most relevant in enhancing machine learning (mostly in terms of practical use as opposed to theoretical/possible use)? Specifically, I want to know about math research ...
- 30.3k
1
vote
0
answers
62
views
A small lemma on cache resets (Bloom filters in particular)
Assume a fixed set of message $D$ and an associated distribution for selecting each message $d_i$ such that the total probability $\sum_{i \in D} d_i = 1$. We create a cache with $M$ bits and $k$ ...
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 ...
- 63.9k
4
votes
2
answers
308
views
Concentration of minimum Hamming distance between $N$ points sampled iid from uniform distribution on $n$-dim hypercube $\{0,1\}^n$
Let $n$ be a large positive integer. Sample $N \ge 2$ points $x_1,\ldots,x_N$ iid from the uniform distribution on the $n$-dimensional hypercube $\{0,1\}^n$. Define the gap $\delta_{N,n} := \min_{i \...
- 10.4k
1
vote
0
answers
83
views
Convex optimization with one-point feedback
In an adversarial bandit setting, we want to minimize $\sum_{1}^{T}l_t$(not exactly this but the corresponding regret), where $l_t$ is the loss function in the $t-$th round. Each round we can specify ...
- 21
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$?
- 716
2
votes
1
answer
179
views
Union of admissible words are subshift of finite type
Assume that $Q=(q_{ij})$ is a $k\times k$ with $q_{ij}\in \{0, 1\}.$ The two side subshift of finite type associated to the matrix $Q$ is a left shift map $T:\Sigma_{Q}\rightarrow \Sigma_{Q}$, where
...
- 6,652
3
votes
1
answer
355
views
Is there a complete countable axiomatization of conditional independence? (Graphoids)
Note: A pointer to a reference, or a yes/no answer with a 1-2 sentence incomplete/non-rigorous justification would suffice for answers. I am just curious about whether the result is true; it is fairly ...
- 136
2
votes
1
answer
176
views
Monotonicity of Dirichlet form of Markov chain
Consider a continuous-time, irreducible Markov chain $X_t$ on a finite state space $E$. Assume the jump rates are $R(x,y)$ for $x,y\in E$, the generator is $L$, i.e for any function $f$ on E,
$$Lf(x)=\...
- 695
6
votes
1
answer
434
views
Probability of complex eigenvalues
I find this is the best site to post this question, even though I considered cs.
It is a Monte Carlo experiment over the set of 10.000 n×n matrices.
If a single matrix eigenvalue is complex then ...
- 2,552
3
votes
0
answers
95
views
Empirically random, quickly multiplicable matrices
I have encountered a need for fast computation of a transformation $Ax$ where $A\in \mathbb{C}^{K\times N},\ K\sim 10^7,\ N\sim 10^3$ is designed, and $x\in \mathbb{C}^N$ has iid $\mathcal{CN}(0,1)$ ...
2
votes
1
answer
152
views
Computationally random bitstreams and normalcy
Let $\mathbb{N}$ denote the set of non-negative integers. We can identify every bitstream, i.e. a function $s:\mathbb{N}\to \{0,1\}$, with some $A\in{\cal P}(\mathbb{N})$: take $A = s^{-1}(\{1\})$.
...
- 54.2k
19
votes
3
answers
1k
views
Which distributions can you sample if you can sample a Gaussian?
Explicitly: You have a computer that is able to pick a real number at random according to the normal distribution: $\mathcal{N}(0,1) = \frac{1}{\sqrt{2\pi}}e^{-x^2/2}$. Which distributions can this ...
- 6,045
2
votes
0
answers
99
views
Recovering a rank-one matrix from its eigendecomposition after randomized rounding [closed]
Let $A = xy^T$ be a rank-$1$ matrix, and suppose every entry of $A$ is in $[0,1]$. We can create a binary matrix $A_{\rm rounded}$ by setting
$$ [A_{\rm rounded}]_{ij} = \begin{cases} 1 & \mbox{ ...
- 121
13
votes
2
answers
3k
views
Who first chose the names Alice and Bob for players A and B? [closed]
Who first chose the names Alice and Bob for the players (or observers) A and B?
CommunityBot
- 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{...
1
vote
1
answer
90
views
Probability of collision of sums of vectors multiplied by random matrix
Let $S$ and $T$ be sets of vectors from $\mathbb{R}^d$ such that $S$ and $T$ are at least different in one element.
Does there exist a random matrix $M \in \mathbb{R}^{d \times k}$, e.g., a gaussian ...
- 10.4k
15
votes
8
answers
3k
views
How Does Random Noise Typically Look?
How does random noise in the digital world typically look?
Suppose you have a memory of n bits, and suppose that a "random noise" hits the memory in such a way that the probability of each bit being ...
- 1,228
10
votes
2
answers
611
views
When can a freely moving sphere escape from a 'cage' defined by a set of impassible coordinates?
To ask this question in a (hopefully) more direct way:
Please imagine that I take a freely moving ball in 3-space and create a 'cage' around it by defining a set of impassible coordinates, $S_c$ (i.e....
- 13.6k
18
votes
3
answers
2k
views
How do we express measurable spaces using type theory?
A measurable space $(X,\mathcal X)$ consists of a set $X$ equipped with a $\sigma$-algebra of subsets $\mathcal X$. I would like to write computer programs involving measurable spaces, but to the best ...
CommunityBot
- 1
1
vote
1
answer
187
views
Random iteration of a set of monotone maps until fixed point
Let $P$ be a poset with a least element $\bot$ ($\forall x \in P.\ \bot \le x$).
Let $M$ be a set of monotone maps $P \to P$.
Call $x \in P$ reachable if $x = f_1(f_2(...f_n(\bot)...))$ for some ...
- 36
4
votes
5
answers
2k
views
Does an "efficient" random number generator exist?
Given some number $n$ and a seed number $s$<$n$, I want a random number generator (RNG) that will go through all integers `<$n$ before coming back to $s$. The resulting random number must be ...
1
vote
2
answers
345
views
Coding SLEs (Schramm–Loewner Evolution) eg. SLE(6)
Any references/links on codes for SLEs written in C++ or Matlab that I can run in Windows (visual studio)?
The only code I found was:http://math.arizona.edu/~tgk/research.html but the link was empty. ...
- 1,791
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 ...
- 128k
7
votes
0
answers
245
views
Distribution of trivial subset sums
Suppose I have a set $S$ of $n$ integers picked independently, uniformly at random from $[-L, L].$ Let $z(S)$ be the number of subsets of $S$ which sum to zero. The question is: what is the ...
- 96.4k
1
vote
0
answers
179
views
Is there an efficient algorithm for sampling from the negative hypergeometric distribution? [closed]
I'm writing a small statistics library currently. One of the algorithms I'm implementing has two variants: one that samples the hypergeometric distribution and one that samples the negative ...
- 6,210
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
8
votes
0
answers
1k
views
Question on randomness extractors
Person A has a source $W$ with min-entropy($W$) = $k$. He also has an extra piece of information about the random source, denoted with $y$, such that min-entropy($W|y$) = $k/3$.
The adversary doesn't ...
- 5,502
1
vote
0
answers
135
views
Optimizing for a unique outcome of a probabilistic marriage problem
Let's say I have some number of individuals who are single, $(b_1, ..., b_N) \in B$, and for every possible pairing of two individuals, $b_i$ and $b_j$, I happen to know the exact probability that the ...
- 11
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):
...
- 73.2k
3
votes
2
answers
255
views
Correcting bias in samples selected by a prediction
Here is the scenario:
I'm trying to find as many golden tickets as I can, so that I can sell them to kids that want to go on a tour of Wonka's chocolate factory.
Fortunately, I have a machine that ...
- 28k
4
votes
2
answers
2k
views
finding numbers at k hamming distance
Guys,
I have N < 2^n randomly generated n-bit numbers stored in a file the lookup for which is expensive. Given a number Y, I have to search for a number in the file that is at most k hamming dist....
- 4,462
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$ ...
CommunityBot
- 1
5
votes
3
answers
4k
views
Counting lattice points on an n-simplex
Imagine an n-simplex, the solution set for the expression: $a_1$*$x_1$ + $a_2$*$x_2$ + ... + $a_n$*$x_n$ = S, where:
$a_1$ through $a_n$ are positive bounded integers
$x_1$ through $x_n$ are ...
- 43