Questions tagged [probability-theory]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
85 views

Average solutions in infinite search tree

I have the following problem: Consider a balanced infinite search tree with branching number $κ$. Consider a search problem with solutions which may be located at any node of the tree. The ...
0
votes
0answers
56 views

How are Probability and Non Determinism Related ? Alternatives to handle Non determinism?

I have been thinking about Non-determinism in any kind of state machine. Since I work on machine learning, I tend to think that probability is a means of handling non-determinism. Instead of ...
2
votes
0answers
31 views

Why can optimality be preserved when inserting a new conjunct into an optimally ordered conjunction of conditions? [duplicate]

In a programming language with short-circuiting, a conjunction of N independent conditions has the following expected cost: where: ...
2
votes
2answers
189 views

The optimal way to reverse engineer a binary classification problem

I am not sure if this question is more suitable for CS, theoretical CS or math so feel free to improve the description and migrate it. In a scenario very similar to popular binary classification ...
1
vote
0answers
463 views

How to choose value of additive smoothing in naive Bayes and why a higher value gives bad accuracy?

In Naive Bayes we often do additive smoothing as a fail safe. Consider the following expression: Lets say $$P(X_i) = \frac{count(X_i) + \alpha}{\sum_i^n count(X_i) + \alpha*total\_size}$$ How to tune ...
1
vote
0answers
71 views

Game with Random Digits (Markov Chain / Coupling)

I've been self-studying Markov Chains and came across a problem online here: http://websites.math.leidenuniv.nl/probability/lecturenotes/CouplingLectures.pdf I'm not asking for anything too formal (I'...
2
votes
1answer
185 views

Confuse on using bucket number to replace hashing multiple times in hyperloglog explanation

In this blog the author states that the following So we now have a rather poor estimate of the number of values in the dataset based on bit patterns. How can we improve on it? One ...
0
votes
0answers
137 views

Probability in Dynamic frame aloha

If I've RFID Collision Arbitration System that is based on multi-frame dynamic frame ALOHA. How can compute the probability of the average tag resolution $L_n$? ,$P_s$ is probability for packet ...
3
votes
2answers
60 views

Are typical sets larger, when information is messier?

Let $0\le q<p\le \frac{1}{2}$, and let $P,Q$ be two Bernoulli Random Variables such that: $$Pr[P=1]=p ; Pr[P=0]=1-p$$ and $$Pr[Q=1]=q ; Pr[Q=0]=1-q$$ My question: Does it follow that, for any $\...
3
votes
1answer
199 views

Probability of k-connectedness for a random graph with given degree sequence

For a degree sequence $(d_1,\ldots, d_n)$ with $\min d_i \geq k$ pick a graph with that degree sequence uniformly at random. What's the probability that the graph is k-connected? I know that for ...
1
vote
1answer
68 views

Probabilistic analysis of finding 2nd largest value in vector

Given the following algorithm for finding the second largest element in a vector: ...
0
votes
1answer
361 views

Equivalence of machine $M$ in $BPP$ and $EXP$

Ok, the proof is clear. But, if we prove that $BPP \subseteq EXP$ we should show that for every machin in $BPP$ there exists equivalent machine in $EXP$. I cannot see how the $EXP$-machine is ...
2
votes
1answer
103 views

Randomized BST height analysis : How $Z_{n,i}$ and $Y_{k-1}$ are independent?

I am referring to this video https://www.youtube.com/watch?v=vgELyZ9LXX4 at 1:08:39 . $n$ : number of nodes in the tree $Z_{n,k}$ : Indicator random variable that activates when rank of the root ...
0
votes
0answers
36 views

Probability that the word is of language using N-Grams

Some programm should allow users to identify the word language probability. All i have is some statistics - the frequency of using bigrams and ...
2
votes
1answer
58 views

Bound covariance of two discrete random variables

Let $X,Y$ be two random variables over a discrete probability space, such that $X \in [0,1]$ and $Y \in [0,1]$. I want to prove that $$ |\text{Cov}[X,Y]| \leq \sqrt{0.5 \; I[X,Y]}$$ where $I[]$ is ...
4
votes
1answer
122 views

Chernoff bound when we only have a lower bound of expecation

This question: Chernoff bound when we only have upper bound of expectation is similar, but for an upper bound of expectation. The standard Chernoff bound says that is $X$ is a sum of 0/1 random ...
1
vote
1answer
200 views

Probability that all indices divisible by 100 in a hash table with linear probing are occupied

I am trying to solve this question on Sedgewick's and Wayne's Algorithms book: Suppose that a linear-probing table of size 10^6 is half full, with occupied positions chosen at random. Estimate the ...
0
votes
0answers
170 views

Finding the expected total number of comparison for a Randomized Quick Sort

Let A = {2, 8, 11, 3, 12, 7, 10, 4, 15} Want to find $E_4$. Little unsure how to do this question. Would this be similar to finding the probability of the number of comparison 2/(j -i +1)?
0
votes
1answer
129 views

Limit on table size - perfect hashing

Let us define a "root universal family" as a family of hash function which for every two items $k_i,k_j$ the probability $P(h(k_i)=h(k_j)) \le \frac{1}{\sqrt m}$ where $m$ is the size of the table. ...
22
votes
2answers
7k views

Why is adding log probabilities faster than multiplying probabilities?

To frame the question, in computer science often we want to calculate the product of several probabilities: P(A,B,C) = P(A) * P(B) * P(C) The simplest approach ...
1
vote
1answer
62 views

Estimating probability from generative model

Assume that we have access to a generative model $G$, that takes as input a state-action pair $(s,a)$ and outputs a sample consisting of a successor state-observation pair $(s',o)$, that is, $(s',o)\...
2
votes
0answers
115 views

What would be the probabilty of a randomly generated tree to be a Red-Black Tree

The question is not related to the homework I was working on a homework, and the specification was to generate a random tree with n elements(n being in the thousands for the assignment) and asked me ...
1
vote
1answer
258 views

Vertical sticks challenge explanation

This is a question based on this one I've also tried this problem but I can't seem to understand Henry's solution to it. Why is the average distance between the sticks $(n+1) / (k+1)$ and not $n/ k$...
1
vote
1answer
70 views

Can we recognize the difference of two strings of $2^n$ length using polynomial size strings?

Is it possible to transform binary strings of length $2^n$ to $n^c$ binary strings of sized $n^d$ such that $$\forall s_1,s_2 \; \exists i \in \{1,\cdots,n^c\} \; f_i(s_1)\neq f_i(s_2),$$ Where two ...
1
vote
0answers
160 views

Probability of finding the maximum element in a heap

You are given a minimum heap, with probability going to left is 50% and going to right is 50%. What is the probability that You will land up on a maximum element in the heap? For this scenario since ...
1
vote
1answer
257 views

Higher order empirical entropy is not the entropy of the empirical distribution?

Basically, the problem is that I always thought that the (unnormalized) $k$th order empirical entropy $n\cdot H_k(x)$ (see "Backround" at the end of this post for more information) for a given string $...
0
votes
1answer
56 views

Prove a language $A_{PTM}$ is not BPP-Complete

I am trying to prove that there are a language is not BPP-Complete. There are a couple of examples online, but they are not the best examples and are a bit complicated. I spoke with one of my computer ...
1
vote
1answer
105 views

Using amplification lemma to decrease error probability gives 0 as divisor

I am attempting to work through an example of how to select an error bound, and then determine the number of simulations necessary by the amplification lemma to obtain the desired error bound. I have ...
1
vote
0answers
24 views

Minimizing $E_{out}$ theoretically in linear regression

Related to linear regression with noise I've been given the following functional, depending on the function $h$: $$ E_{out}(h) = \int \int (h(x)-y)^2 dx dy$$ I want to prove that the function that ...
0
votes
1answer
292 views

Calculate joint entropy of a Hamming Code over a Binary Symmetric Channel?

I have a normal (7,4,3) Hamming Code over GF(2) and a parity check matrix for it (not posted, because I don't think it's involved). I have a set X of 4 bit source vectors called x. They all have ...
0
votes
0answers
58 views

What is the probability distribution of arrival times in a distributed system?

I'm going to simulate an asynchronous distributed system. In a distributed system, when a node sends a message, after $\Delta t$ seconds the message reaches to its destination. My Question: What is ...
3
votes
2answers
1k views

Sorting in a probabilistic order

Given a list of real numbers $p_1, \dots, p_n$, I am looking for a most efficient algorithm to sort this list in a "probabilistic ascending order", meaning that $p_i < p_j$ implies that it is ...
3
votes
1answer
122 views

Finding the dichotomy that maximizes information gain for a classifier?

Suppose that $\Omega$ is a finite probability space,with measure $P$ (we can take $P$ uniform). Let $C \in \{\pm 1 \}$ be a random variable on $\Omega$, the classifier. Let $$H(C) = H(C, \Omega, P) = ...
1
vote
1answer
64 views

Expected Number of Trials

I have an algorithm problem that I want to share with you and I want to get some idea how can I solve it. Problem statement: You have to reach th Nth floor of a building by using a particular ...
3
votes
1answer
65 views

Hidden Markov Model initial probability reestimate: Why $\pi^*_i = \gamma_i(1)$ instead of $\pi^*_i = \frac{\gamma_i(1)}{\sum_{j = 1}^N \gamma_j(1)}$

In the sources I consulted it states that in the Baum Welch algorithm the reestimate of the initial probability of state $i$ of the HMM is $\pi^*_i = \gamma_i(1)$. But $\gamma_i(t)$ is the probability ...
1
vote
1answer
84 views

Most probable value of randomized procedure output

Let $n, m \in \mathbb{N}^{+}$. Let $\mathsf{rand}$ be a procedure which returns some random $x \in \{0, 1, \ldots, m - 1\}$ with a flat probability distribution. I have the following procedure: ...
-1
votes
1answer
190 views

Help in understanding calculation of hash collision from a document

UPDATE In an earlier question of mine asked here : https://math.stackexchange.com/questions/2206095/beginner-level-understanding-concept-on-how-to-derive-probability-of-hash-collis , I got the answer ...
3
votes
3answers
254 views

Confusion about the definition of the average-case running time of algorithms

In this lecture note, The average-case running time is defined by the expected value, over all inputs $X$ of a certain size, of the algorithm's running time for $X$: $$T_{\text{average-case}}(n) ...
0
votes
1answer
166 views

Reachability queries on uncertain graphs

We have an uncertain graph $G$ where each edge $(u,v)$ exists with a probability $p_{(u,v)} \in (0, 1]$. We want to assign a score in $[0, 1]$ to each pair of vertices $u$ and $v$ which represents the ...
1
vote
0answers
22 views

How to derive an algorithms that generates check sums [closed]

Column S contains the check sums of the values given in columns R and Xc. Does anyone here have an idea about how to find the corresponding algorithm to calculate the check sums? Thanks in advance <...
1
vote
0answers
182 views

Calculate expected values of "Craps Game" with the help of Prism Model Checker

I have modelled the craps game (https://en.wikipedia.org/wiki/Craps#Rules_of_play) as a dtmc with the prism model checker: ...
3
votes
1answer
83 views

Sampling from a set of numbers with a fixed sum

Let $s = \{x_1, x_2, \ldots, x_n\}$ be a set of $n$ random non-negative integers where $\sum_i x_i = n$. And let $\{y_1, y_2, \ldots, y_{\sqrt{n}}\}$ denote a subset of size $\sqrt{n}$ of $s$, chosen ...
1
vote
0answers
79 views

Approximate conditional entropy

Given a set of random variables $X = \{x_1, x_2, \dots, x_n\}$. If the conditional entropy for all $Y \subset X - \{X_i\}$ where $|Y| \leq 5$. How to approximate conditional entropy when $|Y| = 10$ ...
0
votes
1answer
2k views

How would you prove a family of functions is universal?

A set of functions from a universe U of keys to n buckets is universal if for every pair of keys in U, say x and y, such that x != y, the probability of h(x) = h(y) is less than or equal to 1/n, for a ...
1
vote
1answer
42 views

"Learning occupancy grid maps with forward sensor models, S.Thurn,2008" a formula that is difficult to overcome

I am reviewing the document" Learning occupancy grid maps with forward sensor models, S.Thrun, 2008" (http://faculty.iiit.ac.in/~mkrishna/ThrunOccGrid.pdf) i am really confused about formula (26), ...
2
votes
1answer
526 views

How can Karger's algorithm (and other randomized algorithms) be used in practice?

Suppose I am given the following problem (the source is here): Disconnect two nodes in a graph by removing minimum number of edges. I would apply Karger's min-cut algorithm. But how can I ...
2
votes
0answers
62 views

Box labelling game

I have a box of stickers. It contains $n$ stickers. Each sticker is labelled with a different number from $\mathbb{Z}$. I have infinite supply of boxes. Box labelling game: I pick a random sticker ...
1
vote
0answers
238 views

EM-algorithm for categorical hidden variables

I have the following model: Let's say two indepentent weighted six-sided dice $X$ and $Y$ with unknown probabilities (i.e. probability of 1 is unkown etc) and they have not necessarily the same ...
3
votes
1answer
223 views

Random Walk on the Integer Line

Suppose we are doing a random walk on the infinite integer line and that we take $2n$ total steps. At every step of this walk, the position of the walker is an integer point on this line. For the next ...
0
votes
1answer
119 views

Reading CLRS analysis of hashing with chaining

I'm currently reading an analysis hashing with chaining, and it goes over two examples: In the first, the search is unsuccessful; no element in the table has key k. In the second, the search ...

1
3 4
5
6 7
9