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
50 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 ...
user avatar
0 votes
1 answer
22 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 &...
user avatar
1 vote
1 answer
39 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$, ...
user avatar
1 vote
1 answer
85 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 ...
user avatar
  • 23
1 vote
1 answer
20 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)\...
user avatar
  • 313
0 votes
0 answers
28 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)^...
user avatar
0 votes
0 answers
21 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 ...
user avatar
0 votes
0 answers
16 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|\...
user avatar
1 vote
0 answers
36 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 ...
user avatar
1 vote
1 answer
31 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 ...
user avatar
2 votes
1 answer
36 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 ...
user avatar
1 vote
1 answer
39 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 ...
user avatar
1 vote
1 answer
21 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 ...
user avatar
  • 313
0 votes
1 answer
152 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 ...
user avatar
1 vote
0 answers
28 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 ...
user avatar
  • 21
0 votes
1 answer
31 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 ...
user avatar
  • 11
1 vote
1 answer
19 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 ...
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 ...
user avatar
1 vote
0 answers
46 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 ...
user avatar
  • 11
0 votes
2 answers
42 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 ...
user avatar
2 votes
1 answer
56 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$. ...
user avatar
2 votes
0 answers
53 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 ...
user avatar
0 votes
0 answers
19 views

Computer network graph design

In the following question, we need to suggest a graph design and a routing algorithm. Routing from $A$ to $B$ is done by returning an edge sequence in the graph that will lead us from $A$ to $B$ ...
user avatar
  • 103
0 votes
1 answer
37 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 -...
user avatar
2 votes
0 answers
58 views

questions about queuing delay

I am learning computer network, and confused by the queuing delay. In my textbook, it says that when La/R approaches 1, and with random inter-arrival times, then the average queuing delay is closer to ...
user avatar
  • 19
0 votes
1 answer
211 views

If the probability of frame being lost is $P.$ Then, calculate the mean no. of transmission for the frame to make it success$.$ [closed]

Here the probability of frame being lost is $P.$ So the probability of frame reaching safely would be $(1-P).$ Now lets consider that the frame will reach safely in $k$-th transmission. That means ...
user avatar
  • 1
1 vote
0 answers
45 views

Is quantum computing a serious usable instrument for the IT industry?

Following this latest and very exciting research object I can't find till now a usable computer in that style. I would like to call actual quantum computing by the topic "researching of quantum ...
user avatar
1 vote
1 answer
29 views

Why does random noise in recurring task periods result in uniform period offsets?

I have a recurring task which finished just now. I schedule it to run every ten minutes; the task will reoccur $10n$ minutes from now for all positive $n$. If instead I choose 50/50 between ten ...
user avatar
2 votes
1 answer
55 views

Why is $\mathcal{D}^m(\{S:L_{(\mathcal{D},f)}(A(S))\gt \epsilon\})\leq \mathcal{D}^m\left(\bigcup^4_{i=1}F_i\right)$ true?

I am studying the book "Understanding Machine Learning: From Theory to Algorithms". I am struggling to understand the solution to exercise 3 (2) on page 41. Exercise: An axis aligned ...
user avatar
1 vote
0 answers
13 views

Distributed Graph Consensus to fit a distribution?

$G$ is a strongly connected graph with nodes $V$ and edges $E$. Each node $v_i$ receives a sample $x_i$ from a Gaussian $\mathcal{N}(\mu,\sigma^2)$ with unknown mean and variance. The objective is for ...
user avatar
  • 453
2 votes
1 answer
151 views

Given only the expected runtime of an algorithm, what can Markov's inequality tell us about its worst-case runtime?

The following is exercise 3.8 from the first edition of Mitzenmacher and Upfal's Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Suppose that we have an algorithm that ...
user avatar
  • 303
2 votes
2 answers
163 views

Question about "with high probability"

An event that occurs with high probability is one whose probability depends on a certain number $n$ and goes to $1$ as $n$ goes to infinity, i.e. it can be made as close as desired to $1$ by making $n$...
user avatar
3 votes
2 answers
144 views

Satisfiable CNFs where each clause contains logarithmically many different literals

Studying for my finals in Complexity theory. This question comes up in different variants and it requires to use probability. A side note before, to be more clear: A CNF clause consists of $n$ clauses ...
user avatar
  • 209
1 vote
1 answer
39 views

How long a graph random walk takes to hit every vertex?

I have a simply connected graph $G$. I start at a uniformly randomly chosen vertex, and from there, randomly walk through the graph by choosing a random edge to follow at each step. On average, how ...
user avatar
  • 453
1 vote
0 answers
35 views

Computing a threshold function

Let $f$ be any function from $\{0, 1\}^{n}$ to $\{-1, 1\}$. For a given $f$, let us define another function $g_f$ as \begin{equation} g_f(x) = \sum_{x \in \{0, 1\}^{n}} f(x). \end{equation} Let us be ...
user avatar
  • 219
2 votes
1 answer
111 views

Deriving a lower bound on the conditional entropy, conditioned on an event

I came across Lemma 19 in Certifying Equality With Limited Interaction, which states the following for jointly distributed random variables $Z$, $W$, where $Z$ takes values in $\{0,1\}^n$, and some ...
user avatar
1 vote
0 answers
10 views

expected value of map generate algorithm

I designed a program to create a map in my 2D game program. And I have three questions... algorithm: step1: ...
user avatar
1 vote
1 answer
35 views

A small question about generating random variable with geometric distribution

I was reading Professor Knuth's Volume 2 (page 136) about generating a geometrically distributed random variable $N$ (with $p$ as the probability of success). Basically, the idea is to generate a ...
user avatar
  • 285
4 votes
1 answer
171 views

Count Sketch probability bound

I have been reading up on the Count Sketch algorithm, and I stumpled upon the Count Sketh algorithm explained in section 5 of https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf. Then, I ...
user avatar
2 votes
2 answers
70 views

Quicksort: Probability of an element being compared to fewer than $k$ pivot elements

Assume we want to use quicksort on some array $s$ with length $n$ consisting of only $n$ distinct elements. Let $S_{(1)},S_{(2)},\dots,S_{(n)}$ be the sorted order of the elements in $S$. Furthermore, ...
user avatar
0 votes
1 answer
48 views

Dynamic programming and probability - list of problems

Does anyone have a list of problems where you have to combine dynamic programming with probability?
user avatar
  • 171
4 votes
1 answer
117 views

Probability of reaching a state in asymmetric random walk

Consider the following random walk: Namely, if $S_i$ is the state at time $i$, then $\Pr(S_{i+1}=1|S_i=0)=1$, and for every $s>0$ we have $$S_{i+1}|S_i=s= \begin{cases} s+1 & \text{w.p. }1-p\\ ...
user avatar
  • 199
0 votes
1 answer
107 views

How to sample Bivariate Normal Distribution with Accept reject method

I have to write python code in jupyter due to sampling bivariate normal distribution with 3 sampling methods: Prior Sampling Gibbs Sampling Rejection Sampling I have done the first two samplings and ...
user avatar
1 vote
0 answers
76 views

Concentration inequality of sum of geometric random variables taken to a power

Let $X_1, \cdots, X_n$ be $n$ independent geometric random variables with success probability parameter $p = 1/2$, where $X_i = j$ means it took $j$ trials to get the first success. Let $S_d = \sum_{i=...
user avatar
  • 443
0 votes
0 answers
288 views

Average number of comparisons for a successful search of a prime number in a binary search tree

A binary search tree is constructed by inserting the following value sequentially: $$3, 9, 1, 6, 8, 7, 10, 4, 2, 5$$ Let $p_v$ be the probability to search for the value $v$ in the binary search tree (...
user avatar
1 vote
0 answers
31 views

Why does attempting to estimate the entropy of text by randomly choosing chars in it and counting how often they are equal give wildly wrong results?

Why does attempting to estimate the entropy of a string, by randomly choosing pairs of (not necessarily adjacent) characters in it, and counting how often the selected characters in the pairs are ...
user avatar
0 votes
1 answer
34 views

Distribution of $(X_1,X_2)$ if $X_1\pm X_2$ are two independent $N(1,4)$

$X_1+X_2$ and $X_1-X_2 $ are i.i.d. $N(1,4)$. What is the distribution of $X = (X_1,X_2)^T$? I know i.i.d. is an independent and identically distributed random variable but I don't know how to use it ...
user avatar
2 votes
1 answer
25 views

How Data Compression relates to Estimating Distribution?

I recently read this paper Mahoney, 1999. And encountered this line, optimal compression of a probabilistic language L with unknown distribution (such as English) using an estimated distribution M (...
user avatar
  • 131
1 vote
0 answers
17 views

Degree of regularity of a Markov chain

A Markov chain with transition matrix $P$ is termed regular if for some $n$, all entries of $P^n$ are positive. Is there a known notion of degree of regularity quantified in terms of how soon all ...
user avatar
  • 183
3 votes
2 answers
174 views

Proving a certain hypothesis class on a given distribution is not learnable

I had this question in Learning theory, but it's really just a question in probability theory to be honest, so I'm gonna try to rephrase it in a way that really emphasizes what I was trying to do to ...
user avatar
  • 317

1
2 3 4 5
10