# Questions tagged [probability-theory]

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

341 questions
Filter by
Sorted by
Tagged with
79 views

### Simulating continuous time semi-Markov state machine and changing transition probability on the fly

The problem that I'm trying to solve (well, I think that I almost did, but need a review from someone more experienced) is about changing probability of the transition for semi-Markov state machine ...
46 views

### Proving simple bound on coupon collector

I came across this paper which gives bounds on coupon colloector problem. Page 451 contains a table where reference to U1 is given as 'folklore'. I presume this is trivial to follow from the ...
50 views

### Infer probabilities, for concatenation of words

Fix an alphabet $\Sigma$, and a set of words, $W = \{w_1,\dots,w_n\} \subseteq \Sigma^*$. I have a randomized model that works like this: Alice generates a random sequence of words, using some ...
68 views

### Maximum entropy probability distribution among Solomonoff priors

If we take Solomonoff's prior $m$, defined here and normalize it we get a probability mass function on all finite words. But, the pmf isn't completely determined until we fix a universal Turing ...
178 views

### Collisions in independent hashing

Let $H$ be a $s$-wise independent family of hash functions from $\{1,\ldots,M\}$ to $\{1,\ldots,N\}$. It is easy to bound one collision, but are there good bounds for muliple collision ?
514 views

### How would you implement truly random hash functions in practice?

Suppose that $[U] = [0,...,U-1]$ is the universe from which all elements will be taken, and $A$ a hash table of size $m$. A hash function $h:[U]\rightarrow[m]$ is truly random if For any set of ...
252 views

### Minimal number of attempts at a multiple choice exam needed in order to pass, without any prior knowledge

A test is consisted of $N$ multiple choice questions, each has $k$ possible answers. A test solution is the sequence of answers $S\in[k]^N$. Given is a black box which receives a solution as input ...
74 views

### Probabilistic Analysis in real time network : Error in data and feedback channel. Two users communication

I'm studying probabilistic analysis in real time network. We have learned how many attempts in average are required to transmit a packet when there is no error on the feedback channel. With no error ...
137 views

679 views

66 views

### Distribution of Ones in a Psuedorandom Sequence

Let S be a string in the set (0,1) produced by taking the AND of the output of two maximal length linear feedback shift registers of large period (say 128 bits). It's easy to see from the truth table ...
3k views

### What are Markov chains?

I'm currently reading some papers about Markov chain lumping and I'm failing to see the difference between a Markov chain and a plain directed weighted graph. For example in the article Optimal state-...
297 views

### Markov Chain w/ non-stochastic matrix

I've come across a problem which at first appeared to be a markov process however the transition matrix of the graph is non-stochastic. That is, the probabilities among edges leaving a node do not sum ...
286 views

### Random Graph is a good expander

If a (n,d) random graph is a n-vertex graph defined as : Choose d random permutations $\pi_1 \ldots \pi_d$, from [n] to [n]. Take edge (u,v) if $v = \pi_i(u)$ for some i. I am trying to prove that, ...
755 views

### Naive Bayes MapReduce

I have the following question to answer in a MapReduce assignment sheet The Naive Bayes classifier is a widely-used tool for analyzing data. Consider a data set that has $n$ data items, each of ...
7k views

### How to calculate probability of packet loss and drop rate?

In a queuing system (M/M/1) with a finite packet capacity $z$, how do you determine the probability of packet loss if we assume that packets are dropped when the system is full? Packets arrive with a ...
195 views

### Why is the most probable assignment for all variables in MRFs called MAP assignment?

I am new to graphical model, especially Markov Random Fields. I have a question about MAP assignment. Let say we have the graph structure and all the potential functions. MAP assignment in MRFs is ...
376 views

### Choosing a subset of binary variables to maximize the sum of the highest $K$

Consider the following problem: Input: integers $n > m > k$; $n$ numbers $0 \leq p_1, \ldots, p_n \leq 1$; $n$ numbers $r_1, \ldots, r_n$ where ($r_i \geq 0$). Let $X_1,\dots,X_n$ be $n$ ...
608 views

### Understanding polynomial equality testing using randomized algorithms

A file is downloaded from a server and is represented as $a = \{0, 1\}^n$. The server has that file as $b = \{0, 1\}^n$. We want to ensure a degree of certainty that $a=b$, using a randomized ...
97 views

### Optimal wagering to minimize expected time to reach a target payoff

Suppose for simplicity we start off with starting amount $S = 1$ and we wish to reach target amount $T$. To do this we sequentially wager a certain amount and then win that amount with probability $p$ ...
216 views

### Anagrams solver based on transitions probability

I have an English dictionary (text file) and the frequency of 2-grams, 3-grams and 4-grams as the beginning of each word. I need to write an algorithm that, with a given word, calculates the possible ...
41 views

### Using all the entropy in an biased bit

Suppose we have $n$ bits of random-looking data, and we want to encode it in such a way that instead of 1/2 the bits being 1's, we have (say) 3/4 the bits being 1's. The entropy of each bit in the new ...
642 views

### Why analysis of Aloha protocol uses Poisson distribution?

Pretty much in all of the analysis of the Aloha protocol that I read, it is assumed that the distribution of packet arrivals is Poisson. What is the rationale behind it? Isn't it actually binomial ...
105 views

### Calculating the number of unique BST generatable from n keys, why is my number so large

I want to find the number of distinct BSTs I can get with 3 unique keys (i.e. 1, 2, 3) Here's my solution: In case 1, we have each node have possibility, 3, 2, 1, respectively, so 3*2*1 = 6 ways In ...
189 views

### PRNG bad seeding and von Neumann unbiasing

Large period PRNGs such as Mersenne Twister require good seeding otherwise the initial output in the sequence may not seem to be high-quality, at least for the first few words (and in the way that is ...