Questions tagged [probability-theory]

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

Filter by
Sorted by
Tagged with
2 votes
1 answer
63 views

Pseudo random permutation of a very large number of elements

Consider a file $\textbf{F}$ containing $n$ distinct elements, located on a hard drive. Given the large size of $n$, it's not feasible to load the entire file $\textbf{F}$ into main memory. Assuming ...
JPF's user avatar
  • 121
0 votes
0 answers
17 views

Analysis of Simon's Algorithm: Probability Expression for Matching Queries

The Simon's problem is that, given a function $f:\{0,1\}^n\to\{0,1\}^n$ such that, for all $x,y\{0,1\}^n$ t satisfies $$ f(x)=f(y)\text{ iff }x=y\oplus s $$ where $s\in \{0,1\}^n$, and the Simon's ...
Sooraj S's user avatar
  • 139
3 votes
3 answers
521 views

Probability of overflow in a summation of fixed-size signed integers

How can I estimate the probability that the sum $S_n$ of $n$ uniform random 48-bit signed integers overflows a 64-bit signed integer? Edit: the overflow can occur at any step, not only on the final ...
Aristide's user avatar
  • 323
0 votes
0 answers
56 views

Growth of the average numbers of peaks for the permutations of $n$ sticks

There are $n$ sticks of lengths $1$ to $n$ in a row. Upon permuting them randomly, we may calculate the average number of peaks viewed from left. A peak is a stick such that all sticks to its left are ...
Zirui Wang's user avatar
1 vote
0 answers
23 views

Clustering 2D points with flavour

Problem Description I have two sets of 2D points with flavours: Noisy points $$p_i = (x_i, y_i, f_i) : p_i \in N : |N|\approx 10^8 $$ and true points $$p_{t_i} = (x_{t_i}, y_{t_i}, f_{t_i}) : p_{t_i} \...
Emil Jansson's user avatar
0 votes
0 answers
30 views

If $NP \subseteq BPP$ then $NP = RP$. Confusion on the probability that M gives at least one wrong answer in BPP in n invocations

I was looking at the proof of if $NP \subseteq BPP$ then $NP = RP$ here. At the end of the proof the author states: "Note that if $M$ always gives correct answers on calls to $M$, then when $\phi$...
venturr988's user avatar
0 votes
0 answers
33 views

A probabilistic data structure based on flipping bits with probability $\frac{1}{2^x}$ for counting

How does this data structure work and what is its application? ...
Mason Rashford's user avatar
2 votes
2 answers
180 views

Analysis of QuickSort Expected Time Complexity: Without Counting the Number of Comparisons

While reading CLRS (4th ed.) regarding the analysis of the expected time for QuickSort, I encountered an alternative approach. The analysis involves the following steps: Given an array of size $n$, ...
Mason Rashford's user avatar
1 vote
0 answers
31 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,632
2 votes
1 answer
104 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 ...
Ferran Gonzalez's user avatar
0 votes
1 answer
27 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
53 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
23 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
76 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
77 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
46 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
  • 165
2 votes
1 answer
138 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
69 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
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
  • 149
1 vote
1 answer
132 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
105 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
40 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
22 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
53 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
87 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
755 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
45 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
27 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
106 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
74 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
59 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
104 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
31 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
24 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
28 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
60 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
121 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
69 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
28 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
276 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
130 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
134 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
40 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
13 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
80 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

1
2 3 4 5
10