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

learn more… | top users | synonyms

2
votes
1answer
54 views

Arrangement of numbers in a grid

I have a $n \times m$ matrix $M$ and a permutation of sequence $P$ of numbers from $1$ to $n$. I have to fill the matrix using numbers $1$ to $n \times m$ in such a way that for each row $i$, the ...
3
votes
2answers
298 views

Returning a random subset with length k of N strings while only storing at most k of them

Here's the problem. I've written a program that reads strings from stdin, and returns a random subset of those strings. The only other argument provided to the program is the length of the subset, ...
1
vote
1answer
37 views

In an M/M/1 Queue, what does exponential distribution of service time mean?

I was reading about the M/M/1 Queue and that we assume new customers arrive according to a Poisson distribution, and each customer takes an amount of time to ...
-4
votes
1answer
12 views

m-element random sample being equally likely …(CLRS 5.3-7)? [closed]

I am trying to understand the following solution to CLRS 5.3-7: http://clrs.skanev.com/05/03/07.html Question description is on the page. I understood the part where m-element subset is constructed ...
7
votes
1answer
92 views

Which one of these two sequences is random, and which one is not?

We let $\alpha = \alpha_1\alpha_2\alpha_3\ldots$ be an infinite random sequence (under the uniform measure) where $\alpha_i$ may be $1$ or $0$, and then define the boolean function $B_k$: $$ ...
8
votes
1answer
80 views

Probability Distributions and Computational Complexity

This question is about the intersection of probability theory and computational complexity. One key observation is that some distributions are easier to generate than others. For example, the problem ...
2
votes
0answers
71 views

What is the average-case running time of Fun-sort?

I read this paper: http://www.sciencedirect.com/science/article/pii/S0166218X04001131?np=y (you can check the PDF online for free), and I translated section 4's Fun-sort algorithm (correct me if I'm ...
6
votes
1answer
52 views

Expected number of maximal cliques in $G(n,p)$

The $G(n,p)$ random graph model creates graphs with $n$ vertices and each possible edge exists independently with probability $p\in (0,1)$. Much is known about the (expected) size of a largest ...
2
votes
1answer
31 views

Understanding Expected Running Time of Randomized Algorithms

I want to understand the expected running time and the worse-case expected running time. I got confused when I saw this figure (source), where $I$ is the input and $S$ is the sequence of random ...
1
vote
1answer
101 views

Understanding Monte Carlo Probabilities

I am trying to get a good grasp on Monte Carlo (MC) algorithms, but I feel I am missing something fundamental. What I don't understand is how MC improves its confidence of giving the correct solution ...
1
vote
0answers
27 views

What is linear relaxation in the context of bayesian networks? [closed]

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
77 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
51 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 ...
4
votes
1answer
361 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
77 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
81 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
52 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
30 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
75 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
92 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
61 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
97 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 ...
6
votes
1answer
133 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
58 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
63 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
137 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
68 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
77 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
176 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
202 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
124 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
380 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
100 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
62 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
250 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
188 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
95 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
411 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
174 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
67 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
83 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
70 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
150 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
102 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
56 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
48 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
125 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, ...