# Questions tagged [probability-theory]

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

355 questions
Filter by
Sorted by
Tagged with
39 views

### Amount of expected loop iterations when searching an array by random index

Lets say we have an array A of size n. It has 1 as its first index and n as its last index. It contains a value x, with x occurring k times in A where 1<=k<=n If we have a search algorithm like ...
25 views

### An algorithm to determine probability of one string appearing earlier than another string in an evenly distributed binary sequence

Given two binary strings of length $n$ and $m$, determine in polynomial time the probability of the first appearance of one string being earlier than the first appearance of the other one in an evenly ...
22 views

### The average number of dominos

Consider there are $n$ dominos to be placed in a lone (such as "DDDDD", where D is dominos). While placing dominos, they may fall to their right or left, making other dominos in line to fall down. ...
56 views

### generalizing ball-bin problem to k-universal family

I am trying to solve a question in the book on Probability and Computing by Michael Mitzenmacher, Eli Upfal. The question asks to generalize ball-bin problem for 2-universal hashing to $k$-universal ...
901 views

### Generating random words by grammar

A bit of context I was writing a parser for a grammar, and for testing purposes I come up with idea to generate some random inputs. The grammar I was dealing with was much more complicated, in this ...
16k 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 ...
13 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 ...
28 views

### how many parameters do we need to estimate for a general probabilistic model

Its a question from a test in machine learning. I have 3 binary variables x1,x2 and x3 (which means that each one of them can be either 1 or 0), each one of them has a binary output y (can be 0 or 1). ...
39 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 ...
41 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. ...
43 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 ...
37 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(...
41 views

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 ...
37 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)....
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 (...
55 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 ...
444 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: ...
139 views

### Deriving the expected number of steps that is taken to perform the k'th operation

Consider a datatype whose objects will be sequences of elements that has the following two methods prepend($x, T$) which will insert an element to x to the beginning of the sequence T search($T, i$) ...
347 views

### ALOHA - Throughput and probabilities

I have a few questions regarding slotted-ALOHA. Assume a network have 25 users and transmission request probability = 0.25. 1) What is the throughput and what is the probability that a user will ...
455 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 ...
217 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 ...
56 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 ...
29 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 ...
29 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 ...
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 (...
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 ...
53 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 ...
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 ...