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
1answer
63 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 ...
0
votes
1answer
15 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 -...
0
votes
1answer
40 views

Dynamic programming and probability - list of problems

Does anyone have a list of problems where you have to combine dynamic programming with probability?
0
votes
1answer
38 views

How to implement conditional probability distribution on set-valued Random Variables

I'm trying to implement conditional probability distribution when the events of two RVs are sets. If I try to extrapolate concepts from real or categorical variables to sets things become confusing ...
2
votes
0answers
45 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 ...
0
votes
1answer
18 views

Conditional probability in Expectation Maximization (EM)

I've got the following equation: $p(j = 1 | x, \theta) = \frac{p(j=1,x | \theta)}{p(x | \theta)}$ Why does it hold? Or maybe, how do I use Bayes Theorem in this case, i.e. if we do not only have $p(j =...
0
votes
1answer
195 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 ...
0
votes
1answer
93 views

Chebyshev’s inequality problem in one exercises I can't understand if I did it right or not

This is what do I have to solve: Byron Book: Exercise 8.3 chapter 8 Verify the use of Chebyshev’s inequality in (8.6) of Example 8.16. Show that if the population mean is indeed 48.2333 and the ...
1
vote
1answer
27 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 ...
1
vote
0answers
39 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 ...
5
votes
1answer
78 views

Understanding simulated annealing information theoretically

So I recently rediscovered simulated annealing though a path that others seem to be well aware of. I was aware of Metropolis-Hastings as a sampling algorithm that creates a Markov-Chain who's ...
1
vote
1answer
62 views

Show that if $\mathcal{H}$ is PAC learnable in the standard one-oracle model, then $\mathcal{H}$ is PAC learnable in the two-oracle model

This is a question $9.1$ from Understanding Machine Learning Chapter 3. It goes like this: Consider a variant of the PAC model in which there are two example oracles: one that generates positive ...
1
vote
1answer
237 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$) ...
0
votes
1answer
436 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 ...
1
vote
1answer
35 views

Distinguishability given black box access to the distribution

Consider two probability distributions $D$ and $U$, over $n$-bit strings, where $U$ is the uniform distribution. We are not given an explicit description of $D$: we are only given black-box access, ie,...
4
votes
1answer
552 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 ...
1
vote
1answer
25 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 ...
0
votes
1answer
144 views

Transition Function in MDP

I got a question about who and how sets the transation function values in markov decision processes? I mean when some says that an agent, in real world grid, is going to step up by %80 and left/right ...
1
vote
0answers
11 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 ...
0
votes
1answer
121 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 ...
2
votes
1answer
40 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 ...
2
votes
2answers
117 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$...
2
votes
2answers
92 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 ...
1
vote
0answers
22 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 ...
1
vote
0answers
32 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 ...
2
votes
1answer
60 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 ...
1
vote
0answers
8 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: ...
1
vote
1answer
34 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 ...
4
votes
1answer
149 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 ...
2
votes
2answers
37 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, ...
0
votes
1answer
20 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 ...
4
votes
1answer
80 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\\ ...
0
votes
0answers
22 views

Simple Bayesian Question

I have the following Bayesian Network. I have worked out the following: P(H) = P(H|D) + P(H|¬D) = 0.5 + 0.1 = 0.6 P(D|H) = (D)∗(P(H|D) +P(H|¬D)) = 0.3∗(0.5 + 0.1) = 0.18 How do I compute the ...
1
vote
0answers
40 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=...
0
votes
0answers
134 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 (...
1
vote
0answers
27 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 ...
0
votes
1answer
33 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 ...
2
votes
1answer
19 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 (...
1
vote
0answers
14 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 ...
3
votes
2answers
164 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 ...
0
votes
0answers
19 views

Problem on probability given frame sizes and their error correction probabilities in a wireless system

I am stuck trying to solve the following question for a while Bit error rate after demodulation in an wireless system = 1.0e-03. The system has 4 possible frame sizes – 48 bytes, 96 bytes, 72 bytes ...
0
votes
1answer
115 views

what is the relationship between entropy and variance?

Consider a simple Bernoulli variable X X = 1 with probability p X = 0 with probability (1-p) The variance is simply p(1-p). The ...
1
vote
1answer
34 views

Computational indistinguishability for any distribution using a Chernoff bound

I had a question about a general statement regarding finding a computationally indistinguishable distribution given any distribution, observed (in the third paragraph of Section 11, page 31) here. ...
1
vote
1answer
48 views

How to show independence and uniform distribution of hash codes from k-wise independent hash functions?

Most definitions of a $k$-wise independent family of hash functions I have encountered state that a family $H$ of hash functions from $D$ to $R$ is k-wise independent if for all distinct $x_1, x_2,\...
2
votes
0answers
39 views

Whether there exists a probabilistic automaton satisfying $\Pr \{ x \in L\}=\frac{\Pr \{ x \in L_1\}}{\Pr \{ x \in L_1\}+\Pr \{ x \in L_2\}}$

Suppose that there are two probabilistic automata $A_1$ and $A_2$ with a same finite alphabet $\Sigma$. The languages of them are $\mathcal{L}_{1} \subseteq \Sigma^*$ and $\mathcal{L}_{2} \subseteq \...
1
vote
0answers
70 views

kth smallest element using Randomized select

I have recently started studying Randomized algorithms on my own. I am refering to Rajiv motwani - randomized algorithms book. Objective - find kth smallest element using radomized select in $O(n^\...
4
votes
3answers
803 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 "...
1
vote
1answer
105 views

Is there an algorithm for random sampling from a priority queue with probability proportional to priority?

Suppose I want to randomly sample from a large set of items, each of which has a "score". I want my probability of sampling to be proportional to the score. One simple way to achieve this ...
0
votes
0answers
91 views

Fast factorial computation

I'm trying to solve this problem - https://codeforces.com/problemset/problem/711/E I've already found and proved that the result is equal to: $$ 1 - \frac{2^n (2^n - 1) \cdots (2 ^ n - k + 1)}{2^{...
0
votes
1answer
41 views

The probability that a person succeeds to pick the longest stick from a randomly ordered n sticks of distinct lengths following the optimal strategy?

To begin with, consider two persons(Px and Py) are playing a game. Px is the organiser of the game who has n sticks of distinct lengths and displaying them one by one to Py in a random order, with ...

1
2 3 4 5
9