Questions tagged [probability-theory]

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

Filter by
Sorted by
Tagged with
5
votes
0answers
74 views

Is resampling random variables to maximize value NP-hard?

Setup Let $S = {X_1, ..., X_n}$ be a set of independent binary random variable, i.e. $X_i \in \{0, 1\}$, each with prior $P(X_i = 1) = p_i$. The $X_i$ are not iid, so $p_i, p_j$ need not be equal if $...
2
votes
0answers
20 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
10 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
71 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
46 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
58 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
31 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
43 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
52 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
18 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
30 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
44 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
41 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
25 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
27 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. ...
3
votes
1answer
52 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
62 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
63 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 \...
0
votes
1answer
17 views

Assumption of a generation of the dataset by a probability distribution

Consider the following paragraph from the deeplearningbook The training and test data are generated by a probability distribution over datasets called the data-generating process. We typically ...
3
votes
1answer
37 views

The expectation of the total number of pairs of keys in a hash table that collide using universal hashing

I am reading CLRS relating to perfect hashing. When computing the $$ \mathbb{E}[\sum_{j=0}^{m-1}{n_j\choose{2}}] $$ where $m$ is the number of slots in the hash table, and $n_j$ is the number of keys ...
0
votes
0answers
30 views

Question on preventing k from reducing too quickly during KMV intersection

This question considers KMV, an algorithm that is able to estimate the cardinality (unique item) from a stream of data. The way it does it is to first map the stream of data to a space that almost ...
2
votes
1answer
60 views

How do we prove the time complexity of this simple problem in probabilistic inference on a Bayesian network?

Suppose we have a simple Bayesian network with two rows of nodes: $x_1, x_2, \ldots, x_n$ and $y_1, y_2, \ldots, y_n$. Each node $x_k$ takes a state of either 0 or 1 with equal probability. Each ...
0
votes
0answers
44 views

Derive the expected # of steps that are taken to perform all the operations (n operations) [duplicate]

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$) ...
1
vote
1answer
112 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$) ...
2
votes
2answers
95 views

expected length of linked list

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$) ...
2
votes
1answer
21 views

How do you marginalize in graphical model elimination?

I'm reading Michael I. Jordan's book on probabilistic graphical models, and I don't understand the elimination algorithm presented in chapter 3. To narrow the question down, consider page 6. In ...
0
votes
1answer
63 views

Hitting probability of random walk within given number of steps

Given m,n dimensions of a 2D matrix; (i,j) initial co-ordinates; (x,y) final co-ordinates. What is the probability of being at (x,y) after at most k steps if we start from (i,j) initially? We can ...
2
votes
1answer
72 views

Network throughput with random delay selected from uniform distribution

Background: I am working with IoT devices which broadcast status messages over a wireless channel periodically and at a rather high rate (500-5000 Hz). Receiving every message is not crucial but the ...
0
votes
0answers
28 views

Probability in 1-universal hash function

I am trying to prepare for an exam and I am not sure how to solve this task: Given is a hash function with m buckets, which uses a 1-universal hash function h: U -> H and handles collisions with ...
3
votes
1answer
52 views

Sampling numbers from a weighted set that sum to constant value

So I have a multi-set of positive integers $S = \{n_1, n_2, \dots\}$ with associated weights $W = \{w_1, w_2, \dots\}$. I want to sample some numbers, without replacement, from $S$ according to ...
2
votes
1answer
55 views

Bertrand's ballot theorem

I want to understand the dynamic programming equation of https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem theorem. it is this If i number of people voted for A and j number of people voted ...
2
votes
1answer
30 views

Complexity/Hardness of a generalization of an Inclusion/Exclusion problem

I would appreciate some help in determining the complexity/hardness of an inclusion/exclusion problem described in Wikipedia: https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle#...
1
vote
0answers
41 views

How to generate a random number in a given range with uniform probability [closed]

I have used programming languages which generate a random number in a given range. Let's say we have a range of 1 to 10 each number has the probability of 1/10 to get selected. What is the criteria ...
1
vote
1answer
69 views

Proof of an Infinite Binary Sequence

I have a problem where given an infinite binary sequence S ∈ {0, 1}∞ to be "prefix-repetitive" if there are infinitely many strings w ∈ {0, 1}* such that ww is a prefix of S. I need to prove that if ...
1
vote
0answers
28 views

Probability lower bound on a double cycle on two vertices in random cuckoo graph

I have read Chater 17. Balanced Allocations and Cuckoo Hashing in Mitzenmacher. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis and got ...
2
votes
0answers
47 views

Probability of a double cycle in cuckoo graph

I have read Chater 17. Balanced Allocations and Cuckoo Hashing in Mitzenmacher. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis and got ...
1
vote
1answer
36 views

Expectation for the number of leaf nodes in a randomized tree construction

Consider this procedure for building a tree from $v_1, v_2, ..., v_n$: insert $v_1$ insert $v_2$ and connect it to $v_1$ via a directional edge from $v_2$ to $v_1$ insert $v_3$ and with a uniform ...
1
vote
1answer
30 views

Expectation of $u'^t v$ = $u^t v$

I have another question with dimensionality reduction. I have a matrix $S \in R^{k \times d}$ and S is in {$- \frac{1}{\sqrt k}, \frac{1}{\sqrt k}$} and i have two vector $u,v \in R^d $. I need to ...
2
votes
1answer
34 views

HyperLogLog leading zeros distribution

I'm reading this article. In particular I'm having some trouble trying to replicate the results of the first image in that article. For x=9, the graph says that the probability is 0.20 aprox. But ...
1
vote
1answer
22 views

Expectation of $\langle s,x \rangle^2$

I'm studying dimensionality reduction (SVD in particular), and I saw the following question: Assume we have a vector $x \in \mathbb R^d$, and consider $F(x)=s^t x$ , where $s$ is a $d$-...
0
votes
2answers
94 views

probability of collision

my data's range is from 1 to 9 and I have two subsets of integers from this range. the hash function takes each of this subsets and calculate product of these three integers and maps this set to the ...
1
vote
1answer
9 views

Is there a term for the distribution of numbers-of-digits of a bounded uniform distribution

Let $X$ be an integer sampled uniformly from the (integer) range $\{ 0...2^k - 1 \}$ . Now, consider the distribution of $\#\text{bits}(X) = \begin{cases} 1 & X = 0 \\\\ 1 + \lfloor \log_2(X) \...
1
vote
1answer
42 views

How can I minimize floating point error when multiplying normal distribution PDFs?

If you multiply two normal distribution PDFs with means $\mu_1$ and $\mu_2$ and variances $v_1$ and $v_2$, then according to this page, the new mean is $$\mu = \frac{\mu_1 v_2 + \mu_2 v_1}{v_1 + v_2}$...
1
vote
1answer
16 views

Confusion About Min-Cut Probabilities

Currently going through a video on Counting Minimum Cuts by Tim Roughgarden. $(A_{i},B_{i}) = \big((A_{1},B_{1}), ..., (A_{t},B_{t})\big) \forall i \in \Bbb{R}$ $P\big((A_{i},B_{i})\big) \geq \frac{1}{...
3
votes
1answer
205 views

expected pairwise square euclidean distance between points

How can I show that the expected pairwise square euclidean distance between points in $X$ is $Θ(d)$? Where $X$ is a $(x_1,...x_n)$ of points generated uniformly at random in the unit, d is d-...
1
vote
1answer
16 views

How many prefix code we can find for a given distribution of probability?

A source emits 5 signals s1, s2, s3, s4 and s5 whose probabilities are as follows: 1/3, 1/3, 1/9, 1/9, 1/9, 1/9. How many prefix codes we can construct on A={a, b, c}? And how many are there with the ...
1
vote
1answer
100 views

Is the bitwise-xor of a Uniform bit string and a non_uniform bit string Uniform?

Having two bit strings $x,y \in \left\{0,1\right\}^n$, where $x$ is selected following a uniform distribution but $y$ is not. Is $z = x \oplus y$ uniform?
3
votes
1answer
17 views

Variance of MAXSAT clause satisfiability

For a given MAXSAT problem, it is trivially easy to compute the mean number of clauses satisfied for all assignments, or equivalently the expected number of clauses satisfied by a random assignment. ...
0
votes
1answer
21 views

What is the relation between the quantity of information of $A_i$ and $A$, where $A=\bigcup_iA_i$?

Let $A$ be an event divided into 4 events $A_i$ with the same probability. Why does the quantity of information of $A_i$ satisfy $$ I(A_i) = I(A) + \log (4)?$$