Questions tagged [probability-theory]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
2k views

How would you prove a family of functions is universal?

A set of functions from a universe U of keys to n buckets is universal if for every pair of keys in U, say x and y, such that x != y, the probability of h(x) = h(y) is less than or equal to 1/n, for a ...
1
vote
1answer
40 views

“Learning occupancy grid maps with forward sensor models, S.Thurn,2008” a formula that is difficult to overcome

I am reviewing the document" Learning occupancy grid maps with forward sensor models, S.Thrun, 2008" (http://faculty.iiit.ac.in/~mkrishna/ThrunOccGrid.pdf) i am really confused about formula (26), ...
2
votes
1answer
415 views

How can Karger's algorithm (and other randomized algorithms) be used in practice?

Suppose I am given the following problem (the source is here): Disconnect two nodes in a graph by removing minimum number of edges. I would apply Karger's min-cut algorithm. But how can I ...
2
votes
0answers
61 views

Box labelling game

I have a box of stickers. It contains $n$ stickers. Each sticker is labelled with a different number from $\mathbb{Z}$. I have infinite supply of boxes. Box labelling game: I pick a random sticker ...
1
vote
0answers
212 views

EM-algorithm for categorical hidden variables

I have the following model: Let's say two indepentent weighted six-sided dice $X$ and $Y$ with unknown probabilities (i.e. probability of 1 is unkown etc) and they have not necessarily the same ...
3
votes
1answer
201 views

Random Walk on the Integer Line

Suppose we are doing a random walk on the infinite integer line and that we take $2n$ total steps. At every step of this walk, the position of the walker is an integer point on this line. For the next ...
0
votes
1answer
99 views

Reading CLRS analysis of hashing with chaining

I'm currently reading an analysis hashing with chaining, and it goes over two examples: In the first, the search is unsuccessful; no element in the table has key k. In the second, the search ...
3
votes
1answer
203 views

What is the complexity of a variation of the Coupon collector's problem?

I need to know the complexity of the following algorithm: Draw elements from a set of size $m$, one by one, randomly, with replacement, until coming across $n$ different elements from the set ($n\le ...
2
votes
1answer
332 views

Heuristic analysis of Bloom filters

I am currently watching a lecture on Bloom filters, and the professor is doing a heuristic analysis of Bloom filters. It's all based on the following assumption: All $h_{i}(x)$'s are uniformly ...
0
votes
1answer
199 views

Hashing Probabilities

I'm not too sure about how to calculate hashing probabilities, and can't find much documents online to help me with it. Am looking to solve this question "If we hash N items into M buckets using a ...
1
vote
1answer
51 views

Understanding a binary classifier problem

I'm trying to understand a problem that's more mathematical in nature that I'm accustomed to. Below I'll try to present the problem and what I have so far understood of it. The problem We have $X_1,....
0
votes
0answers
108 views

Expected distance between two random nodes in weighted tree [duplicate]

Given an undirected connected graph with N nodes and N-1 edges. Out of N nodes, 1...k nodes are selected, out of which 2 nodes are selected randomly (uniformly). How do I calculate the expected ...
3
votes
1answer
432 views

The throughput of the ALOHA protocol if the Binomial distribution was used

In all the examples of ALOHA I've seen, the Poisson distribution is used. Theoretically, how could the throughput be calculated if a Binomial distribution was used instead? For example, in the case ...
2
votes
1answer
186 views

Deep DFS traverse on graph

According to chess rules, the (undirected) graph generated from the Knight move on a keypad is the following: $$ \begin{array}{ccccc} 3 & - & 4 & - & 9 \\ | & & | & & |...
3
votes
1answer
84 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: ...
2
votes
0answers
134 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
203 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. ...
0
votes
0answers
70 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
93 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 | ...
1
vote
0answers
54 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 ...
3
votes
2answers
435 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
266 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
79 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 ...
5
votes
1answer
391 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
178 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]$ to ...
0
votes
2answers
498 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
463 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
62 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 ...
2
votes
1answer
363 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
117 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 ...
2
votes
1answer
3k 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, ...
5
votes
1answer
1k 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 ...
3
votes
0answers
80 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 the ...
4
votes
1answer
680 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
101 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
428 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 ...
2
votes
1answer
122 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-...
2
votes
1answer
527 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 ...
3
votes
1answer
145 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
72 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
77 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
1answer
299 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
241 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
56 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
270 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
69 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
171 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 k}...
11
votes
0answers
971 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
658 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
79 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 ...