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

learn more… | top users | synonyms

0
votes
0answers
4 views

“Practical forms” of Chernoff bound for inequality in expectation

From Wikipedia: The above formula is often unwieldy in practice, so the following looser but more convenient bounds are often used: (i) $Pr(X\geq (1+\delta)\mu)\leq ...
3
votes
1answer
42 views

Algorithm to generate two diffuse, deranged permutations of a multiset at random

Background $\newcommand\ms[1]{\mathsf #1}\def\msD{\ms D}\def\msS{\ms S}\def\mfS{\mathfrak ...
3
votes
1answer
56 views

What do we know about $NP \cap co-NP$?

What do we need about the intersection of $NP$ and $co-NP$ apart from the fact that $P$ is a subset of it? (beyond what these answers here say, What do we know about NP ∩ co-NP and its relation to ...
2
votes
1answer
25 views

Return values of Probabilistic Programs

Syntax and semantics section of this paper on probabilistic programming mentions that the return expression of the program is a function f satisfying $ f : \sum \rightarrow ...
4
votes
1answer
45 views

Distribution of Ones in a Psuedorandom Sequence

Let S be a string in the set (0,1) produced by taking the AND of the output of two maximal length linear feedback shift registers of large period (say 128 bits). It's easy to see from the truth table ...
8
votes
2answers
2k views

What are Markov chains?

I'm currently reading some papers about Markov chain lumping and I'm failing to see the difference between a Markov chain and a plain directed weighted graph. For example in the article Optimal ...
1
vote
1answer
31 views

Markov Chain w/ non-stochastic matrix

I've come across a problem which at first appeared to be a markov process however the transition matrix of the graph is non-stochastic. That is, the probabilities among edges leaving a node do not sum ...
5
votes
1answer
45 views

Random Graph is a good expander

If a (n,d) random graph is a n-vertex graph defined as : Choose d random permutations $\pi_1 \ldots \pi_d $, from [n] to [n]. Take edge (u,v) if $v = \pi_i(u)$ for some i. I am trying to prove that, ...
-1
votes
1answer
68 views

Naive Bayes MapReduce

I have the following question to answer in a MapReduce assignment sheet The Naive Bayes classifier is a widely-used tool for analyzing data. Consider a data set that has $n$ data items, each of ...
0
votes
2answers
129 views

How to calculate probability of packet loss and drop rate?

In a queuing system (M/M/1) with a finite packet capacity $z$, how do you determine the probability of packet loss if we assume that packets are dropped when the system is full? Packets arrive with a ...
0
votes
1answer
39 views

Why is the most probable assignment for all variables in MRFs called MAP assignment?

I am new to graphical model, especially Markov Random Fields. I have a question about MAP assignment. Let say we have the graph structure and all the potential functions. MAP assignment in MRFs is ...
8
votes
0answers
189 views

Choosing a subset of binary variables to maximize the sum of the highest $K$

Given $N$ probabilities $P_1,\dots,P_N$ and rewards $R_1,\dots,R_N$ and the integers $M,K$ $(N>M>K)$ as input, define the random variables $X_1,\dots,X_N$ as $$X_i=\begin{cases} R_i & ...
-1
votes
1answer
48 views

Understanding polynomial equality testing using randomized algorithms

A file is downloaded from a server and is represented as $a = \{0, 1\}^n$. The server has that file as $b = \{0, 1\}^n$. We want to ensure a degree of certainty that $a=b$, using a randomized ...
2
votes
0answers
68 views

Optimal wagering to minimize expected time to reach a target payoff

Suppose for simplicity we start off with starting amount $S = 1$ and we wish to reach target amount $T$. To do this we sequentially wager a certain amount and then win that amount with probability $p$ ...
1
vote
1answer
67 views

Anagrams solver based on transitions probability

I have an English dictionary (text file) and the frequency of 2-grams, 3-grams and 4-grams as the beginning of each word. I need to write an algorithm that, with a given word, calculates the possible ...
2
votes
1answer
20 views

Using all the entropy in an biased bit

Suppose we have $n$ bits of random-looking data, and we want to encode it in such a way that instead of 1/2 the bits being 1's, we have (say) 3/4 the bits being 1's. The entropy of each bit in the new ...
1
vote
1answer
65 views

Why the analysis of Aloha protocol uses Poisson distribution?

Pretty much in all of the analysis of the Aloha protocol that I read, it is assumed that the distribution of packet arrivals is Poisson. What is the rationale behind it? Isn't it actually binomial ...
1
vote
2answers
39 views

Calculating the number of unique BST generatable from n keys, why is my number so large

I want to find the number of distinct BSTs I can get with 3 unique keys (i.e. 1, 2, 3) Here's my solution: In case 1, we have each node have possibility, 3, 2, 1, respectively, so 3*2*1 = 6 ways ...
3
votes
1answer
19 views

PRNG bad seeding and von Neumann unbiasing

Large period PRNGs such as Mersenne Twister require good seeding otherwise the initial output in the sequence may not seem to be high-quality, at least for the first few words (and in the way that is ...
2
votes
1answer
46 views

Turn biased random number generator into uniform

I'm looking at a problem in the book Introduction to Algorithms by Cormen et al. It says that if we are given a random number generator rand() which satisfies the distribution: $P(X = 0) = ...
2
votes
1answer
50 views

How to find a 2-wise independent hash family that is not 3-wise independent?

I'm trying to find a family of hash functions mapping $\{1, 2, ..., 2^n\}$ to $\{0, 1\}$ that is 2-wise independent but not 3-wise independent. Any ideas on that? I know two 2-wise independent ...
3
votes
1answer
81 views

Counting nodes in a trie

I'm studying random tries in one of my classes, and was wondering if anyone could offer any guidance regarding a problem. Question: Given a random $m$-ary trie with $n$ total leaves, letting $I$ be ...
1
vote
1answer
45 views

Prove that this family of hash function is $3$-wise independent, but not $4$-wise independent

Consider the hash function mapping $w$-bit keys to hash values in $\{0,...,m-1\}$. Suppose $w=cr$. Interpret a $w$-bit key $x$ as a vector $(x_1,...,x_c)$ of $c$ $r$-bit keys. Consider the ...
2
votes
1answer
84 views

Show that the following family of hash functions is $2$-wise independent but not $3$-wise independent

I've really been thinking about and working on this problem for a while, and I would appreciate if someone could offer any help towards the solution. Consider the following family of hash ...
2
votes
1answer
40 views

Is the Source Coding Theorem straightforward for uniformly distributed random variables?

Shannon's source coding theorem states the following: $n$ i.i.d. random variables $X_1,\dots,X_n$ each with entropy H(x) can be compressed into more than n⋅H(x) bits with negligible risk of ...
1
vote
0answers
35 views

Intelligent Agents-Probability and Beliefs

I am reading about probability and beliefs in artificial intelligent agents, and came across the following passage: Why the axioms of probability are reasonable The axioms of probability can ...
1
vote
0answers
30 views

Using “incremental algorithms” to find the $k^{th}$ smallest number

This is what I vaguely understand of what an "incremental algorithm" is - say one such for calculating the $k^{th}$ smallest number for a given sequence of elements $x_1, x_2,...,x_n$ then after the ...
2
votes
2answers
50 views

About sorting numbers in linear time

If one is given $n$ numbers picked uniformly at random from the interval $[0,1]$ then is it possible to sort them in linear time? It seems to me that some such method exists which uses binary ...
2
votes
0answers
31 views

How to find number of occurences of specific distances in binary (search) trees?

I want to calculate the amount of tree structures that have a given maximal distance between two nodes given an amount n of nodes (or keys). E.g. with ...
4
votes
1answer
55 views

Mutual information intuition

I was creating an example for a casual talk on mutual information. I considered a system of two coins, which with probability 1/2 are copies of each other, and with probability 1/2 are independent. ...
-2
votes
1answer
44 views

Find the approximate number of messages (n) that need to be tried

Find the approximate number of messages (n) that need to be tried before finding two that had the same message digest (size k) with probability 0.8. You need to find n as a function of k . What is n ...
12
votes
4answers
355 views

Simulate a fair die with a biased die

Given a biased $N$-sided die, how can a random number in the range $[1,N]$ be generated uniformly? The probability distribution of the die faces is not known, all that is known is that each face has a ...
-2
votes
1answer
394 views

Probabilty that quicksort partition creates an imbalanced partition

I have come across this question: Let 0<α<.5 be some constant (independent of the input array length n). Recall the Partition subroutine employed by the QuickSort algorithm, as explained in ...
11
votes
7answers
3k views

How to simulate a die given a fair coin

Suppose that you're given a fair coin and you would like to simulate the probability distribution of repeatedly flipping a fair (six-sided) die. My initial idea is that we need to choose appropriate ...
2
votes
1answer
91 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
459 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
120 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
149 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
105 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
123 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
96 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
80 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
65 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
138 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
35 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
238 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
63 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 ...
5
votes
1answer
371 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
106 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
95 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 ...