1
vote
0answers
13 views

Choosing between increasing sample size and testing for failures

I have a large set of data that shows things (let's call them cars) have performed over the years against various different tests (say, crash test, braking, gas mileage, etc.). What I'm doing is ...
0
votes
0answers
59 views

What's the probability that Tom's bag will weigh more than Sally's?

Assume all cantelopes take on an integer weight in ounces from 0 (an extremely light apple) to 1000 inclusive. Tom has 50 cantelopes of weights $\{T_i: 1\leq i\leq 50\}$. Sally also has 50 ...
13
votes
4answers
178 views

perfect play in 1-dimensional Minesweeper

In 1-dimensional Minesweeper with a known number of mines (that are distributed uniformly), is there a known somewhat-simple strategy for perfect play? When there are n cells and [0 or n-1 ...
1
vote
2answers
30 views

Randomized Algorithm

I asked this question earlier but I wanted to change the problem. A band has tour sites A, B, and C. They get paid every time they play at each tour site, specifically: ...
0
votes
0answers
18 views

Computing standard errors using EM algorithm

I'm applying the EM algorithm to a hidden markov chain (the $\mathbf{Z}=\{Z_1,...,Z_n\}$ variable), with observations(the $\mathbf{Y}=\{Y_0,...,Y_n\}$ variable) dependent not only on the hidden markov ...
3
votes
1answer
87 views

Expected Value of this function

Let’s consider a random permutation p1, p2, …, pN of numbers 1, 2, …, N and Function F is calculated as F=(X[2]+…+X[N-1])^K, where ...
1
vote
0answers
16 views

Determining the optimally scoring move on a probabilistically represented 2D grid in real time

I'm posting this to StackOverflow, cstheory.stackexchange.com, and math.stackexchange.com because I'm not really sure where it fits best. I hope that's OK. I have a 2D grid (size varies per map, ...
0
votes
1answer
28 views

Generating Random Serialnumber with least similarity

I want to generate 16-digits hexadecimal serial-number like: F204-8BE2-17A2-CFF3. (This pattern give me 16^16 distinct serial-number But I don't need all of them as I describe below) I need an idea ...
0
votes
0answers
18 views

Efficient algorithm for point estimation of a dependent random variable

Suppose $X$ is a normal-distributed random variable and $f$ is a known smooth function (possibly quite complicated, with many oscillations). Let $p(y)$ be the pdf of the dependent random variable $Y = ...
0
votes
1answer
23 views

Conditional probability algorithm problem

Byteasar has just arrived at the Bytetown airport and is waiting for his luggage. There are n people (including Byteasar) who were traveling this plane and each of them is waiting for exactly ...
0
votes
0answers
30 views

Why is Expectation Maximization algorithm guaranteed to converge to minimum, even local?

I have read a couple of explanations of EM algorithm (e.g. from Bishop's Pattern Recognition and Machine Learning and from Roger and Gerolami First Course on Machine Learning). The derivation of EM is ...
0
votes
0answers
20 views

Find error in a stochastic algorithm

I have $n$ cities, and I want to simulate the transition of people between these cities according to some rules (not all the cities are connected). Each city have $m_n(t)$ citizens and a rate $r_n(t)$ ...
0
votes
0answers
25 views

Probablity of producing a finer balance in quicksort

So this question is a starred one in CLRS Q) Argue that for any constant 0< $\alpha$ $\leq$1/2, the probability is approximately 1-2$\alpha$˛that on a random input array, PARTITION produces a ...
6
votes
2answers
178 views

Average complexity of random-pick comparison sort

Motivation. Suppose we have a number of images that we want to arrange in a linear order from the prettiest to the ugliest. At our disposal we have a trained aesthete, whom we can show two pictures ...
1
vote
0answers
45 views

Proof of the Surfer Model Pagerank formula

How do you prove this formula for the Surfer Pagerank algorithm mathematically? ...
0
votes
1answer
41 views

Help with probability formula in programming problem

I am trying to solve this dynamic programming problem using probabilities. I know how the recurrence for it should look but I have problems using a probability formula. I have the next case: In a ...
0
votes
1answer
31 views

Help Specify possible definitions for this Boolean Function

My math is rusty, but I need some guidance here. Problem I wish to design a stochastic, boolean procedure $f(state)$, that picks a winner, $f(state_{win})\to 1$ or loser, $f(state_{loss})\to 0$. I ...
0
votes
0answers
44 views

GA (Genetic Algorithm) and stochastic simulation to solve optimization in R

My problem is to solve the following optimisation problem using GA (Genetic Algorithm)and stochastic simulation. The goal is to solve the maximisation problem : \begin{equation*} \begin{aligned} ...
7
votes
2answers
239 views

Probability that a vertex in the spanning tree of an $N$ x $N$ grid graph is a leaf

Suppose we have an $N$ x $N$ grid graph $G(V,E)$ and we construct a spanning tree of this graph in the following way. Start with a set $S$ which contains only the vertex at the top left corner of the ...
5
votes
2answers
93 views

Puzzle about voting

I came across about this puzzle which I'm not sure how to go about. Suppose there are $L$ leaders and $F$ followers, with $1 < L<<F$. A leader makes a binary decision, $0$ or $1$ with same ...
0
votes
0answers
36 views

Probability, linear independence and study of variant of Lights Out

Using Arduino, some leds and pushbuttons I've created a simple variant of the mathematically popular game "Lights Out". In my variant, the starting configuration is always all lights on; what changes ...
2
votes
0answers
95 views

Is there any efficient algoritm to solve the given $2$ equations?

My equations are as follows: $$\alpha(A,B)=\frac{\sum_{n=1}^\infty P_0[T=n|A,B]\left(nK_0-s_n\right)}{\sum_{n=1}^\infty P_1[T=n|A,B]r_n-\sum_{n=1}^\infty P_0[T=n|A,B]s_n}$$ ...
2
votes
0answers
24 views

Random convex shapes containing a ball

I'm interested in the properties of randomly generated convex shapes in $n$-dimensional space. Suppose I were to generate $v$ uniformly distributed random points on the $n$-ball of radius $R$. What ...
0
votes
1answer
121 views

probability of sum of a given set of whole numbers being greater than a certain number

There are total of n balls in k boxes. Box one contains n1 balls, box 2 contains n2 balls and so on. The probability of picking balls from boxes is p1,p2,...,pk. We can pick either all the balls in a ...
2
votes
1answer
714 views

What is the expected number of swaps performed by Bubblesort?

The well-known Bubblesort algorithm sorts a list $a_1, a_2, . . . , a_n$ of numbers by repeatedly swapping adjacent numbers that are inverted (i.e., in the wrong relative order) until there are no ...
1
vote
1answer
108 views

Require help in writing the algorithm for my cricket simulation game

I am trying to write the algorithm for a cricket simulation game which generates runs on each ball between 0 to 6. The run rate or runs generated changes when these factors come into play like Skill ...
2
votes
2answers
93 views

How to pick a random node from a tree?

How can I pick a random node from a tree, given the following constraints? We are given the root of the tree, and at every node we are given its children nodes. But we do not know what its children ...
1
vote
1answer
100 views

How to vary lambda in exponentially distributed numbers

I am implementing an exponentially distributed random number generator (RNG) based on George Marsaglia's Ziggurat algorithm. I previously used the algorithm to create a normally distributed RNG. By ...
1
vote
0answers
57 views

Fast way to estimate cardinal number of subset

I have a large set $S$ of items, but the set is not exactly known. All I know are the cardinal numbers of categories i.e. a number of disjoint subsets, $ \vert{S_1}\vert \dots \vert S_n\vert$ with ...
-1
votes
1answer
56 views

How to compute conditional expectation of a log function

I've been studying the Expectation Maximization algorithm. According to the formula shown here, what I have to do in the M step is to compute a new $\theta$ that maximizes the conditional expectation ...
0
votes
1answer
146 views

PageRank algorithm. Iterative approach.

Given we have 4 nodes: A, B, C, D. A -> B and A <- B, B -> C, C -> D, C -> A and C <- A, D->A. We know only the starting probability of C which is 1. If we start from node C, what are the ...
1
vote
2answers
557 views

gradient descent optimal step size

Suppose a differentiable, convex function $F(x)$ exists. Then $b = a - \gamma\bigtriangledown F(a)$ imples that $F(b) <= F(a)$ given $\gamma$ is chosen properly. The goal is to find the optimal ...
0
votes
1answer
118 views

Using Chernoff bound to analysis the Lazyselect algorithm

It's my homework of the course of randomized algorithm. In the textbook (Randomized Altorithm by Rajeev Motwani et.al.), the author analyzed this algorithm using Chebyshev bound, but are there any ...
2
votes
1answer
154 views

Quicksort analysis problem

This is a problem from a probability textbook, not a CS one, if you are curious. Since I'm too lazy to retype the $\LaTeX$ I will post an ugly stitched screenshot: This seems ridiculously hard to ...
0
votes
1answer
47 views

Probability of getting distinct numbers out of two differently distributed variables.

Assume you have $X$ and $Y$. They both take the same values, but they have different distributions, for example: $X$, $Y$ can be: $\{1,2,3\}$ $X$ has probabilities: $\{\frac{2}{7}$ ...
2
votes
1answer
101 views

Bounding the power of expected value of functions of a random variable.

I am interested in a problem and I do not know where to start looking for possible similar setting. If anyone has a direction to suggest, it would be greatly appreciated. Consider a (finite) set ...
0
votes
1answer
251 views

How can I calculate the exact expected value of merge sort comparison (not O(n))?

First, the question stated that I have one unsorted list and then I have to split it out into two lists by fair coin flips. (Ex. Head goes A-list, tail goes B-list) Second, I'm trying to solve the ...
2
votes
4answers
269 views

Can you simulate any probability with biased coin throws?

What you're given: $p \in (0,1)$, but you don't know the value of $p$. You have an algorithm $\mathcal{A}_p$ that returns $1$ with a probability of $p$ and $0$ with a probability of $(1-p)$. You ...
5
votes
2answers
129 views

Choosing between $n$ things using dice?

For which $n$ is there a finite algorithm to choose between $n$ things with the same probability using a die? For example, we can choose between 2 things, 3 things, 4 things, 6 things, and 8 things, ...
0
votes
1answer
42 views

Probability : Dividing a list into 2 classes

I have a list of integer numbers ($n$). I am dividing it into two parts $n_1$ (smaller) and $n_2$ (bigger) such that the length of $n_1 \ge a*n$; $a$ is positive and $a \lt 0.5$. What is the ...
1
vote
0answers
71 views

Maximum Independent Set on Path and Ring

I known this question is more appropriate to cs.stackexchange.com, nevertheless I want to ask it in Mathematics part because for solving the following problem strong understanding of probabilistic ...
1
vote
1answer
46 views

Median-of-k elements

Assume I am given a sequence of $n$ elements (by sequence I mean an ordered set). I want to randomly pick $k$ elements out of these $n$ elements, where $k$ is an odd number $\leq n$. Then out of ...
4
votes
1answer
279 views

Puzzle : Birds on a circular wire

The problem is taken from my course on randomized algorithms : There is a circle made of wire. n birds (assume n>2) occupy uniformly random position over it (visualize each bird occupying a point on ...
2
votes
1answer
125 views

Probability - Expected value of a $n$ random selection

Given an integer $n$, one does $n$ random selections with repetition one after the other. For each selection there are two possibilities a success $X$ and a failure $O$. For each selection $i\le n$ ...
1
vote
1answer
93 views

How to compare time complexities involving an exponential and a polynomial?

A sequence of events $A_n, n \in \mathbb{N}$ is said to have a high probability, if $\mathrm{P} (A_n^c) \leq \frac{c}{n^d}$ for some $c, d >0$. Chernoff bounds are often used to prove some (upper ...
1
vote
2answers
1k views

Intuition behind the concept of indicator random variables.

I am studying Randomized Algorithms chapter in the book "Introduction to Algorithms" by Cormen et al. In this chapter the book introduces the concept of an indicator random variable and state that ...
4
votes
1answer
126 views

Probabilistic Sieve of Eratosthenes

Consider the following algorithm: ...
5
votes
1answer
1k views

Quick sort algorithm average case complexity analysis

This is for self-study. This question is from Kenneth Rosen's "Discrete Mathematics and Its Applications". The quick sort is an efficient algorithm. To sort $a_1,a_2,\ldots,a_n$, this algorithm ...
3
votes
2answers
343 views

Monte Carlo algorithm that determines if a permutation of the integers 1 through $n$ has already been sorted.

This question is from "Discrete Mathematics and Its Applications", from Kenneth Rosen, 6th Edition. Devise a Monte Carlo algorithm that determines whether a permutation of the integers 1 through ...
0
votes
1answer
45 views

random Algorithm over Random input-help needed

A random Algorithm $A$ receives input in $[n]$ it's know that when the probability is taken over input that was chosen randomly over uni-formal distribution over the algorithm randomness the ...