Undergrad About control random variables

[KFC]

Hi all,
I am developing a very simple computer game to randomly move a point to on a bound region and check how many steps it takes to have the point landing to a certain place. To make it simple, I assume it is a 1D problem, the point could start on origin or any location on positive x axis. The point can only sit in or move to a site of integer coordinate. Also, the point can only move forward and steps to move is limited to a finite set of positive numbers including zero.

STEPS = {0, 1, 2, 3, 5, 8, 12, 13, ...}

So for each movement, the point is either not moving or move forward by a certain steps. If we assume the step is randomly picked from above set, and maximum N movements could be made, it is easy to estimate the most likely position that the point will land on after N movements. But what I am thinking is if we would like the movement is randomly picked and we desired the point will have very high chance to land on neighbor of a specified location in specified N movements, is it possible to find a distribution of those random variable to satisfy this? I wonder if there is any theory or research about this inverse problem. For small set, what I can do is to use computer to search all possible combination to approach the location in desired movements. But for larger set, it takes forever to do so.

 

[QuantumQuest]

Hi all,
I am developing a very simple computer game to randomly move a point to on a bound region and check how many steps it takes to have the point landing to a certain place. To make it simple, I assume it is a 1D problem, the point could start on origin or any location on positive x axis. The point can only sit in or move to a site of integer coordinate. Also, the point can only move forward and steps to move is limited to a finite set of positive numbers including zero.

STEPS = {0, 1, 2, 3, 5, 8, 12, 13, ...}

So for each movement, the point is either not moving or move forward by a certain steps. If we assume the step is randomly picked from above set, and maximum N movements could be made, it is easy to estimate the most likely position that the point will land on after N movements. But what I am thinking is if we would like the movement is randomly picked and we desired the point will have very high chance to land on neighbor of a specified location in specified N movements, is it possible to find a distribution of those random variable to satisfy this? I wonder if there is any theory or research about this inverse problem. For small set, what I can do is to use computer to search all possible combination to approach the location in desired movements. But for larger set, it takes forever to do so.

You're basically asking for a maximum-likelihood estimation of some parameter(s) on a graph. This can be tackled using various methods.

If you are not familiar with MLE, I recommend taking a look first at Wikipedia for MLE (Maximum Likelihood Estimation).

For small set, what I can do is to use computer to search all possible combination to approach the location in desired movements. But for larger set, it takes forever to do so

Brute force searching and brute force algorithms in general can work in a more or less acceptable way for small sets, but for anything larger you need some specific optimization algorithm(s). I recommend taking a look here about MLE with some examples and also at Statlect. Also, there is a good article from Harvard for a more advanced situation of exponential random graph models.

 

[mfb]

But what I am thinking is if we would like the movement is randomly picked and we desired the point will have very high chance to land on neighbor of a specified location in specified N movements

How large is that neighborhood? How large are your typical numbers?

This looks like a standard optimization problem (fit free parameters to maximize some value that depends on those parameters), but I'm a bit worried about the parameter landscape if the neighborhood is too small. You can have several strong local optimal parameter values, and finding the global optimum could be tricky and need many runs of the optimization.

As an example, let's try to reach 30 exactly in 4 steps, where STEPS = {0,7,8,10}. There are just two options: 0,10,10,10 and 7,7,8,8 (order is free of course). The probabilities "50% for 7 and 8, 0% for 0 and 10" lead to 6/16=0.375 success chance, and every small change of those numbers will make it worse. It is not the optimal choice, however: the probabilities "25% for 0, 75% for 10, 0% for 7 and 8" lead to a success chance of 27/64 = 0.422.

 

[StoneTemplePython]

OPs question isn't totally clear to me. If N iterations is large, and each iteration is independent, I have a few different ideas. The gist of it is to use the expected value and i.i.d. random variables. You can use chernoff bounds with respect to the neighborhood around the mean.

(Alternatively you could probably set this up as a markov chain and play around with eigenvalues with magnitude less than one, though this would probably be more trouble than its worth.)