0
votes
0answers
14 views

Randomize algorithm three times for modified values

Let $F:\{0,\ldots,n-1\}\rightarrow\{0,\ldots,m-1\}$ be a function such that $$F((x+y)\bmod n)=(F(x)+F(y))\bmod m$$ for $0\leq x,y\leq n-1$. Now, $1/5$ of the values of $F(x)$ that we store have been ...
1
vote
2answers
23 views

Alternative hash table analysis

Let us say that we have to hash $n$ elements to $m$ hash slots. Now what could be the average length of a chain. We can assume that prob. that 2 elements will map to a particular location will be ...
0
votes
2answers
41 views

Find expected value of F(N)

If we are given that a variable X is defined as X=rand() % N Here rand() returns an integer between 0 and $10^{100}$ (inclusive) uniformly at random. Now we ...
0
votes
1answer
37 views

Quicksort probabilistic analysis

Let us say that we randomly pick up a pivot element and partition the array around it. What is the probability that we always pick the pivots in subsequent recursive calls such that it partitions the ...
0
votes
0answers
29 views

Native algorithm for lottery

Consider a simple lottery game that you are required to pick 6 numbers out of 50 numbers (1 to 50), and you have the history of the most recent n games' result, by ...
0
votes
0answers
9 views

pick rx unique elements from set of x elements (percolation run time)

I have written a program to run experiments on percolation with a square grid of side $N$. The grid starts with all closed spaces, and spaces are open one at a time until there is an open path from ...
1
vote
1answer
53 views
0
votes
0answers
38 views

Can someone help me with the following math question/dilemma?

I have a pool of objects that are randomly selected from a global object database. The objects certain numeric attributes: The objects from the pool are fed to users in real time Users will either ...
2
votes
1answer
29 views

The probability of getting a certain image by random pixelation

Well, seeing that I'm terribly bad at math I don't know how to solve this, I'll try to explain, excuse me if I sound dumb. Just suppose that I've got a photo/image with 320x240 resolution and 24 bit ...
0
votes
1answer
50 views

Need to figure out how to do the math for deck of cards using different searches.

Below are the two questions I found from the websites ( I have added the link below ), that I am interested in learning the answers. My intention are not to post the answers for that guy but, I ...
-1
votes
1answer
48 views

Probability of 1 at both end of string

Given a string S having N characters long and consists of only 1s and 0s. Now given an integer K, let us pick two indexes i and j at random between 1 and N, both inclusive. What's the probability ...
0
votes
4answers
40 views

Generate random numbers in a random fashion

How can I generate 9 random numbers between 1 to 9,without repetition, one after another. Its like: Lets assume that the first random number generated is 4, then the next random number has to be in ...
0
votes
1answer
39 views

Prove that $\sum_{i=0}^\infty i p_i = \sum_{i=1}^\infty q_i$

Given a table with m slots, indexed $0,1,\dots, m-1$ and n keys that are included in this table, $n \lt m$, with $m-n$ slots being empty, I'm given an algorithm that given a certain permutation of the ...
2
votes
0answers
18 views

map if-then-else to probability [closed]

I need an algorithm to transform game rules (p&p role playing) to probabilities, specifically conditional constructs built from if-then-else with conditions made of the boolean and relational ...
2
votes
0answers
58 views

“Alice and Bob” problem with matrices

Alice has a binary matrix $A$, and Bob has a binary matrix $B$. Both matrices are of size $n \times n$. Alice and Bob want to check if the matrices are equal except for exactly $1$ entry. Alice has to ...
0
votes
2answers
407 views

Game of cards and GCD

Alice and Bob play the game. The rules are as follows: Initially, there are n cards on the table, each card has a positive integer written on it. At the beginning Alice writes down the number 0 on ...
1
vote
0answers
26 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
65 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
191 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
33 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
26 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
95 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
21 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
120 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
21 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
46 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
35 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
21 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
70 views

Probability 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
198 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
55 views

Proof of the Surfer Model Pagerank formula

How do you prove this formula for the Surfer Pagerank algorithm mathematically? ...
0
votes
1answer
55 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
57 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
3answers
262 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
97 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
40 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 ...
3
votes
0answers
41 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
134 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 ...
4
votes
1answer
1k 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
159 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
135 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
110 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
65 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
64 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
200 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 ...
2
votes
3answers
1k 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
135 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
169 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
50 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}$ ...