Questions tagged [probability-theory]

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

484 questions
Filter by
Sorted by
Tagged with
21 views

Find effective memory access time in a system with TLB as well as physical address cache

The problem statement: I have a simple paging system with a TLB and a Physical Address Cache. Here's the flow: CPU generates logical address=(p,d) Given "p", CPU seeks in its TLB cache if ...
103 views

Expected Entropy of the Empirical Distribution

Given a distribution on $n$ outcomes where outcome $i$ has probability $p_i$, the Shannon entropy of the distribution is defined as $- \sum_{i = 1}^n p_i \cdot \log_2 p_i$. Let's suppose I sample from ...
• 141
19 views

Proof that the hopfield network decreases the energy for simultaneous updates?

A hopfield network is given by an $N\times N$ matrix $w$ satisfying $w_{ij}=w_{ji}$ and operates on $N$-dimensional bitstrings, which we represent as $\{-1,1\}$. If a hopfield network updates each ...
• 4,012
52 views

Information content of a real number

Suppose I have a sequence of 5 IID Bernoulli variables, with probability of having value 1 being 0.5. If we observe an instance of the sequence, the information content would be 5 bits, as each ...
69 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 ...
• 121
19 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 ...
• 139
525 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 ...
• 323
60 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 ...
• 990
1 vote
25 views

1 vote
61 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$, ...
• 113
1 vote
105 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 ...
• 23
1 vote
21 views

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 ...
29 views

• 21