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

learn more… | top users | synonyms

1
vote
1answer
65 views

Complexity of dynamic card game algorithm

Consider the following dynamic card game with a regular deck of 26 red cards and 26 black cards. A dealer draws the unturned cards one by one, and we can ask him to stop at any time. For every red ...
4
votes
1answer
61 views

A facility location problem

Consider the following scenario. There are N localities in a town where population for locality $L_i$ is denoted by $P_i$, $i \in {1,\ldots,n}$. We need to place K hospitals around the town in a way ...
-1
votes
1answer
38 views

Random quadtrees

I have $N$ uniformly distributed 2D points and I want to find out how many points lie in some small rectangular region. However, the number of points can be arbitrarily large (e.g., $N=10^8$), so I ...
1
vote
2answers
61 views

Is shuffling a set of items after popping an item meaningfully more random than doing it once, before starting?

I'm working on a thing to randomly assign people into a shift. There's mostly 2 sets of people, "free" and "assigned". Is shuffling the "free" set after assigning an employee meaningfully more random ...
9
votes
0answers
173 views

Pseudo-random sequence prediction

Disclaimer: I am a biologist, so sorry for (perhaps) basic question phrased in such crude terms. I am not sure if I should ask this question here or on DS/SC, but CS is the largest of three, ...
3
votes
1answer
47 views

How do POMDPs and Dynamic Influence Diagrams differ?

To give some perspective, first consider the following diagram comparing Markov Chains, HMMs, MDPs, and POMDPs (I'm not sure who to credit for it). Fully observable ...
3
votes
1answer
35 views

One-shot Private Randomness Extractor

Suppose a pair of random variables $(X,Y)\in\mathcal{X}\times \mathcal{Y}$ with joint distribution $P_{XY}$ is given. I am interested in a deterministic mapping $f:\mathcal{Y}\to \{0, 1\}^k,$ for ...
2
votes
1answer
34 views

Why arrival process of packets at a switch is not a Poisson Process?

"Packet arrivals are not Poisson .... but some events are, such as web requests and new flow arrivals" I know since the network traffic is very bursty, they are not Poisson. But I am unable to ...
1
vote
1answer
21 views

Dempster-Shafer theory initial belief values

I am looking to implement D-S Theory in my (computer science) research, I'll be using it to determine the probability that a triggered sensor event is a true positive. How would you calculate an ...
4
votes
1answer
38 views

Balanced allocation-Hash table- overflow probability

My question is related to this: Hash-Table in Practice In [1] page 7, it is said that if we throw $n$ balls into $k$ bins, then each bin contains at most $\frac{n}{k}+O(\sqrt[2]{(\frac{n}{k})\log ...
5
votes
0answers
222 views

Alternative to Bloom filter for extreme parameters

A Bloom filter is a space-efficient probabilistic data structure to perform membership-tests on a set (see Wikipedia's page for a definition; I use the same notations below). I am interested in a ...
3
votes
1answer
654 views

What is the best you can do with a noisy message?

You play a TV game in which you have to open one door out of $n$. Behind each door, there is a treasure with probability 1/2, independent of the other doors, so your apriori chance of winning is 1/2. ...
1
vote
1answer
34 views

Simulating continuous time semi-Markov state machine and changing transition probability on the fly

The problem that I'm trying to solve (well, I think that I almost did, but need a review from someone more experienced) is about changing probability of the transition for semi-Markov state machine ...
1
vote
1answer
40 views

Proving simple bound on coupon collector

I came across this paper which gives bounds on coupon colloector problem. Page 451 contains a table where reference to U1 is given as 'folklore'. I presume this is trivial to follow from the ...
3
votes
0answers
31 views

Infer probabilities, for concatenation of words

Fix an alphabet $\Sigma$, and a set of words, $W = \{w_1,\dots,w_n\} \subseteq \Sigma^*$. I have a randomized model that works like this: Alice generates a random sequence of words, using some ...
2
votes
0answers
20 views

Maximum entropy probability distribution among Solomonoff priors

If we take Solomonoff's prior $m$, defined here and normalize it we get a probability mass function on all finite words. But, the pmf isn't completely determined until we fix a universal Turing ...
1
vote
1answer
51 views

Collisions in independent hashing

Let $H$ be a $s$-wise independent family of hash functions from $\{1,\ldots,M\}$ to $\{1,\ldots,N\}$. It is easy to bound one collision, but are there good bounds for muliple collision ?
1
vote
1answer
68 views

How would you implement truly random hash functions in practice?

Suppose that $[U] = [0,...,U-1]$ is the universe from which all elements will be taken, and $A$ a hash table of size $m$. A hash function $h:[U]\rightarrow[m]$ is truly random if For any set of ...
4
votes
2answers
166 views

Minimal number of attempts at a multiple choice exam needed in order to pass, without any prior knowledge

A test is consisted of $N$ multiple choice questions, each has $k$ possible answers. A test solution is the sequence of answers $S\in[k]^N$. Given is a black box which receives a solution as input ...
-1
votes
1answer
46 views

Probabilistic Analysis in real time network : Error in data and feedback channel. Two users communication

I'm studying probabilistic analysis in real time network. We have learn how many attempts in average are required to transmit a packet when there is no error on the feedback channel. With no error ...
4
votes
1answer
45 views

Average vs Worst-Case Hitting Time

Consider a simple random walk on an undirected graph and let $H_{ij}$ be the hitting time from $i$ to $j$. How much bigger can $$ H_{\rm max} = \max_{i,j} H_{ij}, $$ be compared to $$ H_{\rm ave} = ...
2
votes
1answer
73 views

Probabilistic algorithm with two-sided error

I am currently studying probabilistic algorithms and came across three major complexity classes: BPP: worst-case polynomial time, two-sided error RP: worst-case polynomial time, one-sided error ZPP: ...
0
votes
0answers
10 views

Removing the acceptance error from AM

Typically the AM class is defined with error upper bound of 1/3 for deciding both the situations of the membership question being true or false. But curiously enough for the situations when the ...
0
votes
1answer
32 views

Estimate distribution of a composite variable

Suppose I have N sets of numbers (10 numbers per set) {a1, ....., a10}. I form a sum by taking one number at random from each set. SUM = num from set 1 +......+ num from set N. If I do this a large ...
1
vote
1answer
50 views

How does derandomization of 3SAT work via conditional expectations?

Given a single SAT clause with its 3 literals coming from 3 different variables it is obvious that a random assignment of values will satisfy it with probability 7/8 But I do not understand how ...
5
votes
1answer
136 views

Generate a random graph with geometrical degree distribution

I'm working on graph generation, trying to implement the RT-nested-Smallworld network model described in this paper. We are talking about generating an undirected graph in a slightly different way ...
2
votes
1answer
29 views

How does one change the probability bounds in probabilistic complexity classes without changing the class?

I see this theorem whose proof is not clear to me : "Let $L \subseteq \{0,1\}^*$ be a language and suppose that there exists a polynomial time PTM M such that for every $x \in \{0,1\}^*$ and $Pr[ ...
2
votes
1answer
30 views

Can one use the PCP theorem to prove correctness of deternimistic algorithms?

I am thinking of the equality "PCP(O(log(n)),0) = P" Say I have a deterministic polynomial time algorithm $A$ whose correctness I can't prove immediately. But say I create a probabilistic version of ...
3
votes
1answer
143 views

Chernoff bound when we only have upper bound of expectation

If $X$ is a sum of i.i.d. random variables taking values in $\{0,1\}$ and $E[X]=\mu$, the Chernoff bound tells us that $$\Pr(X\geq (1+\delta)\mu)\leq e^{-\frac{\delta^2\mu}{3}}$$ for all ...
3
votes
1answer
79 views

Analysis of sorting Algorithm with probably wrong comparator? [duplicate]

It is an interesting question from an Interview, I failed it. An array has $n$ different elements $[A_1, A_2, \ldots, A_n]$ (random order). We have a comparator $C$, but it has a probability p to ...
3
votes
1answer
55 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 ...
11
votes
2answers
375 views

Efficient 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
80 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
30 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 ...
5
votes
1answer
52 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
101 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
53 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
142 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
1k 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
69 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 ...
9
votes
0answers
231 views

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

Consider the following problem: Input: integers $n > m > k$; $n$ numbers $0 \leq p_1, \ldots, p_n \leq 1$; $n$ numbers $r_1, \ldots, r_n$. Let $X_1,\dots,X_n$ be $n$ independent random ...
-1
votes
1answer
108 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
79 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
100 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
27 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
130 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
70 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
38 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
172 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) = ...