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

learn more… | top users | synonyms

0
votes
1answer
50 views

Deep DFS traverse on graph

First, the question is based on http://stackoverflow.com/questions/2893470. By chess rules, the (undirected) graph generated from the above problem is the following: $$ \begin{array}{ccccc} 3 &...
4
votes
1answer
44 views

Classification training data, but regression prediction

Suppose I'm performing machine learning on a simple dataset, and have a bunch of training data of the form: ...
0
votes
0answers
6 views

Compute conditional probability [migrated]

If a conditional probability table is given for P(St|M,E). How to compute the value for P(St = x | M = y,E)? where E is binary (0 or 1) Is it correct : P(St = x | M = y,E) = P(St = x|M = y, E = 0).P(...
3
votes
0answers
68 views

Universal lower semicomputable semimeasure and Coding Theorem

I'm following Li and Vitanyi's book "An introduction to Kolmogorov complexity and its applications" 3ed. I'll rewrite here the definitions I need for my question. The authors define the reference ...
2
votes
1answer
40 views

Clock solitaire game and principle of deferred decision

I have been reading the randomized algorithm book by Rajeev Motwani and Prabhakar Raghavan. In section 3.5 they have introduced principle of deferred decision which is a different probability space. ...
1
vote
0answers
18 views

Wald's equation for dependent decrements

I'm taking a course on Coursera about approximation algorithms for fun and one of the modules uses probability to analyze the cost of a linear program with randomized rounding solution to the set ...
1
vote
0answers
7 views

Find minimum conditional entropy

Task : Given $X$ random variables. Find out the minimum conditional entropy for a variable $x_i \in X$ when $x_i$ is conditioned upon any combination $k$ remaining variables. Find $min(Entropy (x_i | ...
0
votes
0answers
12 views

Does marginalizing on a Bayesian network preserve its original independence assumptions?

I know that marginalizing over a Bayesian network causes changes to the graph (e.g. marginalizing node c in the V-structure given by $a \rightarrow c \leftarrow b$ results in $a$ and $b$ being ...
1
vote
0answers
25 views

probability that the vertex set {1,…,k} is component of random graph

Consider a graph with vertices 1,...,n and suppose that each of the $\binom{n}{2}$pairs of vertices is, independently, an edge of this graph with probability p.Let $P_n$ denote the probability that ...
2
votes
2answers
105 views

The transition function in a Markov decision process

A Markov decision process is typically described as a tuple $\langle A,U,T,R \rangle $ where $A$ is the state space $U$ is the action space $T: A \times U \times A \mapsto [0,\infty) $ is the state ...
4
votes
0answers
39 views

Mean and variance of number of buckets of length $i$ in hashing with chaining

Consider a hash table with $m$ buckets, with chaining as collision resolution policy. Given the set $S$ that will be stored in the hash table, let $X_i$ be the number of buckets whose chain length is $...
1
vote
0answers
55 views

Problem with update in Dynamic Bayesian Networks

Consider the following Bayesian network: I want to impose constraints that state that a node can only be true (1) if at least one of its parents are true (1). So, for node $C$, the constraint takes ...
3
votes
1answer
129 views

Reconstructing a screen of permuted pixels

Reconstructing a screen of permuted pixels Summary Given a video with the pixel locations randomly permuted (once, for the entire video), can we (efficiently) reconstruct the original picture? Let: ...
6
votes
1answer
80 views

Two definitions of universal hash functions

I have seen two definitions of universal hash functions in the literature. For any $i \geqslant 2$ let $[i]=\{1,\ldots,i\}$. Definition 1: A family $\mathcal H$ of hash functions from $[n]$ ...
0
votes
0answers
24 views

Probability of producing a correct result at time t

A system with 3 nodes, as a function of time the probabilities of each of the 3 nodes producing a correct results are 0.99, $e^{(-t/10000)}$, $e^{(-t/1000)}$, respectively. How would you use the nodes ...
0
votes
2answers
34 views

Probabilities, Unigram and Bigram [closed]

Assume that we have these bigram and unigram data:( Note: not a real data) bigram: #a(start with a) =21 bc= 42 cf= 32 de= 64 e#= 23 unigram: # 43 a= 84 b=123 c=142 f=161 d=150 e=170 ...
1
vote
1answer
65 views

Markov Chain Mixing Time of the Complete Graph

I'm having a hard time understanding mixing time for Markov Chains on Complete Graphs (Kn). We can define the probability matrix for Kn where Pi,j=probability of going from i to j (technically 1/...
4
votes
1answer
53 views

Summation of a Random Variable

I'm having trouble grokking Cormen's Algorithms book on pg. 120. The context is the hiring problem (as it is called in the book). Here is the part that is tripping me up: "Let X be the random ...
1
vote
1answer
50 views

Expectation Maximization Algorithm for simple naive Bayesian network

I am trying to understand the following network A has two children - B & C (aka common cause) All the variables are binary and can be either 0 or 1. In data values are missing only for some ...
10
votes
1answer
94 views

What is the chance that this code terminates?

I wrote this Python code, and wondered if it sometimes simply doesn't terminate (assuming we had infinite memory/time and no recursion depth limit). Intuitively you'd think it terminates, since at ...
1
vote
1answer
54 views

Why is ZPP = RP ∩ co-RP?

I am trying to prove the theorem that ZPP = RP $\; \cap \; co-RP$. If $L \in \; \subseteq RP \; \cap \; co-RP$ then I can see that it belongs to $ZPP$. But I am unable to prove the reverse direction, ...
3
votes
1answer
78 views

What does the “principle of deferred decisions” formally mean

I have encountered the phrase "Principle of deferred decisions" in Mitzenmacher and Upfal's book on Randomized Algorithms and several other courses online. Isn't it just conditional probability? In my ...
4
votes
0answers
45 views

Output process of a G/M/1 queue

What is the output distribution of a GI/M/1 (general input process and exponential service times) queue. The GI/M/1 is according to Kendall's notation: arrivals are independent but we do not know ...
4
votes
1answer
126 views

Huffman Coding and Depth Calculation?

I'd like to as a variation on this question regarding Huffman tree building. Is there any theory or rule of thumb to calculate the depth of a Huffman tree from the input (or frequency), without ...
1
vote
1answer
57 views

Different probabilistic statement for Simple Uniform Hashing

Let me denote the number of elements with $n$ and the size of the table with $m$. I was trying to understand the Simple Uniform Hashing assumption that people and books describe in works and make them ...
2
votes
3answers
70 views

What is the formal analysis with Simple Uniform Hashing that the load factor is $\alpha = \frac{n}{m}$

Recall the definition of the load factor is the average number of elements in a chain for hashing for a table $T$ of size $m$ (with $n$ elements in consideration). Let $n_j = T[j]$ be the size of the ...
1
vote
1answer
62 views

Probability bounds on size of smaller partition in randomized quicksort

Let $0 < a < 0.5$ be some constant. We have an $n$-element array as input. Randomized quicksort chooses one element from array uniformly at random as a pivot and partitions. With probability $1-...
1
vote
1answer
107 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
75 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
40 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
62 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 ...
10
votes
1answer
204 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, so ...
3
votes
1answer
61 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 ...
4
votes
1answer
40 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
53 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
24 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
54 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 ...
6
votes
0answers
316 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
657 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
39 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
41 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
38 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
23 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 ...
2
votes
1answer
95 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
86 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
181 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
54 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 learned 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
51 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
126 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
1answer
34 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 ...