Questions tagged [probability-theory]

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

Filter by
Sorted by
Tagged with
1 vote
0 answers
29 views

Complexity class of a problem asking for a chance of receiving an item

I have asked a question on math.SE about if there is a way to do it better than by brute force, but this time I am interested in the complexity of the problem itself. I will repeat the problem, with a ...
rus9384's user avatar
  • 1,429
3 votes
1 answer
88 views

How many random bits does this algorithm use on average?

Here, flip() is a function that returns 0 or 1 with equal probability. It can be proved ...
Ilkay Burak's user avatar
0 votes
1 answer
23 views

Cormen chapter 11 probability of two keys being assigned the same slot simple uniform hashing

I have been reading Cormen's chapter 11 and I stumbled upon the following statement on page 260 (3rd Edition): Let xi denote the ith element inserted into the table, for i = 1, 2 ... n, and let ki = ...
carlos palma's user avatar
1 vote
1 answer
38 views

Number of non-zero elements in intersection of two bloom filters

Let us assume I use bloom filters of size $m$ bits with $k$ hash functions. Now I have two set $X$ and $Y$. Let $B(X)$ be bloom filter of the set $X$. In general I know that $B(X\cup Y)= B(X) \lor B(Y)...
Galois group's user avatar
0 votes
0 answers
17 views

Transductive Information Maximization vs classification with feature embedding in higher dimensional spaces?

Recent research work has shown that transductive learning/inference outperforms standard methods that were used before, where people embed features in a high dimensional space and then use the ...
Sandra's user avatar
  • 63
0 votes
1 answer
22 views

Latent variable model from measure theory perspective

It's common in machine learning papers to see things like $p(x,z|\theta)$ or $p(x|z)$. Where $x$ is usually the data vector, $z$ the latent vector and $\theta$ the model parameter, like network ...
SecondOrderConfusion's user avatar
2 votes
0 answers
75 views

Distribution of $k$-matchings in a random graph

Take the Erdos-Renyi random graph $G(n,p)$, i.e. the random graph with $n$ vertices and where each possible edge has an independent probability of $p$ of being present. Recall that a $k$-matching is a ...
Harry Vinall-Smeeth's user avatar
0 votes
1 answer
69 views

Finding the first vertex in a recursively growing graph

I have an undirected graph which grew according to a recursive algorithm, i.e., it started with a single vertex and then, one after another, new vertices arrived and connected to existing ones. Now, I'...
Bob Aiden Scott's user avatar
1 vote
0 answers
17 views

definition of P-samplable distribution that allows non-binary fractions

Arora and Barak (in chapter 18, on average-case complexity) define a polynomial-time samplable (or P-samplable) distribution $D$ (actually a family $\{D_n\}$, for each output length $n$) as having an ...
Shivaram Lingamneni's user avatar
0 votes
0 answers
8 views

Does optimal input distribution for $W^{\otimes n}_{Y|X}$ tell us anything about the optimal input distribution for $W^{\otimes n-1}_{Y|X}$?

Suppose I have $n$ i.i.d. copies of some channel $W_{Y|X}$ for some finite $n$. I wish to send the maximum number of messages over these $n$ copies such that the error in decoding the message is at ...
user1936752's user avatar
0 votes
0 answers
41 views

If $\overline{3SAT}\in BP\cdot NP$ then $PH=\Sigma_3^P$

I have the problem If $\overline{3SAT}\in BP\cdot NP$ then $PH=\Sigma_3^P$ To solve this I am using a result $BP\cdot NP\subset NP/poly$ which I can prove (not doing here). I have two solutions but ...
Soham Chatterjee's user avatar
1 vote
0 answers
38 views

distribution choice for network latency

Consider this situation. A few clients are connected to a server over the internet. I define network latency as the time between request leaving the client and reaching the server. What distributions (...
whoisit's user avatar
  • 111
2 votes
1 answer
126 views

Dynamic programming: optimal order to answer questions to score the maximum expected marks

You have $n$ questions in an exam. Question $i$ is answered correctly with probability $p_i > 0$. If question $i$ is answered correctly, you get $R_i$ marks. You can choose to answer the questions ...
maynis's user avatar
  • 23
1 vote
0 answers
68 views

How can the mutual information be equal to minus conditional entropy? [closed]

I am reading the following paper: https://arxiv.org/abs/2301.06941 The authors in Eq.(8) have obtained a relation which has the mutual information, $i$, in the exponent of the exponential on the RHS ...
user avatar
0 votes
0 answers
60 views

Universal hash functions and prime number modulus scheme

Definition of a universal hashing function $h: U \rightarrow[m]$ (where $[m]=\{0, \ldots, m-1\}$) is that for any given distinct keys $x,y \in U$, when $h$ is picked at random (independently of $x$ ...
Jung's user avatar
  • 101
0 votes
0 answers
22 views

Manipulating a binary tree representation

I am designing a discrete probability distribution with a string of binary values as an input $\{s_i\}\in\{S_i\}$, and binary outputs $e\in E$ with Bernoulli probability $P(E=1|\{S_i\})=XOR[\{S_i\}]=...
Jordan K's user avatar
1 vote
1 answer
66 views

Generate uniform random vectors

Problem : Consider a random vector $v$ which is uniformly distributed over the sample space $S = \{v \in \mathbb{Z}^{n} : 1^Tv = a , v \ge 0\}$ . How to efficiently generate such random vector ? note :...
C.C.'s user avatar
  • 129
1 vote
1 answer
120 views

Distributing cards randomly given constraints

We want to distribute 3*n known cards among 3 players evenly given a set of constraints that prohibits some players from having certain suits. For example: We want to distribute 1H, 2H, 3S, 4S, 5D, 6D ...
SAKO's user avatar
  • 11
3 votes
1 answer
93 views

Algorithm to select a random bit string with constraints

Problem Description Given $a, b, n \in \mathbb{N}$ with $a < b < n$. Let $M$ be the set of all possible bit strings of length $n$ which begin and end with one and have at least $a$ and at most $...
user13062187's user avatar
1 vote
1 answer
38 views

Expected value of maximum of a matrix of size $n$

I have a square matrix (call it $A$) of size $n$ ($n$ is a positive integer). Each column is a permutation of $[1:n]$. I take the first row of $A$, i.e. $A(1,:)$ and wonder what will be the frequency ...
fox's user avatar
  • 183
0 votes
1 answer
20 views

influence of neighourhood points

Im trying to understand the following question. Suppose $h,f:\{-1,1\}^n\rightarrow \{-1,1\}$ satisfy $\sum_x h(x)f(x)\leq 0.5$, then one can rewrite this as $\textsf{Pr}_x [h(x)=f(x)]\leq 3/4$. Can we ...
wwjohnsmith's user avatar
1 vote
2 answers
52 views

Probabilty of Elements being smaller than a specific value

Right now i am looking at the following statement, but i cant grasp why it is correct. Can somebody help? "If we look at F0 uniformly distributed (and, say, pairwise independent) elements of [0, ...
Ilian kurt's user avatar
3 votes
0 answers
51 views

Edge length in an EMST

Consider a domain on a unit grid such that the grid nodes hold a point with probability $\frac12$. We construct a Euclidean minimum spanning tree on these points. How could we compute the probability ...
user avatar
2 votes
1 answer
86 views

Probability of this random selection

Suppose we have an array of $n$ integers. Suppose that we pick one of these elements uniformly at random and call it $x$. Suppose that $\log n$ elements are also sampled (uniformly at random) from the ...
joeren1020's user avatar
3 votes
1 answer
728 views

Is it possible to randomly allocate items to bins such that each distinct allocation has equal probability?

I'm trying to randomly allocate N indistinguishable items over B indistinguishable bins with unlimited capacity. Each allocation should occur with equal probability. An allocation identifies the ...
programonkey's user avatar
2 votes
0 answers
42 views

Generalizing Fano's Inequality [closed]

Fano's inequality says the following: Theorem: Let $X$ be a random variable with range $M$. Let $\hat{X} = g(Y)$ be the predicted value of $X$ given some transmitted value $Y$, where $g$ is a ...
new_student's user avatar
0 votes
0 answers
24 views

Conditional probability of making claim by insurance policyholder

In any given year,a male automobile insurance policyholder make a claim with probability $p_m$ and a female automobile insurance policy holder will make a claim with a probability $p_f$ where $p_f \...
Win_odd Dhamnekar's user avatar
3 votes
2 answers
102 views

Rank in a Convex Combination

Given vectors $A, B \in \mathbb{R}^{n}$, $w \in [0,1]$ and $x \in \mathbb{R}$, let $$ Rank(A,B,w,x)=\sum_{i=1}^{n} \boldsymbol 1 \{w A_{i} +(1-w) B_{i} < x\} $$ denote the number of elements in the ...
hilberts_drinking_problem's user avatar
0 votes
1 answer
49 views

Expected value of Markov chain after nth steps

A Markov chain $\{ X_n, n \geqslant 0\}$ with states 0, 1, 2 has the transition probability matrix $$P= \begin{bmatrix} \frac12 & \frac13 & \frac16 \\ 0 & \frac12 & \frac23 \\ \frac12 &...
Win_odd Dhamnekar's user avatar
1 vote
1 answer
53 views

Average and max. hitting time to a specific vertex [closed]

Consider simple random walks that stop when reaching a given node $x$ in an undirected, unweighted and connected graph on $n$ nodes. Let $H(i,x)$ denote the (expected) hitting time from $i$ to $x$, ...
fawadria's user avatar
  • 113
1 vote
1 answer
100 views

Sample a set of N numbers without replacement, each element taken from N different weighted sets

Here's my problem: I have $N$ sets of integers $S_i$ where $|S_i| = n_i \forall i \in [1,N]$ each with non-uniform weights $W_i = \{w_{i,1}, ..., w_{i,n_i}\}$ such that $\sum_{j}{w_{i,j}} = 1$. I want ...
Montspy's user avatar
  • 23
1 vote
1 answer
21 views

Conditional entropies of sum relations

Let $(X_1,Y_1)$ and $(X_2,Y_2)$ be identically and independently distributed. Also consider $Z=X_1+X_2$. I am trying to prove the following inequality: $$ H(X_2 \vert Y_1 Y_2 Z) \leq H (X_1 \vert Y_1)\...
Root's user avatar
  • 313
0 votes
0 answers
29 views

Tight bounds for expected maximum of k binomial(n,p) IIDs

What is the tightest lower and upper bound for the expected maximum value of k IID Binomial(n, p) random variables I tried to derive it : $$Pr[max \leq C] = (\sum_{i = 0}^C {n \choose i}p^i(1 - p)^i)^...
Goli Emami's user avatar
0 votes
0 answers
23 views

Entropy of a single Hint

Assume that the probability that a woman is above 80 years old is 3 times that of a man. How much information (in bits) do you get if you are given that a 80 year old person is a male? How should I ...
Aris Konstantinidis's user avatar
0 votes
0 answers
20 views

Probability Estimation with Chernoff Bound

Let's say there is an unfair coin with $P[head]=p$. We do not now $p$ but we know that $p \geq a$ for a known $a$. After $n$ trials we get $bn$ heads. Now, we want to estimate $p$ so that $P[|p-b|\...
Aris Konstantinidis's user avatar
1 vote
0 answers
54 views

Bloom filter creating different arrays from two input sets

Assume a bloom filter that is composed of $H = \{H_1, ..., H_k\}$ hash functions, and uniformly maps elements from an input set $X$ to an array $A$ of size $n$. Let $X_1, X_2$ (not same) be two input ...
Aris Konstantinidis's user avatar
1 vote
1 answer
33 views

Distribution maximizing ratio of expected maximum over the mean

I’m looking for a distribution that is non-negative, or has good tail bounds (so non-negative with high probability) and maximizes the ratio between the expected maximum of $n$ iid samples and the ...
Goli Emami's user avatar
2 votes
1 answer
98 views

Question about what exponentially small probability of success means in randomized algorithms

I am reading the book Randomized Algorithms By Motwani and Raghavan, and one of their exercises gives a modification of Karger's Min-Cut algorithm(Both is Monte Carlo) which picks two vertices and ...
DenLilleMand's user avatar
1 vote
1 answer
58 views

Influence of a variable in composition of Boolean functions

Suppose $f$ and $g$ are Boolean functions without a constant term, and where every variable has the same influence. How to show every variable will have the same influence in $f \circ g$? To me it ...
kleinbottle's user avatar
1 vote
1 answer
27 views

Distance bound for convex combination of inputs

Let $f$ be a function of 2 variables. Consider $f\colon X \times Y \rightarrow Z$. Let $P_i$ (for $i=1,\ldots,n$) be $n$ probability distributions on $X$, and let $Q$ be a distribution on $Z$. We ...
Root's user avatar
  • 313
0 votes
1 answer
248 views

how many bits should I expect to flip, if I flip each bit with probability 1/n?

I am trying to work out some analysis for an algorithm I am trying to write, one step of what I am doing require knowing the answer to the above question. I know it might sound a bit simple, but I am ...
user206904's user avatar
1 vote
0 answers
97 views

Hashing for dot products

I've come across this problem that uses hashing to compute dot products (for non-negative vectors). Suppose we are in $d$-dimensional space and $M$ will be our target for our hash. That is we have a ...
grozby's user avatar
  • 21
0 votes
1 answer
94 views

What is conditional probability?

I've been looking online and through a couple youtube videos but I cannot understand how exactly conditional entropy is being applied here. From what I'm understanding is that p(Y=1 | X=1) is 0 ...
MG0310's user avatar
  • 11
1 vote
1 answer
26 views

Observable Markov Model: Expected number of observations

I have a question that asks me "What is the expected number of observations in a state?" with the note: $$\sum^{\infty}_{d=1}d a^{d=1} = \frac{1}{(a-1)^2}\text{ when } |a| < 1$$ Prior to ...
Ellis Thompson's user avatar
0 votes
0 answers
12 views

Algorithmic Complexity of Enqueue and Dequeue of a Special Queue [duplicate]

The Canteen Queue Problem: There is a common canteen for $K$ hostels. Each hostel (co-ed) has some $N_1, N_2,...,N_K$ students. These students line up to pick up their trays in the common canteen, in ...
Kunind Sahu's user avatar
1 vote
0 answers
73 views

Most Likely Number of Winners - Dynamic Programming

You are given a team's win probability for each game on their schedule in the form P[1..n] where P[i] is the likelihood they win game i. Give a dynamic programming algorithm that returns the most ...
Go Blue's user avatar
  • 11
0 votes
2 answers
43 views

Question about Markov Chains

The following question is taken from the book titled "Probability models for Computer Science" written by Sheldon M. Ross. Question: A particle moves along n + 1 vertices that are situated ...
Win_odd Dhamnekar's user avatar
2 votes
1 answer
134 views

Analysis of a calculation of expected number of collisions in hashing

For a formal problem statement, I quote from the text Introduction to Algorithms by Cormen et. al Suppose we use a hash function $h$ to hash $n$ distinct keys into an array $T$ of length $m$. ...
Abhishek Ghosh's user avatar
2 votes
0 answers
58 views

Decision problem solution monte carlo

I have a rather straightforward question for this community (that I am not able to solve). Assume there is a probability of Tom having a bag of candy. If Tom has a bag, he says the truth 4/5 times and ...
DragoonStorm's user avatar
0 votes
1 answer
139 views

Algorithm best compare similarities between two data sets in percentage

I'm trying to create an algorithm that finds the percentage of similarity between two subjects with sets of survey questions. Example: Q1: Do you prefer physically demanding tasks? A1: Nope Maybe Yes -...
syahiruddin's user avatar

1
2 3 4 5
10