Questions about the branch of mathematics concerned with modelling and analysing random phenomena.
3
votes
2answers
45 views
Randomized Algorithms Probability
I'm taking a grad level randomized algorithms course in the fall. The professor is known for being very detail oriented and mathematically rigorous, so I will be required to have an in-depth ...
1
vote
0answers
39 views
Conditional Probabilities as Tensors?
Is it proper to view conditional probabilities, such as the forms:
P(a|c)
P(a|c,d)
P(a, b|c, d)
...and so forth, as being tensors?
If so, does anyone know of a decent introductory text (online ...
0
votes
0answers
43 views
What is the purpose of Bayes Nets
I have seen a lot of explanations of what bayes nets are, but I simply cannot wrap my head around their use in code. So here is my three part question.
Am I right in my definition of bayes nets? ...
1
vote
1answer
51 views
What makes Bayesian Networks decomposable into joint trees?
Given a Bayesian Network $N$, one can build a junction/joint tree $JT$ over $N$ by applying series of steps (namely, moralisation,triangulation..etc). Then we can use $JT$ to answer queries over $N$.
...
0
votes
1answer
29 views
Compare two methods of random permutations
I want to compare in a practical sense two methods of random permutations -- one theoretically perfect, namely that of Fisher and Yates, and another ad hoc, let's
call it X. A way of comparison I ...
2
votes
1answer
79 views
How to distinguish whether a sample is from distribution $\chi_1$ or $\chi_2$?
I am given an oracle $A$ that takes input samples from two distributions $\chi_1$ and $\chi_2$.
Suppose we have $Pr_{x \sim \chi_1}[A(x) = 1] = p_1$ and $Pr_{x \sim \chi_2}[A(x) = 1] = p_2$, where ...
3
votes
1answer
25 views
Chazelle's discrepancy book: greedy method
In Bernard Chazelle's book The Discrepancy Method, which is available free as a PDF from the author's website, the very first statement requiring thought by the reader (on page 3, just before Theorem ...
1
vote
1answer
44 views
What does the posterior probability of a variable mean in the Bayes' rule?
I have been studying Artificial Intelligence and I have noticed that the Bayes' rule allows us to infer the posterior probability if a variable. But, my question is, what does the word, or phrase, ...
1
vote
1answer
45 views
Null Hypothesis in Analysis and Testing
I have my end of year exams next Thursday. I'm generally doing fine but I am having some major issues with this strand of my course, this has to be the biggest issue I have. So, here is the question ...
2
votes
1answer
39 views
The notion of density of distribution
I have difficulties in understanding the notion of density for distribution.
Notion of density for distribution. A distribution $H$ over $\{0,1\}^n$ has density $\sigma$ if for every $x \in ...
4
votes
1answer
54 views
Negligible Function in Cryptography
In the field of Cryptography and Computation Complexity there is a notion of negligible function.
I have some difficulties in understanding intuition behind this notion. The following are some ...
2
votes
0answers
22 views
Differences between Fuzzy C-Means and EM
When clustering a set of data points, what exactly are the differences between Fuzzy C-Means (aka Soft K-Means) and Expectation Maximization?
In slide 30 and 32 of this lecture I found, it says that ...
4
votes
1answer
46 views
Shannon Entropy to Min-Entropy
In many papers I've read that it is well known that the Shannon entropy of a random variable can be converted to min-entropy (up to small statistical distance) by taking independent copies of the ...
6
votes
1answer
239 views
Applying Expectation Maximization to coin toss examples
I've been self-studying the Expectation Maximization lately, and grabbed myself some simple examples in the process:
From here: There are three coins $c_0$, $c_1$ and $c_2$ with $p_0$, $p_1$ and ...
2
votes
1answer
47 views
Mutual information and moment generating functions
I went to listen to a workshop and someone from the audience asked the presenter how the moments can improve the mutual information. I am learning about MI (Mutual Information) so didn't have enough ...
3
votes
1answer
40 views
Pointwise mutual information vs. Mutual information?
I am learning about information theory and mutual information. However, I am quite confused with MI(Mutual information) vs. PMI(Pointwise mutual information) especially signs of MI and PMI values. ...
3
votes
3answers
60 views
Unbiasing of sequences
There is the well-known method of unbiasing of bit sequences due to von Neumann. Are there similar schemes applicable to other sequences, e.g. the result of throwing a normal die?
0
votes
1answer
38 views
Smoothing frequencies without count data
I have frequency data for different events under two conditions, resulting in sets of frequencies F1 and F2. I would like to normalize the frequencies of events under condition 1 by their frequencies ...
1
vote
3answers
84 views
Random graph model
When we say that in random graph we add an edge with a certain fixed probability, what do we actually mean?
For example if probability is 0.5, does that mean that we can just add two edges in a graph ...
8
votes
2answers
178 views
Discrepancy between heads and tails
Consider a sequence of $n$ flips of an unbiased coin. Let $H_i$ denote the absolute value of the excess of the number of heads over tails seen in the first $i$ flips. Define $H=\text{max}_i H_i$. Show ...
6
votes
1answer
125 views
Mental poker: proving dealt hand is fair
I have just read mental poker, described in this fascinating paper(PDF) by cryptographic greats Adi Shamir, Ron Rivest, and Leonard Adleman.
Assuming I have a website, (TTP) how can I prove to the ...
2
votes
2answers
45 views
Condition in Shamir Secret Sharing Scheme
For Shamir's secret sharing scheme (doi 10.1145/359168.359176), one obtains a random polynomial $q$ of degree at most $n-1$ (over $\mathbb{Z}_p[x]$). The constant coefficient of this polynomial is ...
0
votes
0answers
44 views
A few questions on Difference of Gaussians [closed]
I use this formula for Difference of Gaussians (DoG): $\frac{1}{\sigma}(\frac{x^2}{2\sigma^2}-1.0)e^{\frac{-x^2}{2\sigma^2}}$
What is the relationship between this formula and the difference of two ...
3
votes
0answers
68 views
Building probability distribution functions from observation
There are N players and M objects, each of the objects has a value. Each player has a strategy in choosing an object. Each round a player will choose an object, many players can choose the same ...
3
votes
1answer
127 views
How many random walks to start from each node?
Assume that we are given a real life graph, DBLP network in my case, where degree distribution of nodes follows a power law (many nodes have 1, 2 neighbors, and only a few nodes have hundreds of ...
2
votes
1answer
64 views
probability wheel, redistribution of probabilities
I have a contiguous ordered data structure (0 based index):
x= [1/3, 1/3, 1/3]
Let's say I selected index 1 and increased the probability by 1/3. Rest of the ...
0
votes
0answers
75 views
How to calculate the blocking probability of processes with gamma-distributed service times using the Erlang formula?
I have seen numerous examples of using the Erlang formula to calculate the blocking probability for processes with exponentially distributed service times. However, I am not quite sure how to do that ...
21
votes
2answers
263 views
How asymptotically bad is naive shuffling?
It's well-known that this 'naive' algorithm for shuffling an array by swapping each item with another randomly-chosen one doesn't work correctly:
...
3
votes
2answers
117 views
Construction of binary random variable
We throw two coins in a row and thus get the event space $\{ZZ, WW, ZW, WZ\}$.
Each of the 4 elementary events has a probability $1/4$.
how can I construct 3 binary random variable $x_1$, $x_2$, ...
5
votes
1answer
60 views
Maximal derangements
When one shuffles playing cards, the goal is evidently to achieve a possibly big derangement
of a given deck. For manual shuffling there are terms like inshuffle, outshuffle etc. I like
to know ...
2
votes
1answer
423 views
Average number of comparisons to locate item in BST
This is a GRE practice question.
If a node in the binary search tree above is to be located by binary tree search, what is the expected number of comparisons required to locate one of the items ...
1
vote
1answer
143 views
Hiring one person out of n — rank and probablity
I am studying algorithms from CLRS book. I try to understand the difference between
probability of hiring the $i$th person out of $n$ and
probability of hiring the $i$th person out of $n$ persons ...
0
votes
3answers
24 views
Heuristically determine a value f such that a probability d/f approaches 1/2
We have a set X of N elements. We want to get a new set X' having a size M < N.
...
6
votes
1answer
315 views
Smoothing in Naive Bayes model
A Naive Bayes predictor makes its predictions using this formula:
$$P(Y=y|X=x) = \alpha P(Y=y)\prod_i P(X_i=x_i|Y=y)$$
where $\alpha$ is a normalizing factor. This requires estimating the parameters ...
2
votes
1answer
192 views
Determining Probability from a Graph
Lets say I have node A that connects to 10 other nodes. 6 of those nodes have Property 1 and the other 4 have Property 2. How can I easily determining the probability of landing on a node with ...
0
votes
1answer
126 views
Time series probability and mutual information
There is a time series of say $100$ data points. I wish to assign symbols of $0, 1, 2$ for each unique data point. The issue is I have tried but got stuck since no matter I specify the symbols, the ...
3
votes
1answer
129 views
How to random-generate a graph with Pareto-Lognormal degree nodes?
I have read that the degree of nodes in a "knowledge" graph of people roughly follows a power law distribution, and more exactly can be approximated with a Pareto-Lognormal distribution.
Where can I ...
12
votes
3answers
239 views
Is rejection sampling the only way to get a truly uniform distribution of random numbers?
Suppose that we have a random generator that outputs
numbers in the range $[0..R-1]$ with uniform distribution and we
need to generate random numbers in the range $[0..N-1]$
with uniform distribution.
...
3
votes
1answer
95 views
Does there exist any work on creating a Real Number/Probability Theory Framework in COQ?
COQ is an interactive theorem prover that uses the calculus of inductive constructions, i.e. it relies heavily on inductive types. Using those, discrete structures like natural numbers, rational ...
4
votes
1answer
74 views
Probabilities of duplicate mail detection by comparing notes among servers
I have the following problem:
We want to implement a filtering strategy in e-mail servers to reduce the number of spam messages. Each server will have a buffer, and before sending an e-mail, it ...
11
votes
1answer
380 views
How to prove correctness of a shuffle algorithm?
I have two ways of producing a list of items in a random order and would like to determine if they are equally fair (unbiased).
The first method I use is to construct the entire list of elements and ...
9
votes
1answer
156 views
Number of clique in random graphs
There is a family of random graphs $G(n, p)$ with $n$ nodes (due to Gilbert). Each possible edge is independently inserted into $G(n, p)$ with probability $p$. Let $X_k$ be the number of cliques of ...
4
votes
1answer
116 views
Online generation of uniform samples
A source provides a stream of items $x_1, x_2,\dots$ . At each step $n$ we want to save a random sample $S_n \subseteq \{ (x_i, i)|1 \le i \le n\}$ of size $k$, i.e. $S_n$ should be a uniformly chosen ...
2
votes
1answer
144 views
Deterministic and randomized communication complexity of set equality
Two processors $A, B$ with inputs $a \in \{0, 1\}^n$ (for $A$) and $b \in \{0, 1\}^n$
(for $B$) want to decide whether $a = b$. $A$ does not know $B$’s input and vice versa.
A can send a message ...
3
votes
1answer
78 views
Making random sources uniformly distributed
How do I build a random source that outputs the bits 0 and 1 with $prob(0) = prob(1) = 0.5$. We have access to another random source $S$ that outputs $a$ or $b$ with independent probabilities ...
5
votes
2answers
143 views
Extracting non-duplicate cells in a particular matrix with repeated entries
Consider a board of $n$ x $n$ cells, where $n = 2k, k≥2$. Each of the numbers from $S = \left\{1,...,\frac{n^2}{2}\right\}$ is written to two cells so that each cell contains exactly one number.
How ...
6
votes
1answer
108 views
Prove fingerprinting
Let $a \neq b$ be two integers from the interval $[1, 2^n].$ Let $p$ be a random prime with $ 1 \le p \le n^c.$ Prove that
$$\text{Pr}_{p \in \mathsf{Primes}}\{a \equiv b \pmod{p}\} \le c ...
16
votes
1answer
206 views
Algorithm to chase a moving target
Suppose that we have a black-box $f$ which we can query and reset. When we reset $f$, the state $f_S$ of $f$ is set to an element chosen uniformly at random from the set $$\{0, 1, ..., n - 1\}$$ where ...
7
votes
1answer
530 views
Randomized Selection
The randomized selection algorithm is the following:
Input: An array $A$ of $n$ (distinct, for simplicity) numbers and a number $k\in [n]$
Output: The the "rank $k$ element" of $A$ (i.e., the one in ...
13
votes
2answers
168 views
How does variance in task completion time affect makespan?
Let's say that we have a large collection of tasks $\tau_1, \tau_2, ..., \tau_n$ and a collection of identical (in terms of performance) processors $\rho_1, \rho_2, ..., \rho_m$ which operate ...
