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
36 views

Expected number of coins

Alice and bob play a game. Bob has a well-shuffled deck of $M=4999$ white cards and $N=4999$ green cards. Each permutation of cards in the deck is equally likely. Alice has set some rules for Bob. ...
1
vote
0answers
37 views

Calculate probability in graphical model

I have the following graphical model, in which I wish to compute $p(Intelligence = 1|Letter = 1, SAT = 1)$ But I'm not sure how to rewrite $p(Intelligence = 1|Letter = 1, SAT = 1)$? I was told to ...
-2
votes
0answers
12 views

probability of error for a Bayesian classifier with P(x | c 1 ) = P(x | c 2 ) and P(c 1 ) = P(c 2 )

What is the probability of error for a Bayesian classifier with P(x | c 1 ) = P(x | c 2 ) and P(c 1 ) = P(c 2 )? Why? Does this make sense? if so, can anyone explain this clearly?
1
vote
0answers
41 views

Decomposition of Mutual Information

I came across a book where the author uses the following property of mutual information: Let $X$,$Y$,$Z$ be arbitrary discrete random variables and let $W$ be an indicator random variable. $$ (1)\ \ ...
0
votes
1answer
36 views

Reservoir Sampling vs Round Robin

You are given a List of numbers (length unknown). Let's say the length is 10. GetRandom(List) is called once. If implemented correctly, each number has 1/10 probability of being returned. GetRandom(...
1
vote
1answer
10 views

Why there is no polynomially large sequence of polynomial large weights that derandomize the isolation lemma?

I was studying the paper Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size by Arvind and Mukhopadhyay and came across the following claim (Observation 1.2 on page 3): "More ...
1
vote
1answer
12 views

Probability of selecting a particular set, by sampling without replacement from a categorical distribution

Suppose I have a categorical distribution on items $1,\dots,n$, that assigns probability $p_i$ to item $i$. I now repeatedly sample from this distribution, until I have obtained $k$ unique objects. ...
-2
votes
0answers
45 views

Expected Length of string

Consider a string of length N which contains up to K distinct characters. The compression algorithm works as follows: Replace each maximal contiguous substring containing only one distinct character (...
-1
votes
1answer
31 views

From a randomized algorithm with expected time $O(n)$ to a reliable with determined running time

Let $A$ be a randomised algorithm and $F$ be a function such that $A$ returns $F(x)$ on any input $x$. Furthermore suppose that, for input $x$ of size $n$, the $\textbf{expected}$ running time of $A$ ...
3
votes
0answers
35 views

Node depth in randomly built binary search tree

It can be proved that randomly built binary search trees of size $n$ are of depth $O(\log n)$ and it is clear that level $k$ has at most $2^{k}$ nodes (root's level is 0). I have an algorithm that ...
2
votes
1answer
40 views

Probability of terminating in a state in a probabilistic algorithm

Suppose i have a circular array of $n$ elements. At time $t=0$ i am in position 0 of the array. The algorithm moves left or right with probability $p=1/2$ (since the array is circular when it moves ...
1
vote
1answer
36 views

What kind of bigram probability smoothing is this?

I hope it isn't off topic but I need to understand this example. Given the corpus 12 1 13 12 15 234 2526 and smoothing factor of ...
2
votes
1answer
28 views

Demonstrating that probability for every possible result is uniform at the end of an algorithm

I have memory of $k$ elements that you can imagine being represented by an array. One by one, the array receives a value corresponding to the time index, for example at $t=1$ the value will be $1$. At ...
2
votes
1answer
35 views

If I walk through list and delete every out-of-order element I come across, on average how many elements will be left?

I have a uniformly randomly permuted list of length $n$. I walk through the list element-by-element, and delete an element if it's out-of-order (compared to the previous in-order elements of the list)....
6
votes
0answers
142 views

Correctness of a greedy Algorithm on Knockout Tournaments

You are given a function $\operatorname{rk}:\{1\dots 2^k\}\rightarrow \mathbb{N^+}$ representing the ranks of the players $1\dots2^k$ in a participating in a tournament. The tournament evolves in a ...
0
votes
0answers
11 views

Synthesis of the crisp programs from the Bayesian (probabilistic) programs?

https://arxiv.org/abs/2001.00805 is the article which is pointing towards the direction that the optimal policy of the reinforcement learning can be expressed as the Bayesian/probabilistic program (...
0
votes
0answers
54 views

apply the method of conditional expectations

For a Randomized vertex cover problem Why there is not much hope of deriving an efficient, deterministic version using the method of conditional expectation? I can assume the problem is not ...
3
votes
1answer
429 views

Expected length of a random walk on a line

I am given the following randomized algorithm for SAT, Input: A satisfiable CNF-formula $\varphi$. Output: An assignment $\rho$, such that $\rho \models \varphi$. The algorithm works as follow: ...
8
votes
0answers
111 views

Compute the expected size of an approximation of vertex cover

Consider the following randomized approximation algorithm of vertex cover: Input: A graph G = (V, E). Output: A set $C_G \subseteq V$ a vertex cover of $G$. The algorithm: Set $C_G := \emptyset$. ...
0
votes
0answers
25 views

Expected number of retransmissions for a packet

In a communication link out of p packets one packet will be lost. If stop and wait protocol is used then expected number of retransmissions for a packet? (A) P/(1-P) (B) P (C) 1/(1-P) (D) 1/P ...
3
votes
1answer
26 views

Given an unsorted list of $n$ items, how many random comparisons are needed on average to be able to sort the list?

There is an unsorted list of $n$ items $x_1, \ldots, x_n$. Until you can sort the list, you are given one of the ${n \choose 2}$ possible binary comparisons uniformly at random (with replacement). On ...
0
votes
1answer
45 views

Probability of detecting errors in codewords

I have been struggling with the below question for quite some time, and I don't have a pointer to move forward. A certain Error Control Coding scheme using block codes takes an input block (...
3
votes
0answers
51 views

Probability of colisson for classes of hash functions

I am going through some old exams in one of my courses, and I don't have access to solutions. I've found a problem which I am not sure how to tackle. I am not looking for the answer but some help/...
0
votes
0answers
8 views

Contingency Table Confusion NLP

Hello for the contingency table: [true positive, false negative, false positive, true negative]. I am having a hard time remembering the difference between these terms because all the terms are ...
3
votes
2answers
54 views

In information theory, why is the entropy measured in units of bits?

In information theory, we have the quantity "information". Suppose we have some discrete random variable $X$, that can take values $\{{a,b,c\}}$ with corresponding probability distribution $\{{\frac{...
1
vote
2answers
63 views

Bayes theorem probaility doesn't make sense

I try to use Bayes Theorem to calculate the probability of $P(A|B)$. I have $P(A)$ in column1, $P(B|A)$ in colmn2, $P(B)$ in column 3. I get the following: my calculations were: $$P(B/A) = 0.8\times ...
0
votes
0answers
28 views

Is FOL representation of probabilistic assignment statement correct?

For instance, $x = x + 1[0.3]x+2$ sets $x$ to $x + 1$ with probability $0.3$ and to $x+2$ with probability $0.7$. If I use notation used in the paper "An Analysis of First-Order Logics of Probability"...
4
votes
0answers
44 views

Understanding simulated annealing information theoretically

So I recently rediscovered simulated annealing though a path that others seem to be well aware of. I was aware of Metropolis-Hastings as a sampling algorithm that creates a Markov-Chain who's ...
1
vote
0answers
33 views

Probability of string misidentified in Bloom filter

I'm attempting a question related to Bloom filters: Our Bloom filter uses $3$ different independent hash functions $H_1, H_2, H_3$ that each take any string as input and each return an index into a ...
2
votes
1answer
143 views

Calculating probability of reaching state in DTMC

Consider a highly-connected graph of states & transitions where each transition is marked with a weight (representing probability of occurring) and the graph satisfies the Discrete Time Markov ...
2
votes
1answer
79 views

Does this shuffle have non-zero probability for all permutations?

I was trying to do some code golf, when I created the following algorithm to shuffle a string: ...
2
votes
1answer
35 views

What is the density of a regular language $L$ over an alphabet $\Sigma$ in $\Sigma^n$?

In other words, what is the likelihood that a recognizer of a given regular language will accept a random string of length $n$?   If there is only a single non-terminal $A$, then there are only ...
2
votes
0answers
23 views

The No-Free-Lunch Theorem and K-NN consistency

In computational learning, The NFL theorem states that there is no universal learner. For every learning algorithm , there is a distribution that causes the learner to output a hypotesis with a large ...
0
votes
0answers
15 views

Algorithmic question: distribute balls, optimise for balancing (i) weights (ii) probabilities of picking balls

I have an algorithmic problem that requires some lengthy explanation, which follows below. tl;dr: distribute balls with weights among bags, optimise for balancing both (i) the weights between the ...
3
votes
1answer
78 views

Efficient algorithm to simulate dealing cards from a large deck of cards?

In shedding-type card games, the dealer starts by dealing a shuffled deck of cards to the players (if there are N players, card i...
0
votes
1answer
55 views

information theory, find entropy given Markov chain

There is an information source on the information source alphabet $A = \{a, b, c\}$ represented by the state transition diagram below: a) The random variable representing the $i$-th output from this ...
4
votes
0answers
61 views

Peculiar MCMC sampling problem

I have two random variables, X and Y, and Y is a positive real number. I can sample from $p(y|x)$, but I need to sample from $p(x)$, which I know to be proportional to $\frac 1 {E[y|x]}$. I could ...
2
votes
2answers
114 views

Randomly built binary search trees

In Introduction to Algorithms (CLRS) 3rd Edition, page 299, the section attempts to prove: The expected height of a randomly built binary search tree on $n$ distinct keys is $O(\lg n)$. We define "...
2
votes
1answer
94 views

Introduction to Algorithms (CLRS) Ex 5.2-5 solution

The following is Ex 5.2-5 from Introduction to Algorithms (CLRS), 2nd Edition. Let $A[1...n]$ be an array of n distinct numbers. If $i<j$ and $A[i]>A[j]$, then the pair $(i, j)$ is called an ...
1
vote
1answer
80 views

Calculate probabilty to escape the maze

I am trying to solve the problem to calculate probability to escape the maze and stuck at one use case. Here is the problem statement The Frog is in an two-dimensional maze represented as a table. ...
2
votes
0answers
27 views

Correctness of Karger's min-cut Algorithm

tl;dr in the analysis for Karger's min-cut, the probability of an edge being in the min-cut in the $j$th iteration, $\frac{k}{0.5k(n-j)}$, neglects the fact that all the edges between the two ...
0
votes
0answers
33 views

Construction of hash function with a given distribution

Two questions about the construction of a hash function: Let $U = \{u_1,...,u_n\}$ be a set of size $n$, and suppose that one is interested in a function $h\colon U \rightarrow [0,1]$ such that $h$ "...
1
vote
2answers
63 views

Quicksort where element comparison outcome is random. Probability of element being in a certain position

So we have this block of pseudocode: Monsters = [M1,M2,M3,M4,M5,M6,M7,M8]; qsort(Monsters,rand_compare); qsort() sorts the ...
4
votes
1answer
44 views

How to approach analysis of randomized algorithm

Let us suppose we have a sequence of values $C(i)$ that represent some counter for a given $i$ for $i \in \lbrace 1, \cdots, n \rbrace$. Let us assume some uniform distribution $U$ where selecting any ...
0
votes
0answers
26 views

Interpretation of statement over probability distributions and functions

Consider the following paragraph from this research paper: To learn the generator’s distribution $p_g$ over data $x$, we define a prior on input noise variables $p_z(z)$, then represent a mapping ...
1
vote
1answer
32 views

Prior probability in HMM

This is the HMM model considered in the question And this is the emission probabilities for the respective states. There are two emission values, bringing an umbrella and not bringing an umbrella. ...
4
votes
1answer
58 views

Using Chebyshev to derive an upper bound for Coupon Collecter's Problem

I'm TA'ing a course and have trouble solving an exercise. Let $X$ be a RV defined to be the number of trials required to collect at least one of each type of coupon (of which there are $n$). Then $E[...
2
votes
1answer
32 views

Data points as outcomes of a random experiment

It is well known that Random variable is a function from sample space of a random experiment to $\mathbb{R}$. Consider the following sentences from deep learning book Let $\{x^{(1)}, \cdots , x^{...
4
votes
1answer
68 views

Prove the probability of which a hash function is collision-free

Suppose $H = \{h_1, ..., h_T\}$ be a family of pairwise independent hash functions mapping $\{0, 1\}^n$ to $\{0, 1\}^{n/2}$. Let $M = \frac{2^{n/4}}{10}$ and let $x_1, ..., x_M$ be any M distinct ...
1
vote
1answer
77 views

Constructing hitting sets for randomized algorithms

Suppose A($\cdot$,$\cdot$) is an efficient randomized algorithm and L is a language such that $\text{If }x \in L, \text{Pr}_r[(A(x,r) = 1)] = 1$ and if $x \notin L, \text{Pr}_r[A(x, r) = 0] \ge \...

1 2 3 4 5 8