Questions about the branch of mathematics concerned with modelling and analysing random phenomena.

learn more… | top users | synonyms

1
vote
0answers
16 views

What is linear relaxation in the context of bayesian networks?

To add onto the question, how are elliptical differential equations applicable in this context? I was listening to a talk about Bayesian networks and someone asked if they were using differential ...
-3
votes
2answers
45 views

Perceptron learning rule for classification

That's the problem $$y=(x,w,\rho) = \begin{cases} 1 & \sum_{i=1}^3 w_ix_i >\rho\\ 0 & \text{otherwise} \end{cases},$$ where $x=\{x_1,x_2,x_3\}$ are inputs, $w=\{w_1,w_2,w_3\}$ are ...
1
vote
1answer
44 views

Min-entropy of a random pre-image of a random function

I am facing hard time understanding min-entropy. Fix $v \in \{0,1\}^{n/2}$, let $F\colon \{0,1\}^n \to \{0,1\}^{n/2}$ be chosen randomly, and let $X_v$ be a string chosen uniformly at random among ...
-1
votes
0answers
20 views

Minimal I-maps induced by sets of scopes. Clarification needed [closed]

I've asked this question on cross validated and got no answer. Maybe it's more of a computer science question. Here it goes: I have a question about Prop. 9.1 on page 307 in "Probabilistic Graphical ...
4
votes
1answer
358 views

Is this method really uniformly random?

I have a list and want to select a random item from the list. An algorithm which is said to be random: When you see the first item in the list, you set it as the selected item. When you see ...
2
votes
2answers
73 views

Soft Margin Loss and Conditional Probabilities

Consider the following soft margin loss function: $\max(0, 1-yf(x))$. I have the problem of needing to compute the conditional probability $p(y|x)$ corresponding to this function and am having ...
5
votes
1answer
69 views

Possible to construct a probabilistic halting problem solver?

I'm a CS undergrad so my math/CS knowledge is not that deep so please correct me if my premise is flawed or I have made some incorrect assumptions. So I was thinking, much in the way that some ...
0
votes
1answer
47 views

In Probabilistic Graphical Models, are Cliques and Clusters the same?

I am learning Probabilistic Graphical Models with the help of the videos on Coursera. I am in week 4 and I see cliques being mentioned often. But the graphs being discussed are cluster graphs. So are ...
1
vote
1answer
32 views

Interpreting probabilistic time turning machines

I was trying to understand better the definition of a strong PSRG and I came across this expression which I am trying to understand better: $$ Pr_{r \in \{0,1\}^l}[A(r) = \text{"yes"}]$$ Where r is ...
2
votes
0answers
26 views

Adversarial bin packing

An adversary gives you a set of items whose total size is $x$ (he gets to choose how $x$ is distributed. e.g. there may be $k-1$ items of size $\frac{x}{k}$ and 2 items of size $\frac{x}{2k}$). The ...
0
votes
1answer
67 views

Naive Bayes Intuition

I have some difficulties in understanding the intuition behind Naive Bayes Classification. In general, I do understand every argument of the definition, however I don't understand why it's correct ...
-2
votes
2answers
89 views

help with the probability of acceptance of a Nondeterministic Pushdown automata

I have this nondeterministic pda: $$\Sigma= \{a,b,c\}$$ and $$ L=\{\omega\ \epsilon\ \Sigma^*\ |\ \omega\ = \alpha\beta\beta^R\gamma\ and\ \alpha,\beta,\gamma\ \epsilon\ \Sigma^*\ and\ |\beta|\ ...
-2
votes
1answer
58 views

proof of convergence in arbitrary precision PRNGs

consider a program that generates a random walk using a PRNG, as in following pseudocode. it uses arbitrary precision arithmetic such that there is no limit on variable values (ie no overflow). ...
-3
votes
2answers
82 views

Measuring uniformity of CRC32 by using birthday problem

I would like to measure what is the probability that given some data and it's CRC32 checksum there is some other data with the same checksum. Running the simulation is not feasible because of the 2^32 ...
7
votes
1answer
129 views

Estimating the time until we obtain five-in-a-row?

Consider the following random process. We have a $10\times 10$ grid. At each time step, we pick a random empty grid cell (selected uniformly at random from among all empty cells) and place a marker ...
0
votes
1answer
57 views

Post-selection and complexity theory [closed]

I read about post-selection and didn't understand the meaning behind this thing. I didn't understand the Wikipedia article well, so what is a simple but understandable explanation of post-selection ...
2
votes
0answers
61 views

Which component sizes do we observe while randomly deconstructing a tree?

Suppose I have a connected graph with $n$ vertices and $n−1$ edges, that is in form of a tree. Now, I will add the number of vertices in the tree and uniformly randomly select a vertex. I break the ...
3
votes
2answers
112 views

Probability that a uniformly random sequence is already sorted

Now I tried tackling this question from different perspectives (and already asked a couple of questions here and there), but perhaps only now can I formulate it well and ask you (since I have no good ...
2
votes
1answer
55 views

Sort algorithm input probabilities

Suppose that there is an algorithm which sorts a sequence of $n$ elements $$a_1, a_2, ..., a_n$$ Each of the $a_i$ is chosen with probability $1/k$ from a set of $k$ distinct integer numbers. Is ...
0
votes
2answers
73 views

Bayesian Network - Inference

I have the following Bayesian Network and need help with answering the following query. EDITED: Here are my solutions to questions a and b: a) ...
-1
votes
1answer
163 views

Little's law and average time on a system with a switch

We have a switch with $2$ lines of input and $2$ output. Each line is $10 Mbps$. The size of packets is fixed and is $1KB$. The $1^{st}$ line of input is active (transferring packets) $40\%$ of the ...
4
votes
2answers
195 views

Recommended readings for Probability theory applied to algorithms

Currently, I'm delving into Analysis of Algorithms and I've discovered that I would need to improve my knowledge of Probability Theory. Any recommendation? Where do I start? Thanks in advance!
2
votes
2answers
112 views

Measures and probability in formal language theory

I am looking for references for the following problem: I have a very special class of regular languages and my aim is to express (and to justify my conjecture) that this class itself is very small in ...
1
vote
1answer
319 views

Average number of slots needed in slotted-Aloha

Consider 2 stations that share the same bus. Both stations are perfect synchronized each other and when they have packets to transmit, they are starting the transmission in the beginning of a same ...
2
votes
1answer
73 views

Interpretation of “expected cost” of an algorithm

I'm studying randomized algorithms and I sometimes come across results like (1) The algorithm has an expected $O(f(n))$ cost. and (2) With constant probability, the cost is bounded by ...
3
votes
1answer
60 views

How to compute a level set $A=\left\{ \theta:f\left(\theta\right)\geq a\right\} $

I have a real function $f:\mathbb{{R}}^{d}\mapsto\mathbb{R}$, where $d>1$. The question is how to compute the level set $A=\left\{ \theta:f\left(\theta\right)\geq a\right\} $. I am a statistician ...
1
vote
2answers
215 views

Generate random numbers from an interval with holes

Given a set $S$ of $k$ numbers in $[0, N)$. The task is to randomly generate numbers in the range $[0, N)$ such that none belongs to $S$. Edit - Also given an API to generate random numbers between ...
6
votes
3answers
179 views

Computer science problems related to music?

Are there any CS problems, preferably open, that are related to music or musical theory somehow? I would think of problem with musical notation but also probabilities when randomizing according to a ...
6
votes
1answer
93 views

Can expected “depth” of an element and expected “height” differ significantly?

When analysing treaps (or, equivalently, BSTs or Quicksort), it is not too hard to show that $\qquad\displaystyle \mathbb{E}[d(k)] \in O(\log n)$ where $d(k)$ is the depth of the element with rank ...
3
votes
0answers
27 views

Should Expectation Maximization take into account the Naive Bayes' independence assumption?

Should the independence assumption on which the Naive Bayes (NB) classifier is based, be taken into account when applying Expectation Maximization(EM) to infer missing values? The Naive Bayes ...
2
votes
1answer
365 views

Understanding an example of coin toss expectation maximization [duplicate]

I've been trying to get my head around Expectation maximization algorithms, and I thought I'd start simple. I found this 3-coin example here: http://cs.dartmouth.edu/~cs104/CS104_11.04.22.pdf I ...
1
vote
2answers
126 views

distance between histograms

I have 2 histograms that represent the height of characters in 2 images. example: 1 ** 2 **** 3 **** . . . 100 ****** For these 2 histograms I compute the peaks. And To check if these 2 images ...
2
votes
0answers
59 views

Exact Inference in Bayesian Networks

I'm doing some exam study and came across a question I'm not really sure on. Consider the Bayesian network below: Let's denote "Disease" with $D$ and "Symptom" with $S$. I want to find $P(D \mid ...
3
votes
2answers
79 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 ...
3
votes
0answers
69 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 ...
1
vote
1answer
139 views

What is the purpose of Bayesian networks?

I have seen a lot of explanations of what Bayesian networks 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 ...
1
vote
1answer
97 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
52 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
87 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 ...
4
votes
1answer
42 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
110 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
93 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
42 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
467 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 ...
5
votes
1answer
182 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 ...
9
votes
1answer
2k 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
95 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
300 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. ...
4
votes
3answers
68 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
54 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 ...